Материал: Программирование на языке С#

. Из стека извлекаются все рёбра вошедшие в оптимальный маршрут.. Каждое ребро, извлечённое из стека, помечается как часть оптимального маршрута. Для каждого ребра, извлечённого из стека, определяются образующие его вершины и так же помечаются как часть оптимального маршрута.

. Осуществляется отрисовка транспортной сети с отмеченным на ней маршрутом.

Поиск в глубину (рекурсивная версия)

Перейдём к самому алгоритму поиска. Данная версия алгоритма поиска в глубину была реализована с использованием рекурсии, т.к. рекурсия является очень естественным приёмом при работе с графами. Учитывая тот факт, что использование рекурсии может приводить к замедлению работы алгоритма в следующем параграфе будет рассмотрена версия алгоритма поиска вглубину без использования рекурсии. Основная идея алгоритма состоит в следующем.

В функцию передаётся 4 параметра:

. Вершина, в которой мы сейчас находимся (из какой вершины пришли).

. Вершина, в которую мы хотим пойти.

. Ребро, по которому мы хотим пойти.

. Вершина, в которую мы хотим попасть.

Функция содержит избыточные данные (например, зная текущую и следующую вершину мы легко можем восстановить ребро по которому мы хотим пойти), но это упрощает реализацию алгоритма, т.к. не требует организации дополнительного поиска в графовой структуре данных.

Стеки вершин и рёбер, а также стоимости текущего и оптимального пути задаются при помощи глобальных переменных.

При первом запуске алгоритма, мы не находимся ни в одной из вершин, поэтому первый параметр функции принимает значение минус единица. Аналогичная ситуация складывается с третьим параметром. В связи с тем, что мы попадаем в стартовую вершину не через какое-либо из существующих рёбер, то этот параметр так же равняется минус единице. Второй параметр соответствует стартовой вершине. Четвёртый параметр соответствует той вершине, в которую мы хотим попасть.

Перейдём к штатному режиму работы алгоритма.

В-первую очередь проверяется "А можно ли идти в эту вершину?". Идти нельзя если:

 мы уже были в этой вершине (если пренебречь этим условием, то возможно образование циклов, а т.к. веса рёбер у нас всегда положительные, то путь, в котором есть цикл, никогда не сможет стать оптимальным);

 вершина заблокирована; ребро заблокировано.

Если нельзя, то функция досрочно прекращает свою работу. Во-вторых, проверяется "А нужно ли идти в эту вершину?". Идти не нужно если:

 если мы получим путь более тяжёлый, чем текущий оптимальный (эта эвристика позволяет нам не рассматривать полностью все пути и сокращать перебор, отсекая ненужные ветви, в том случае, если заведомо известно, что маршрут с текущим префиксом не сможет быть оптимальным); если мы получим количество пересадок, большее, чем заложено в ограничении (это основное отличие классического алгоритма поиска в глубину от рассматриваемого при решении поставленной задачи). Если не нужно, то функция досрочно прекращает свою работу. После этих проверок вершина, которая подходит по всем параметрам, добавляется в стек вершин, в котором хранится текущий путь.

Затем пересчитываются показатели.

увеличивается вес текущего пути (соответственно на вес ребра по которому был сделан очередной шаг алгоритма поиска в глубину); при необходимости увеличивается количество пересадок. Делается проверка "А не достигли ли мы заданной вершины?". Если вершина достигнута, то делается проверка на то, а не является ли текущий путь более оптимальным (в смысле суммарного веса), по сравнению с текущим кандидатом на оптимальность. Если текущий путь лучше, то он записывается на место оптимального.

Далее осуществляется шаг рекурсии. Для всех рёбер, выходящих из текущей вершины, делается рекурсивный вызов, тем самым обеспечивается полный перебор, который и требуется для решения поставленной задачи.

