поміщається в кінець черги ваг ;. кількість пересадок поточного шляху поміщається в кінець черги кількості пересадок ;. робиться крок назад шляхом вилучення вершини зі стека поточних вершин і витяганням ребра з стека поточних ребер, також перераховується поточний вагу шляхом вирахування ваги віддаленого ребра і перераховується кількість зроблених пересадок у бік зменшення.
.4.5 Пошук в ширину (багатопотокова версія)
Цей метод є покращеною версією пошуку в ширину. Він зберігає той самий принцип обходу графа, але дозволяє одночасно переглядати відразу кілька потенційних маршрутів. Розпаралелювання пошуку в глибину неможливо в силу специфіки порядку обходу вершин. У даній версії алгоритму не здiйснюється обмеження на максимальну кількість одночасно працюючих потоків, і п?? і необхідності, може бути здійснено за рахунок використання механізму пулу потоків.
У силу багатопоточності для запуску алгоритму використовуються додаткові побудови.
. Заводиться глобальна змінна, в якій зберігається поточна кількість активних потоків. Кожен потік при запуску збільшує її значення і зменшує перед завершенням.
. Заводиться допоміжна структура даних, що зберігає в собі повний набір параметрів необхідних для алгоритму. Це робиться в силу того, що функції-делегату представляє собою тіло потоку може бути переданий тільки один параметр типу object. До складу структури входять наступні поля :. поточна вершина ;. кінцева вершина ;. поточний вагу ;. поточну кількість пересадок ;. стек вершин, що входять в поточний шлях ;. стек ребер, що входять в поточний шлях.
Після запуску потоку для здійснення пошуку в ширину головний потік, що відповідає за роботу форми повинен дочекатися завершення всіх допоміжних потоків. Для цього він чекає завершення першого створеного потоку, а потім чекає поки змінна, в якій зберігається поточне кількість активних потоків, не стане рівною нулю. Окреме очікування завершення першого породженого потоку необхідно в силу того, що він може не встигнути инициализироваться і інкрементіровать значення змінної, в якій зберігається поточна кількість активних потоків.
Розглянемо сам алгоритм:
. Збільшується кількість активних потоків.
. У локальний стек вершин поміщається поточна вершина.
. Якщо поточна вершина збігається з фінальною вершиною, то необхідно перевірити, чи не є поточний шлях найкращим в порівнянні з кандидатом на оптимальність. Однак, подібна перевірка може бути здійснена тільки в рамках критичної секції, яка допомагає уникнути потенційних конфліктів з паралельними потоками. І, якщо поточний шлях краще воно копіюється в якості оптимального і його вага запам'ятовується (ці дві дії так само повинні здійснюватися в рамках критичної секції).
. Якщо ж ми ще не дійшли до фінальної вершини. Перебираються всі ребра виходять з поточної вершини. Не розглядаються ребра, які призводять до виникнення циклів, тобто призводять до вершин вже знаходяться в поточному шляху. Так само не розглядаються заблоковані ребра і ребра, що приводять у заблоковані вершини. Не розглядаються ребра, що мають таку вагу, які будучи складеним з поточним вагою, буде перевищувати вагу поточного оптимального маршруту. Не розглядаються ребра, які ведуть до перевищення максимально можливої ??кількості пересадок. Після того, як відповідні ребра знайдені, для кожного з них здійснюється наступна послідовність дій :. формується копія поточного стека вершин ;. формується копія поточного стека ребер ;. формується копія ваги поточного шляху ;. формується копія кількості пересадок на поточному шляху ;. в копію стека вершин поміщається кінець ребра, по якому ми хочемо йти ;. в копію сітка ребер поміщається рёбро, за яким ми хочемо йти ;. копія ваги поточного шляху збільшується на вагу ребра, по якому ми хочемо піти ;. копія кількості пересадок на поточному шляху, якщо ребро веде в іншу транспортну мережу ;. і замість того щоб поміщати це все в кінець черги, як це робилося в класичному пошуку в ширину створюється ще один потік із щойно сформованим набором параметрів.
. Після того як всі можливі шляхи з поточної вершини перебрані і відповідні потоки стартували, потік знищується, зменшуючи кількість запущених потоків на одиницю.
3.5 Приклад роботи алгоритму
Розглянемо невеликий приклад. Нехай необхідно знайти шлях з вершини A в вершину H. При двох дозволених пересадках оптимальний шлях (представлений на верхньому малюнку) складається з чотирьох ребер і має вагу рівний 13. При трьох дозволених пересадках оптимальний шлях (представлений на нижньому малюнку) складається з одинадцяти ребер і має вагу рівний 11.
Подібний результат забезпечують всі розроблені алгоритми.
Малюнок 2.1 - Приклад роботи програми
ВИСНОВОК
У ході курсового проекту був ...
