1. алгоритм Флойда Розглянутий алгоритм іноді називають алгоритмом Флойда -Уоршелла. Алгоритм Флойда...
2. Ключові терміни

алгоритм Флойда

Розглянутий алгоритм іноді називають алгоритмом Флойда -Уоршелла. Алгоритм Флойда -Уоршелла є алгоритмом на графах, який розроблений в 1962 році Робертом Флойдом і Стівеном Уоршеллом. Він служить для знаходження найкоротших шляхів між усіма парами вершин графа.

Метод Флойда безпосередньо грунтується на тому факті, що в графі з позитивною вагою ребер всякий Неелементарні (що містить більше 1 ребра) найкоротший шлях складається з інших найкоротших шляхів.

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

В алгоритмі Флойда використовується матриця A розміром nxn, в якій обчислюються довжини найкоротших шляхів. Елемент A [i, j] дорівнює відстані від вершини i до вершини j, яке має кінцеве значення, якщо існує ребро (i, j), і дорівнює нескінченності в іншому випадку.

алгоритм Флойда

Основна ідея алгоритму. Нехай є три вершини i, j, k і задані відстані між ними. Якщо виконується нерівність A [i, k] + A [k, j] <A [i, j], то доцільно замінити шлях i-> j шляхом i-> k-> j. Така заміна виконується систематично в процесі виконання даного алгоритму.

Крок 0. Визначаємо початкову матрицю відстані A0 і матрицю послідовності вершин S0. Кожен діагональний елемент обох матриць дорівнює 0, таким чином, показуючи, що ці елементи в обчисленнях не беруть участь. Вважаємо k = 1.

Основний крок k. Задаємо рядок k і стовпець k як провідний рядок і ведучий стовпець. Розглядаємо можливість застосування заміни описаної вище, до всіх елементів A [i, j] матриці Ak-1. Якщо виконується нерівність , Тоді виконуємо наступні дії:

1. створюємо матрицю Ak шляхом заміни в матриці Ak-1 елемента A [i, j] на суму A [i, k] + A [k, j];
2. створюємо матрицю Sk шляхом заміни в матриці Sk-1 елемента S [i, j] на k. Вважаємо k = k + 1 і повторюємо крок k.

Таким чином, алгоритм Флойда робить n ітерацій, після i -й ітерації матриця А буде містити довжини найкоротших шляхів між будь-якими двома парами вершин за умови, що ці шляхи проходять через вершини від першої до i -й. На кожній ітерації перебираються всі пари вершин і шлях між ними скорочується за допомогою i -й вершини ( Мал. 45.2 ).

Мал.45.2.

Демонстрація алгоритму Флойда // Опис функції алгоритму Флойда void Floyd (int n, int ** Graph, int ** ShortestPath) {int i, j, k; int Max_Sum = 0; for (i = 0; i <n; i ++) for (j = 0; j <n; j ++) Max_Sum + = ShortestPath [i] [j]; for (i = 0; i <n; i ++) for (j = 0; j <n; j ++) if (ShortestPath [i] [j] == 0 && i! = j) ShortestPath [i] [j] = Max_Sum; for (k = 0; k <n; k ++) for (i = 0; i <n; i ++) for (j = 0; j <n; j ++) if ((ShortestPath [i] [k] + ShortestPath [k ] [j]) <ShortestPath [i] [j]) ShortestPath [i] [j] = ShortestPath [i] [k] + ShortestPath [k] [j]; }

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

Якщо граф представлений матрицею суміжності, то час виконання цього алгоритму має порядок O (n3), оскільки в ньому присутні вкладені одна в одну три цикли.

Переборні алгоритми

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

Розглянемо Переборні алгоритми, засновані на методах пошуку в графі, на прикладі задачі знаходження найкоротшого шляху в лабіринті.

Постановка завдання.

Лабіринт, що складається з прохідних і непрохідних клітин, заданий матрицею A розміром mxn. Елемент матриці A [i, j] = 0, якщо клітина (i, j) прохідна. В іншому випадку .

Потрібно знайти довжину найкоротшого шляху з клітки (1, 1) в клітку (m, n).

Фактично дана матриця суміжності (тільки в ній нулі замінені нескінченно, а одиниці - нулями). Лабіринт являє собою граф.

Вершинами дерева варіантів в даній задачі є шляхи, що починаються в клітці (1, 1). Ребра - показують хід конструювання цих шляхів і з'єднують два шляхи довжини k і k + 1, де другий шлях виходить з першого додаванням до шляху ще одного ходу.

Перебір з поверненням

Даний метод заснований на методі пошуку в глибину. Перебір з поверненням вважають методом проб і помилок ( "спробуємо сходити в цю сторону: не вийде - повернемося і спробуємо в іншу"). Так як перебір варіантів здійснюється методом пошуку в глибину, то доцільно під час роботи алгоритму зберігати поточний шлях в дереві. Цей шлях є стек Way.

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

Нехай поточної є деяка клітина (на початку роботи алгоритму - клітина (1, 1)). Якщо для поточної клітини є клітина-сусід Neighbor, відсутня в Way, в яку на цьому шляху ще не ходили, то додаємо Neighbor в Way і поточної клітці присвоюємо Neighbor, інакше витягти з Way.

Наведене вище опис дає чітко зрозуміти, чому цей метод називається перебором з поверненням. Поверненню тут відповідає операція "витягти з Way", яка зменшує довжину Way на 1.

Перебір закінчується, коли Way порожній і робиться спроба повернення назад. У цій ситуації повертатися вже нікуди ( Мал. 45.3 ).