При нормальном завершении работы функции необходима реализация корректного возврата из рекурсии, т.е. должны быть пересчитаны показатели:

 уменьшается вес текущего пути (т.к. мы движемся обратно по маршруту); при необходимости уменьшается количество пересадок. И, наконец, из стека извлекается текущая вершина.

Поиск в глубину (нерекурсивная версия)

Нерекурсивная версия этого алгоритма может иметь выигрыш по скорости работы в связи с тем что:

Каждый вызов рекурсивной функции приводит к тому, что происходит надстраивание программного стека, сохраняется точка возврата, создаётся окружение для запуска функции, выделяется память под локальные переменные и т.д.увеличиваются требования по памяти

o увеличиваются требования по количеству выполняемых инструкций.

Кроме того, алгоритм уже имеет в своём составе стек, в котором хранится текущий путь. В принципе, при использовании рекурсивной версии поиска в глубину есть возможность избежать необходимости хранения пройденного пути в стеке, т.к. этот путь может быть восстановлен при обратном ходе рекурсии. Кроме того, современные процессоры и компиляторы имеют ряд механизмов, оптимизирующих рекурсивные вызовы таким образом, что накладные расходы будут практически не заметны. Но, учитывая, что в данном случае решается не классическая задача поиска в глубину, этот подход может вызвать ряд проблем.

В нерекурсивную функцию поиска в глубину передаётся только два параметра: стартовая вершина, и вершина в которую мы хотим попасть.

Рассмотрим сам алгоритм.

. Осуществляется проверка того, не является ли стартовая вершина совпадающей с финальной вершиной. Если это так, то осуществляется досрочный выход из функции поиска маршрута. При этом ни одно ребро не может быть помечено как часть оптимального пути т.к. согласно принятым выше ограничениям в графе не могут присутствовать петли. Поэтому только одна вершина добавляется в список вершин, входящих в оптимальный путь.

. Для каждой вершины заводится вспомогательный массив, в котором хранится порядковый номер ребра, которое было выбрано перед переходом в следующую вершину. В рекурсивной версии алгоритма не было необходимости в этой переменной, т.к. эта информация сохранялась перед рекурсивным вызовом в локальной переменной. Элементы этого вспомогательного массива инициализируются значением минус единица, т.к. ни одно ребро ещё не было выбрано.

. В стек складывается текущая вершина, с которой начинается поиск.

. Поиск продолжается до тех пор, пока не будут просмотрены все возможные маршруты. Учитывая специфику алгоритма поиска (которая будет рассмотрена ниже) при возврате назад, все посещённые ранее вершины постепенно извлекаются из стека. Поэтому условием завершения поиска является извлечение из стека последней вершины (т.е. когда он становится пустым). В рекурсивной версии мы имеем почти аналогичное условие, только там пустым становится стек рекурсивных вызовов.

