На головну

Метод присвоєння міток

  1. B) Систематизація конкретно-наукових і загальнонаукових методів пізнання.
  2. D. Симплекс-метод
  3. FDDI. Архітектура мережі, метод доступу, стек протоколів.
  4. I. Внесення відомостей в форму ДМВ-1 при використанні методу визначення митної вартості за ціною угоди із ввезених товарів
  5. I. МЕТОДИКА
  6. I. Методичні вказівки для виконання контрольних робіт
  7. I. Методичні вказівки з підготовки

Завдання полягає в тому, щоб знайти найкоротший шлях на графі від якоїсь виділеної вершини до будь-якої іншої вершини.

приклад: Вузол 7 - склад, інші вузли - будівельні майданчики компанії. Показники на дугах - відстані в кілометрах.

 Треба знайти найкоротші відстані від складу до кожної будівельного майданчика.

Яка довжина найкоротшого шляху від складу до будівельного майданчика 1?

Чи проходить найкоротший шлях від складу до будівельного майданчика 1 через будівельний майданчик 2?

Яка довжина найкоротшого шляху від складу до будівельного майданчика 2?

Чи проходить найкоротший шлях від складу до будівельного майданчика 2 через будівельний майданчик 4?

Кожному вузлу приписують мітку з двох чисел:

- Перше число - мінімальна відстань від вузла 7 до даного вузла,

- Друге - номер попереднього вузла на шляху від вузла 7 до даного вузла.

позначеним називають вузол, для якого визначено шлях від вузла 7. Інакше вузол - Непомічені.

Якщо найкоротша відстань від вузла 7 до даного вузла визначено, то відповідна позначка постійна і позначається в круглих дужках. решта мітки тимчасові і позначаються у квадратних дужках. Вузли з постійними мітками зафарбовує.

Вузлу 7 присвоюємо мітку (0, S), де 0 - відстань від вузла 7, S - позначення стартового вузла.

Вузол 7 пов'язаний з вузлами 2, 4 і 6. Їм присвоюємо відповідні мітки - [17, 7], [5, 7], [6, 7].

Після виконання цієї операції виконують два кроки:

- Знаходять ділянку мінімальної довжини і відповідну тимчасову мітку роблять постійної;

- Вузол, якому відповідав би дана постійна мітка стає новим стартом.

Мітка з найменшою відстанню [5, 7] відповідає вузлу 4. Цей вузол оголошуємо поміченим і замінюємо дужки у мітки.

Вузол 4 пов'язаний безпосередньо з вузлами 2 і 5 без постійних міток. Тимчасова мітка вузла 5 дорівнює [5 + 4, 4] = [9, 4], а у вузла 2 - [5 + 6, 4] = [11, 4]. Оскільки вузол 2 вже має тимчасову мітку [17, 7], то з двох міток вибираємо ту, в якій відстань менше, тобто [11, 4].

З усіх тимчасових міток [11, 4], [9, 4], [6, 7] вибираємо мітку з найменшим першим числом - [6, 7]. Вона стає постійною і черговий крок починаємо з вузла 6.

Цей вузол пов'язаний тільки з вузлом 5 без постійної мітки. Тимчасова мітка вузла 5 дорівнює [6 + 2, 6] = [8, 6]. Ця мітка має меншу перше число, ніж попередня, тому вузлу 5 приписуємо нову тимчасову мітку [8, 6].

З усіх тимчасових міток [11, 4], [8, 6] мітку з найменшим першим числом [8, 6] оголошуємо постійної і наступний крок починаємо з відповідного їй вузла 5.

Вузол 5 пов'язаний тільки з одним вузлом без постійної мітки - вузлом 3. Тимчасова мітка вузла 3 дорівнює [8 + 4, 5] = [12, 5].

З усіх тимчасових міток [11, 4], [12, 5] мітку з найменшим першим числом [11, 4] оголошуємо постійної і наступний крок починаємо з відповідного їй вузла 2.

Вузол 2 пов'язаний з вузлами і 1 і 3 без постійних міток. Тимчасова мітка вузла 1 дорівнює [11 + 15, 2] = [26, 2], а вузла 3 - [11 + 3, 2] = [14, 2]. Оскільки вузол 3 вже позначений міткою з меншим першим числом, то мітку не змінюємо.

З тимчасових міток [26, 2], [12, 5] мітка з найменшим першим числом [12, 5] стає постійною і наступний крок починаємо з відповідного їй вузла 3.

Мітку вузла 1 міняємо на (12 + 10, 3) = (22, 3).

Всіх вузлів приписані постійні мітки. Дія алгоритму припиняється.

Перше число мітки у кожної вершини - це довжина найкоротшого шляху від вузла 7 до даної вершини. Щоб відновити найкоротший шлях від вузла 7 до якоїсь вершини, потрібно з цієї вершини перейти в сусідню (її номер - друге число мітки) і т.д. до вершини 7.

Відповіді на питання завдання:

Мітка вузла 1 - (22, 3), отже, довжина найкоротшого шляху від вузла 7 до вузла 1 дорівнює 22. Щоб визначити шлях, дивимося друге число мітки: з вузла 1 йдемо в вузол 3. мітка вузла 3 - (12, 5) , отже, йдемо в вузол 5. Метка вузла 5 - (8, 6), отже, йдемо в вузол 6. Метка вузла 6 - (6, 7), отже, йдемо в вузол 7. Таким чином, найкоротший шлях 1 -3-5-6-7. Він не проходить через вузол 2.

Два інших питання - на самостійне розгляд.

 



Оптимізаційних задач на графах | МІНІМАЛЬНОЇ ДОВЖИНИ
© um.co.ua - учбові матеріали та реферати