кладі стек, в якому зберігається поточний шлях. В принципі, при використанні рекурсивної версії пошуку в глибину є можливість уникнути необхідності зберігання пройденого шляху в стеку, тому цей шлях може бути відновлений при зворотному ході рекурсії. Крім того, сучасні процесори і компілятори мають ряд механізмів, що оптимізують рекурсивні виклики таким чином, що накладні витрати будуть практично не помітні. Але, враховуючи, що в даному випадку вирішується не класична задача пошуку в глибину, цей підхід може викликати ряд проблем.
У нерекурсивними функцію пошуку в глибину передається тільки два параметри: стартова вершина, і вершина в яку ми хочемо потрапити.
Розглянемо сам алгоритм.
. Здійснюється перевірка того, чи не є стартова вершина збігається з фінальною вершиною. Якщо це так, то здійснюється достроковий вихід з функції пошуку маршруту. При цьому жодне ребро не може бути позначено як частина оптимального шляху т.к. згідно з прийнятими вище обмеженням в графі не можуть бути присутніми петлі. Тому тільки одна вершина додається в список вершин, що входять в оптимальний шлях.
. Для кожної вершини заводиться допоміжний масив, в якому зберігається порядковий номер ребра, яке було обрано перед переходом в наступну вершину. У рекурсивної версії алгоритму не було необхідності в цій змінній, тому ця інформація зберігалася перед рекурсивним викликом в локальної змінної. Елементи цього допоміжного масиву инициализируются значенням мінус одиниця, тому жодне ребро ще не було обрано.
. У стек складається поточна вершина, з якої починається пошук.
. Пошук триває доти, поки не будуть переглянуті всі можливі маршрути. Враховуючи специфіку алгоритму пошуку (яка буде розглянута нижче) при поверненні назад, всі відвідані раніше вершини поступово витягуються з стека. Тому умовою завершення пошуку є витяг з стека останньої вершини (тобто коли він стає порожнім). У рекурсивної версії ми маємо майже аналогічна умова, тільки там порожнім стає стек рекурсивних викликів.
. Верхня вершина стека є поточною. Здійснюється перевірка того, а не дійшли ми до фінальної вершини .. Якщо ми дійшли до фінальної вершини, то необхідно виконати вже стандартну перевірку того, а чи не є знайдений шлях більш легким у порівнянні з поточним кандидатом на оптимальний маршрут. Якщо це дійсно так, то поточний шлях запам'ятовується як оптимальний і його вага так само запам'ятовується. Далі нам необхідно зробити крок назад, що б ми могли перевірити альтернативні шляхи, які виходять з попередньої вершини. Для цього нам необхідно переглянути ребро, що знаходиться на вершині стека ребер, і дізнатися з якої вершини ми прийшли. Сенсу подальшого пересування з фінальної вершини по графу немає, тому далі робиться крок назад :. з стека вершин поточного маршруту витягується верхня вершина ;. з стека ребер поточного маршруту витягується верхнє ребро ;. вага поточного маршруту зменшується на вагу витягнутого ребра ;. якщо повернення назад на один крок пов'язаний з пересадкою, то поточна кількість зроблених пересадок зменшується на одиницю .. У тому випадку, якщо ми ще не дійшли до фінальної вершини нам необхідно переглянути всі ребра, за якими може бути здійснено рух з поточної вершини. При цьому відсікаються шляхи, які приводять нас в вершини, які вже зберігаються в поточному шляху. Це робиться в силу того, що маршрут, що містить цикл ніколи не може претендувати на статус оптимального в плані сумарної ваги відвіданих ребер. Так само не розглядаються заблоковані ребра і ребра, які приводять в заблоковані вершини. В силу обмежень на максимальну кількість пересадок не розглядаються ребра, які призводять до перевищення заданої кількості. Для першого ребра, що пройшов вищевказану перевірку, виконується наступний набір дій :. вершина, в яку потрапляє ребро, додається в стек вершин і стає поточною ;. ребро додається в стек, в якому зберігається поточний маршрут ;. на цьому цикл завершується, тому робиться крок в наступну вершину, але для вершини, з якої робиться крок, запам'ятовується на якому ребрі була зроблена зупинка, з тим, щоб по поверненню в цю вершину, продовжити перебір можливих маршрутів .. Після того, як всі ребра, що виходять з поточної вершини , перевірені, робиться крок назад. Для цього. з стека вершин поточного маршруту витягується верхня вершина ;. з стека ребер поточного маршруту витягується верхнє ребро ;. вага поточного маршруту зменшується на вагу витягнутого ребра ;. якщо повернення назад на один крок пов'язаний з пересадкою, то поточна кількість зроблених пересадок зменшується на одиницю ;. і так як ми пішли з поточної вершини, лічильник проглянутих з неї ребер обнуляється, тобто приймає значення мінус одиниця.
Очевидно, що цей алгоритм є найефективнішим в плані використання оперативної пам'яті, тому м...