. Верхняя вершина стека является текущей. Осуществляется проверка того, а не дошли ли мы до финальной вершины.. Если мы дошли до финальной вершины, то необходимо выполнить уже стандартную проверку того, а не является ли найденный путь более лёгким по сравнению с текущим кандидатом на оптимальный маршрут. Если это действительно так, то текущий путь запоминается как оптимальный и его вес так же запоминается. Далее нам необходимо сделать шаг назад, что бы мы могли проверить альтернативные пути, исходящие из предыдущей вершины. Для этого нам необходимо просмотреть ребро, находящееся на вершине стека рёбер, и узнать из какой вершины мы пришли. Смысла дальнейшего передвижения из финальной вершины по графу нет, поэтому далее делается шаг назад:. из стека вершин текущего маршрута извлекается верхняя вершина;. из стека рёбер текущего маршрута извлекается верхнее ребро;. вес текущего маршрута уменьшается на вес извлечённого ребра;. если возврат назад на один шаг связан с пересадкой, то текущее количество сделанных пересадок уменьшается на единицу.. В том случае, если мы ещё не дошли до финальной вершины нам необходимо просмотреть все рёбра, по которым может быть осуществлено движение из текущей вершины. При этом отсекаются пути, которые приводят нас в вершины, которые уже хранятся в текущем пути. Это делается в силу того, что маршрут, содержащий цикл никогда не может претендовать на статус оптимального в плане суммарного веса посещённых рёбер. Так же не рассматриваются заблокированные рёбра и рёбра, которые приводят в заблокированные вершины. В силу ограничений на максимальное количество пересадок не рассматриваются рёбра, которые приводят к превышению заданного количества. Для первого ребра, прошедшего вышеуказанную проверку, выполняется следующий набор действий:. вершина, в которую попадает ребро, добавляется в стек вершин и становится текущей;. ребро добавляется в стек, в котором хранится текущий маршрут;. на этом цикл завершается, т.к. делается шаг в следующую вершину, но для вершины, из которой делается шаг, запоминается на каком ребре была сделана остановка, с тем, чтобы по возвращению в эту вершину, продолжить перебор возможных маршрутов.. После того, как все рёбра, выходящие из текущей вершины, проверены, делается шаг назад. Для этого. из стека вершин текущего маршрута извлекается верхняя вершина;. из стека рёбер текущего маршрута извлекается верхнее ребро;. вес текущего маршрута уменьшается на вес извлечённого ребра;. если возврат назад на один шаг связан с пересадкой, то текущее количество сделанных пересадок уменьшается на единицу; v. и так как мы ушли из текущей вершины, счётчик просмотренных из неё рёбер обнуляется, т.е. принимает значение минус единица. Очевидно, что этот алгоритм является самым эффективным в плане использования оперативной памяти, т.к. мы храним только один текущий путь. Рассмотрим вопрос, связанный со скоростью работы. Все представленные в этой работе алгоритмы основаны на полном переборе. Во всех алгоритмах используются одинаковые эвристики, позволяющие отсекать заведомо неоптимальные ветви. Следовательно, с этой точки зрения ускорение возможно по следующим направлениям:

. отказаться от рекурсии (что и было сделано в рамках данного алгоритма);

. использование избыточных данных, позволяющих хранить уже рассчитанные значения (что и было сделано во всех предложенных алгоритмах);

. использование многопоточных алгоритмов, рассчитанных на выполнение на многоядерных процессорах (что и будет сделано в следующих разделах).

Поиск в ширину (однопоточная версия)

Функция поиска в ширину является более требовательной в плане использования оперативной памяти, т.к. ней все пути рассматриваются параллельно. Особенно эта проблема становится актуальной в графах с большим количеством связей. Поэтому однопоточная версия этого алгоритма не желательна для использования и приводится в силу того, что на её основе будет строиться многопоточная версия.

Алгоритму на вход подаётся два параметра, номер стартовой вершины и номер конечной вершины. Перед запуском алгоритма осуществляется проверка на то, не совпадают ли стартовая и конечная вершина. В случае совпадения производится досрочный выход из функции подобно тому, как это делалось в предыдущем алгоритме.

Как и раньше текущий путь будет размещаться в структуре данных типа стек. Туда помещается стартовая вершина.

В классической версии поиска в ширину используется структура данных типа очередь. Однако мы не можем использовать только очередь, т.к. нам важен не только обход графа в заданном порядке, нам необходимо иметь возможность хранения всего пройденного пути и сравнения его с оптимальным. Именно в силу этого условия будет использована не просто очередь, а очередь стеков (в каждом стеке будет храниться один из потенциальных путей).

На самом деле будет использовать 4 очереди.

В первой очереди будут храниться стеки вершин потенциальных маршрутов. Во второй очереди будут храниться стеки рёбер потенциальных маршрутов. В третьей очереди будут храниться веса потенциальных маршрутов. И в четвёртой очереди будут храниться количества пересадок сделанных на текущий момент для каждого из потенциальных маршрутов. По мере достижения финальной вершины, маршруты будут удаляться из очередей. Поэтому условием окончания работы алгоритма будет тот факт, что одна из очередей будет пуста. Пусть это будет очередь вершин. Основной цикл до опустения очереди вершин будет выглядеть следующим образом:

