Материал: Проектирование вычислительной системы транспортной логистики

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

. Верхняя вершина стека является текущей. Осуществляется проверка того, а не дошли ли мы до финальной вершины.

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

из стека вершин текущего маршрута извлекается верхняя вершина;

из стека рёбер текущего маршрута извлекается верхнее ребро;

вес текущего маршрута уменьшается на вес извлечённого ребра;

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

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

вершина, в которую попадает ребро, добавляется в стек вершин и становится текущей;

ребро добавляется в стек, в котором хранится текущий маршрут;

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

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

из стека вершин текущего маршрута извлекается верхняя вершина;

из стека рёбер текущего маршрута извлекается верхнее ребро;

вес текущего маршрута уменьшается на вес извлечённого ребра;

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

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

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

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

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

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

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

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

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

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

В первой очереди будут храниться стеки вершин потенциальных маршрутов.

Во второй очереди будут храниться стеки рёбер потенциальных маршрутов.

В третьей очереди будут храниться веса потенциальных маршрутов.

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

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

Основной цикл до опустения очереди вершин будет выглядеть следующим образом:

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

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

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

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

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

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

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

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

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

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

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

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

. Увеличивается количество активных потоков.

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

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

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