Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Новые рефераты » Алгоритми розв'язання задач

Реферат Алгоритми розв'язання задач





кладі графа, показаного на малюнку 4. Нехай потрібно знайти найкоротші відстані від 1-й вершини до всіх інших.

Кружками позначені вершини, лініями - шляху між ними (ребра графа). У гуртках позначені номери вершин, над ребрами позначена їх «ціна» - довжина шляху. Поряд з кожною вершиною червоним позначена мітка - довжина найкоротшого шляху в цю вершину з вершини 1.

Перший крок. Розглянемо крок алгоритму Дейкстри для нашого прикладу. Мінімальну мітку має вершина 1. Її сусідами є вершини 2, 3 і 6.


Рис. 4


Рис. 5


Рис. 6


Перший по черзі сусід вершини 1 - вершина 2, тому що довжина шляху до неї мінімальна. Довжина шляху в неї через вершину 1 дорівнює сумі значення мітки вершини 1 і довжини ребра, що йде з 1-й в 2-ю, тобто 0 + 7=7. Це менше поточної мітки вершини 2, нескінченності, тому нова мітка 2-й вершини дорівнює 7.


Рис. 7


Аналогічну операцію проробляємо з двома іншими сусідами 1-й вершини - третій і 6-й.


Рис. 8


Всі сусіди вершини 1 перевірені. Поточне мінімальна відстань до вершини 1 вважається остаточним і перегляду не підлягає (те, що це дійсно так, уперше довів Е. Дейкстра). Викреслимо її з графа, щоб відзначити, що ця вершина переглянуло.


Рис. 9


Другий крок. Крок алгоритму повторюється. Знову знаходимо «найближчу» з невідвіданих вершин. Це вершина 2 з міткою 7.


Рис. 10


Знову намагаємося зменшити мітки сусідів обраної вершини, намагаючись пройти в них через 2-ю вершину. Сусідами вершини 2 є вершини 1, 3 і 4.

Перший (по порядку) сусід вершини 2 - вершина 1. Але вона вже переглянуло, тому з 1-й вершиною нічого не робимо.

Наступний сусід вершини 2 - вершина 3, оскільки має мінімальну мітку з вершин, відзначених що не відвідані. Якщо йти в неї через 2, то довжина такого шляху буде дорівнює 17 (7 + 10=17). Але поточна мітка третій вершини дорівнює 9, а це менше 17, тому мітка не змінюється.


Рис. 11


Ще один сусід вершини 2 - вершина 4. Якщо йти в неї через 2-ю, то довжина такого шляху буде дорівнює сумі найкоротшої відстані до 2-й вершини і відстані між вершинами 2 і 4, тобто 22 (7 + 15=22). Оскільки, встановлюємо мітку вершини 4 рівний 22.

Всі сусіди вершини 2 переглянуті, заморожуємо відстань до неї і помічаємо її як відвіданих.


Рис. 12


Рис. 13

Третій крок. Повторюємо крок алгоритму, вибравши вершину 3. Після її «обробки» отримаємо такі результати:


Рис. 14


Подальші кроки. Повторюємо крок алгоритму для залишилися вершин. Це будуть вершини 6, 4 і 5, відповідно до порядку.


Рис. 15

Завершення виконання алгоритму. Алгоритм закінчує роботу, коли не можна більше обробити жодної вершини. У даному прикладі всі вершини закреслено, проте помилково вважати, що так буде в кожному прикладі - деякі вершини можуть залишитися незачеркнутимі, якщо до них не можна добратися. Результат роботи алгоритму видно на останньому малюнку: найкоротший шлях від вершини 1 до 2-й становить 7, до третього - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.


. 2 Аналіз алгоритму Флойда


Алгоритм Флойда - динамічний алгоритм для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблено в 1962 році Робертом Флойдом, хоча в 1959 році Бернард Рой (Bernard Roy) опублікував практично такий же алгоритм, але це залишилося непоміченим.

Цей алгоритм більш загальний порівняно з алгоритмом Дейкстри, оскільки він знаходить найкоротші шляхи між будь-якими двома вузлами мережі. У цьому алгоритмі мережа представлена ??у вигляді квадратної матриці з n рядками і n стовпцями. Елемент (i, j) дорівнює відстані d ij від вузла i до вузла j, яке має кінцеве значення, якщо існує дуга (i, j), і дорівнює нескінченності в іншому випадку.

Покажемо спочатку основну ідею методу Флойда. Нехай є три вузли i, j і k і задані відстані між ними (рис. 1). Якщо виконується нерівність d ij + d jk lt; d ik, то доцільно замінити шлях i - gt; k шляхом i - gt; j - gt; k. Така заміна (далі її будемо умовно називати трикутним оператором) виконується систематично в процесі виконання алгоритму Флойда.


Рис.16. Трикутний оператор


Назад | сторінка 3 з 7 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Пошук вершини в графі між двома заданими вершинами
  • Реферат на тему: Розробка та реалізація алгоритму Флойда і Беллмана-Форда для пошуку найкоро ...
  • Реферат на тему: Пошук найкоротшого шляху між парами вершин в орієнтованому і неориентирован ...
  • Реферат на тему: Реалізація алгоритму знаходження множин елементарних циклів графа засобами ...
  • Реферат на тему: Розробка та реалізація мовою високого рівня алгоритму виділення сільносвязн ...