. Из начала очереди маршрутов из вершин извлекается маршрут и делается текущим.

. Из начала очереди маршрутов из рёбер извлекается маршрут и делается текущим.

. Из начала очереди весов извлекается вес текущего маршрута. 4. Из начала очереди количества пересадок извлекается текущее количество пересадок.

. Извлекаем с вершины стека вершин текущего маршрута вершину и делаем её текущей.

. Если текущая вершина совпадает с финальной вершиной, то осуществляется проверка того, а не является ли текущий путь более лёгким, по сравнению с текущим, считающимся оптимальным маршрутом. И если это так, то он записывается на его место и его вес также запоминается.

. Если же текущая вершина не является финальной, то нам необходимо сформировать все возможные направления движения из неё исходящие. Для этого просматриваются все рёбра, которые выходят из текущей вершины. Не рассматриваются рёбра, которые приводят к возникновению циклов, т.е. приводят к вершинам уже находящимся в текущем пути. Так же не рассматриваются заблокированные рёбра и рёбра, приводящие в заблокированные вершины. Не рассматриваются рёбра, имеющие такой вес, которые будучи сложенным с текущим весом, будет превышать вес текущего оптимального маршрута. Не рассматриваются рёбра, которые ведут к превышению максимально возможного количества пересадок. После того, как подходящие ребра найдены, для каждого из них осуществляется следующая последовательность действий:. в стек вершин добавляется конечная вершина ребра;. в стек рёбер добавляется ребро;. пересчитывается текущий вес за счёт прибавления веса ребра, по которому осуществляется переход;. пересчитывается текущее количество пересадок, в соответствии с ребром по которому осуществляется переход;. копия стека вершин помещается в конец очереди стеков вершин;. копия стека рёбер помещается в конец очереди стеков рёбер; g. вес текущего пути помещается в конец очереди весов; h. количество пересадок текущего пути помещается в конец очереди количества пересадок;. делается шаг назад путём извлечения вершины из стека текущих вершин и извлечением ребра из стека текущих рёбер, также пересчитывается текущий вес путём вычитания веса удалённого ребра и пересчитывается количество сделанных пересадок в сторону уменьшения.

Поиск в ширину (многопоточная версия)

Этот метод является улучшенной версией поиска в ширину. Он сохраняет тот же самый принцип обхода графа, но позволяет одновременно просматривать сразу несколько потенциальных маршрутов. Распараллеливание поиска в глубину невозможно в силу специфики порядка обхода вершин. В данной версии алгоритма не осуществляется ограничение на максимальное количество одновременно работающих потоков, и при необходимости, может быть осуществлено за счёт использования механизма пула потоков. В силу многопоточности для запуска алгоритма используются дополнительные построения.

. Заводится глобальная переменная, в которой хранится текущее количество активных потоков. Каждый поток при запуске увеличивает её значение и уменьшает перед завершением.

. Заводится вспомогательная структура данных хранящая в себе полный набор параметров необходимых для алгоритма. Это делается в силу того, что функции-делегату представляющей собой тело потока может быть передан только один параметр типа object. В состав структуры входят следующие поля:. текущая вершина; b. конечная вершина; c. текущий вес;. текущее количество пересадок;. стек вершин, входящих в текущий путь; f. стек рёбер, входящих в текущий путь.

После запуска потока для осуществления поиска в ширину главный поток, отвечающий за работу формы должен дождаться завершения всех вспомогательных потоков. Для этого он ждёт завершения первого созданного потока, а затем ждёт пока переменная, в которой хранится текущее количество активных потоков, не станет равной нулю. Отдельное ожидание завершения первого порождённого потока необходимо в силу того, что он может не успеть инициализироваться и инкрементировать значение переменной, в которой хранится текущее количество активных потоков.