екурсія є дуже природним прийомом при роботі з графами. Враховуючи той факт, що використання рекурсії може призводити до уповільнення роботи алгоритму в наступному параграфі буде розглянута версія алгоритму пошуку в глибину без використання рекурсії.
Основна ідея алгоритму полягає в наступному.
У функцію передається 4 параметра:
. Вершина, в якій ми зараз знаходимося (з якої вершини прийшли).
. Вершина, в яку ми хочемо піти.
. Ребро, за яким ми хочемо піти.
. Вершина, в яку ми хочемо потрапити.
Функція містить надлишкові дані (наприклад, знаючи поточну і наступну вершину ми легко можемо відновити ребро, по якому ми хочемо піти), але це спрощує реалізацію алгоритму, тому не вимагає організації додаткового пошуку в графовой структурі даних.
Стеки вершин і ребер, а також вартості поточного і оптимального шляху задаються за допомогою глобальних змінних.
При першому запуску алгоритму, ми не перебуваємо ні в одній з вершин, тому перший параметр функції приймає значення мінус одиниця. Аналогічна ситуація складається з третім параметром. У зв'язку з тим, що ми потрапляємо в стартову вершину не через якусь із існуючих ребер, то цей параметр так само дорівнює мінус одиниці. Другий параметр відповідає стартовою вершині. Четвертий параметр відповідає тій вершині, в яку ми хочемо потрапити.
Перейдемо до штатного режиму роботи алгоритму.
В-першу чергу перевіряється «А чи можна йти в цю вершину?».
Йти не можна якщо:
· ми вже були в цій вершині (якщо знехтувати цією умовою, то можливе утворення циклів, а тому ваги ребер у нас завжди позитивні, то шлях, в якому є цикл, ніколи не зможе стати оптимальним);
· вершина заблокована;
· ребро заблоковано.
Якщо можна, то функція достроково припиняє свою роботу.
По-друге, перевіряється «А чи потрібно йти в цю вершину?».
Йти не потрібно якщо:
· якщо ми отримаємо шлях важчий, ніж поточний оптимальний (ця евристика дозволяє нам не розглядати повністю всі шляхи і скорочувати перебір, відсікаючи непотрібні гілки, в тому випадку, якщо наперед відомо, що маршрут з поточним префіксом не зможе бути оптимальним);
· якщо ми отримаємо кількість пересадок, більше, ніж закладено в обмеженні (це основна відмінність класичного алгоритму пошуку в глибину від розглянутого при вирішенні поставленого завдання).
Якщо не потрібно, то функція достроково припиняє свою роботу.
Після цих перевірок вершина, яка підходить за всіма параметрами, додається в стек вершин, в якому зберігається поточний шлях.
Потім перераховуються показники.
· збільшується вага поточного шляху (відповідно на вагу ребра, по якому був зроблений черговий крок алгоритму пошуку в глибину);
· при необхідності збільшується кількість пересадок.
Робиться перевірка «А чи не досягли ми заданої вершини?».
Якщо вершина досягнута, то робиться перевірка на те, а чи не є поточний шлях більш оптимальним (в сенсі сумарної ваги), в порівнянні з поточним кандидатом на оптимальність. Якщо поточний шлях краще, то він записується на місце оптимального.
Далі здійснюється крок рекурсії. Для всіх ребер, що виходять з поточної вершини, робиться рекурсивний виклик, тим самим забезпечується повний перебір, який і потрібно для вирішення поставленого завдання.
При нормальному завершенні роботи функції необхідна реалізація коректного повернення з рекурсії, тобто мають бути перераховані показники:
· зменшується вага поточного шляху (тому ми рухаємося назад по маршруту);
· при необхідності зменшується кількість пересадок.
І, нарешті, з стека витягується поточна вершина.
3.4.3 Пошук в глибину (нерекурсивними версія)
нерекурсивними версія цього алгоритму може мати виграш по швидкості роботи в зв'язку з тим що:
· Кожен виклик рекурсивної функції призводить до того, що відбувається надстраіваніе програмного стека, зберігається точка повернення, створюється оточення для запуску функції, виділяється пам'ять під локальні змінні і т.д.
o збільшуються вимоги по пам'яті;
o збільшуються вимоги за кількістю виконуваних інструкцій.
· Крім того, алгоритм вже має у своєму с...