Way є поточним шляхом, але в процесі роботи необхідно зберігати і оптимальний шлях OptimalWay.

Удосконалення алгоритму можна зробити наступним чином: не дозволяти, щоб довжина Way була більше або дорівнює довжині OptimalWay. В цьому випадку, якщо і буде знайдений якийсь варіант, він свідомо не буде оптимальним. Таке удосконалення в загальному випадку означає, що як тільки поточний шлях стане свідомо неоптимальним, треба повернутися назад. Дане поліпшення алгоритму дозволяє в багатьох випадках сильно скоротити перебір.

Мал.45.3.

Демонстрація алгоритму перебору з поверненням / * Опис функції переборного алгоритму методом пошуку в глибину * / void Backtracking (int n, int m, int ** Maze) {int Begin, End, Current; Begin = (n - 1) * m; End = m - 1; int * Way, * OptimalWay; int LengthWay, LengthOptimalWay; Way = new int [n * m]; OptimalWay = new int [n * m]; LengthWay = 0; LengthOptimalWay = m * n; for (int i = 0; i <n * m; i ++) Way [i] = OptimalWay [i] = -1; int * Dist; Dist = new int [n * m]; for (int i = 0; i <n; i ++) for (int j = 0; j <m; j ++) Dist [i * m + j] = (Maze [i] [j] == 0? 0: - 1); Way [LengthWay ++] = Current = Begin; while (LengthWay> 0) {if (Current == End) {if (LengthWay <LengthOptimalWay) {for (int i = 0; i <LengthWay; i ++) OptimalWay [i] = Way [i]; LengthOptimalWay = LengthWay; } If (LengthWay> 0) Way [- LengthWay] = -1; Current = Way [LengthWay-1]; } Else {int Neighbor = -1; if ((Current / m - 1)> = 0 &&! Insert (Way, Current - m) && (Dist [Current - m] == 0 || Dist [Current - m]> LengthWay) && Dist [Current] < LengthOptimalWay) Neighbor = Current - m; else if ((Current% m - 1)> = 0 &&! Insert (Way, Current - 1) && (Dist [Current - 1] == 0 || Dist [Current - 1]> LengthWay) && Dist [Current] <LengthOptimalWay) Neighbor = Current - 1; else if ((Current% m + 1) <m &&! Insert (Way, Current + 1) && (Dist [Current + 1] == 0 || Dist [Current + 1]> LengthWay) && Dist [Current] < LengthOptimalWay) Neighbor = Current + 1; else if ((Current / m + 1) <n &&! Insert (Way, Current + m) && (Dist [Current + m] == 0 || Dist [Current + m]> LengthWay) && Dist [Current] < LengthOptimalWay) Neighbor = Current + m; if (Neighbor! = -1) {Way [LengthWay ++] = Neighbor; Dist [Neighbor] = Dist [Current] + 1; Current = Neighbor; } Else {if (LengthWay> 0) Way [- LengthWay] = -1; Current = Way [LengthWay-1]; }}} If (LengthOptimalWay <n * m) cout << endl << "Yes. Length way =" << LengthOptimalWay << endl; else cout << endl << "No" << endl; } Лістинг.

хвильовий алгоритм

Цей переборний алгоритм, який заснований на пошуку в ширину, складається з двох етапів:

1. поширення хвилі;
2. Зворотній хід.

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

Мал.45.4.

Демонстрація хвильового алгоритму

Зауважимо, що перебір методом пошуку в ширину в порівнянні з перебором з поверненням, як правило, вимагає більше допоміжної пам'яті, яка необхідна для зберігання інформації, щоб побудувати шлях при зворотному ході і позначити відвідані вершини. Однак він працює швидше, так як абсолютно виключається відвідування однієї і тієї ж клітини більш ніж один раз.

Ключові терміни

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

Алгоритм Флойда - це алгоритм пошуку найкоротшого шляху між будь-якими двома вершинами графа.

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

Найкоротший шлях - це шлях в графі, тобто послідовність вершин і ребер, інцидентних двом сусіднім вершинам, і його довжина.

Переборний алгоритм - це алгоритм обходу графа, заснований на послідовному переборі можливих шляхів.

короткі підсумки

1. Знаходження найкоротшого шляху на сьогоднішній день є актуальним завданням
2. До найбільш ефективним алгоритмам знаходження найкоротшого шляху в графах ставляться алгоритм Дейкстри, алгоритм Флойда і Переборні алгоритми. Ці алгоритми ефективні при досить невеликих кількостях вершин.
3. У реалізації алгоритму Дейкстри будується безліч вершин, для яких найкоротші шляхи від початкової вершини вже відомі. Наступні кроки засновані на додаванні до наявного безлічі по одній вершині із збереженням довжин оптимальних шляхів.
4. Складність алгоритму Дейкстри залежить від способу знаходження вершини, а також способу зберігання безлічі невідвіданих вершин і способи оновлення довжин.
5. Метод Флойда ґрунтується на факті, що в графі з позитивною вагою ребер всякий Неелементарні найкоротший шлях складається з інших найкоротших шляхів.
6. Якщо граф представлений матрицею суміжності, то час виконання алгоритму Флойда має порядок O (n3).
7. Переборні алгоритми є алгоритмами пошуку оптимального рішення.
8. Хвильовий алгоритм є переборного алгоритмом, який заснований на пошуку в ширину і складається з двох етапів: поширення хвилі і зворотний хід.
9. Перебір методом пошуку в ширину, в порівнянні з перебором з поверненням, вимагає більше допоміжної пам'яті для зберігання інформації, проте, він працює швидше, так як виключається відвідування однієї і тієї ж вершини більш ніж один раз.