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