Алгоритм поиска в ширину

Алгоритм поиска в ширину

Алгоритм поиска в ширину

Определение 1

Алгоритм поиска в ширину — это способ обхода графа и определения маршрутов внутри графа.

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

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

Обход вершин ведётся в очерёдности увеличения их удаления от корневого уровня.

Имеем граф G = (V, Е) и корневой уровень S, выбранный для начала обхода. Первым посещается узел S, а затем выполняется посещение смежных с S узлов (множество узлов, которые являются смежными с S, обозначим символом q; подразумевается, что q ⊆ V, то есть q является неким подмножеством V).

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

Выполнение алгоритма прекращается по завершению анализа всего графа, или если будет выполнено заданное условие.

Ничего непонятно?

Попробуй обратиться за помощью к преподавателям

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

Каждый текущий период обхода может быть описан таким образом: если цвет вершины чёрный, то все её «потомки» могут иметь или серые, или чёрные цвета. Итак, есть смешанный граф с |V| = 4 и |E| = 5, представленный на рисунке один. Необходимо пройти все его вершины, применяя алгоритм поиска в ширину. Выберем как корневую (стартовую) вершину, узел с номером три.

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

И, в конечном итоге, вершины четыре и два, осматриваются в этой очерёдности и на этом обход в ширину заканчивается.

Рисунок 1. Смешанный граф. Автор24 — интернет-биржа студенческих работ

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

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

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

Формализация поиска в ширину

Основными объектными структур информационных данных, применяемых в программе, являются:

  1. Матрица смежности GM.
  2. Формирование очереди quеuе.
  3. Формирование массива посещённых вершин (visitеd).

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

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

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

  1. Обнуление массива visitеd, то есть нет посещённых вершин графа.
  2. Выполняется выбор стартовой вершины s и её помещают в очередь в соответствующий массив.
  3. Выполняется исследование вершины s, она получает метку «посещённая», и все вершины, которые являются смежными с ней, перемещаются в хвост очереди, а вершина s подлежит удалению.
  4. Если окажется, что на этом шаге очередь уже нулевая, то выполнение алгоритма прекращается, в ином случае выполняется посещение вершины, стоящей первой в очереди, делается отметка о её посещении, а все её «потомственные» вершины ставятся в конец очереди.
  5. Пока есть возможность, производится выполнение пункта четыре.

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

Замечание 1

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

Пространственная и временная сложность

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

{\displaystyle O (\vert V\vert +\vert E\vert )}O(\vert V\vert +\vert E\vert)

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

{\displaystyle O (\vert V\vert +\vert E\vert )}O(\vert V\vert +\vert E\vert )

Полнота алгоритма

В случае, когда каждый узел имеет не бесконечное количество «потомков», то алгоритм будет считаться полным при условии:

  1. Существования решения и алгоритм поиска в ширину может его найти, не зависимо от конечности графа.
  2. Решение не существует, но если граф бесконечен, то поиск не будет завершён.

Если размеры рёбер графа одинаковые, то алгоритм поиска в ширину будет на уровне оптимального, так как гарантированно определит самый короткий маршрут.

Источник: https://spravochnick.ru/informatika/algoritmizaciya/algoritm_poiska_v_shirinu/

Поиск в ширину

Алгоритм поиска в ширину

Поиск в ширину (англ. breadth-first search, BFS) – один из алгоритмов обхода графа. Метод лежит в основе некоторых других алгоритмов близкой тематики.

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

Вершины просматриваются в порядке возрастания их расстояния от корня.

Пусть задан граф G=(V, E) и корень s, с которого начинается обход. После посещения узла s, следующими за ним будут посещены смежные с s узлы (множество смежных с s узлов обозначим как q; очевидно, что qV, то есть q – некоторое подмножество V).

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

Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения наличествующего условия.

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

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

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

Имеем смешанный граф (рис. 9.1) с |V| = 4 и |E| = 5. Выполним обход его вершин, используя алгоритм поиска в ширину. В качестве стартовой вершины возьмем узел 3.

Сначала он помечается серым как обнаруженный, а затем черным, поскольку обнаружены смежные с ним узлы (1 и 4), которые, в свою очередь, в указанном порядке помечаются серым.

Следующим в черный окрашивается узел 1, и находятся его соседи – узел 2, который становится серым. И, наконец, узлы 4 и 2, в данном порядке, просматриваются, обход в ширину завершается.

Рисунок 9.1 – Смешанный граф

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

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

Теперь перейдем к более формальному описанию алгоритма поиска в ширину. Основными объектами – тремя структурами данных, задействованными в программе, будут:

· матрица смежности графа GM;

· очередь queue;

· массив посещенных вершин visited.

Две первые структуры имеют целочисленный тип данных, последняя – логический. Посещенные вершины, заносятся в массив visited, что предотвратит зацикливание, а очередь queue будет хранить задействованные узлы. Напомним, что структура данных «очередь» работает по принципу «первый пришел – первый вышел». Рассмотрим разбитый на этапы процесс обхода графа:

1. массив visited обнуляется, т. е. ни одна вершина графа еще не была посещена;

2. в качестве стартовой, выбирается некоторая вершина s и помещается в очередь (в массив queue);

3. вершина s исследуется (помечается как посещенная), и все смежные с ней вершины помещаются в конец очереди, а сама она удаляется;

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

5. выполнять пункт 4, пока это возможно.

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

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

Код программы на C++:

const int n=4;

int i, j;

int GM[n][n] = //матрица смежности графа

{

{0, 1, 1, 0},

{0, 0, 1, 1},

{1, 0, 0, 1},

{0, 1, 0, 0}

};

void BFS(bool *visited, int unit) //поиск в ширину

{

int *queue=new int[n];

int count, head;

for (i=0; i

Источник: https://studopedia.ru/5_159662_poisk-v-shirinu.html

Cybern.ru » Обход в ширину

Алгоритм поиска в ширину

Обход в ширину (англ. Breadth-First Search, BFS) — один из основных не рекурсивных методов обхода вершин графа, позволяющий построить кратчайшие пути из начальной вершины (source vertex) обхода до всех остальных.

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

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

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

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

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

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

Для реализации алгоритма используется структура данных «очередь» (queue), которая работает по принципу FIFO (first-in, first-out). Это значит, что чем раньше очередная вершина была посещена, тем раньше будут просмотрены все ее еще не пройденные соседние вершины.
Исходный граф может быть как неориентированным, так и ориентированным, сути метода это не меняет.

Пошаговое представление

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

1 2 34 (для) всех вершин     //помечаем каждую вершину как не посещенную     //полагаем расстояние до каждой непомеченной вершины, равным бесконечности     //предок каждой непомеченной вершины равен -1

 
BFS(s)

1 2 3 4 5 6 7 8 9 10 11 12 13 1415     //кладем начальную вершину в очередь //помечаем вершину как посещенную //расстояние от вершины до самой себя равно 0 //пока очередь не пустая     //продолжаем обход из вершины , находящейся в «голове» очереди     //удаляем вершину в «голове» из очереди     (для) всех вершин //обрабатываем ребро       //если вершина является не посещенной, то добавляем ее в очередь         //помечаем вершину как посещенную         //помечаем предком вершины вершину         //обновляем расстояние от начальной вершины обхода до вершины        //кладем вершину в очередь

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

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

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

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

Дерево поиска в ширину

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

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

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

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

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

Дерево называется деревом поиска в ширину (breadth-first tree) для данного графа и данной начальной вершины. Заметим, что построенное дерево зависит от того, в каком порядке просматриваются вершины в списках смежных вершин.

Ребра исходного графа , которые входят в дерево поиска в ширину изображены на рисунке ниже жирной линией.

Реализации метода обхода в ширину

Источник: http://cybern.ru/obxod-v-shirinu.html

Реализация поиска в ширину¶

Алгоритм поиска в ширину

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

Поиск в ширину (BFS — от англ. breadth first search) — один из самых лёгких алгоритмов поиска в графе.

Так же он служит прототипом некоторых других важных алгоритмов, которые мы изучим позже.

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

Замечательной особенностью этого алгоритма является то, что он находит все вершины на расстоянии \(k\) от \(s\) до того, как начинает искать любую из вершин на расстоянии \(k+1\).

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

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

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

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

Алгоритм поиска в ширину показан ниже в листинге 2. Он использует представление графа в виде списка смежности, разработанное нами ранее. Дополнительно используется Queue — ключевой, как мы увидим, момент — чтобы решить, какую вершину исследовать следующей.

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

BFS начинается с вершины s и окрашивает start в серый, показывая, что она изучается в настоящий момент. Два других значения — расстояние и предшественник — инициализируются 0 и None соответственно. Наконец, start помещается в Queue.

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

Если он белый, то вершина неисследована, и произойдут следующие четыре вещи:

  1. Новая неисследованная вершина nbr окрашивается в серый.
  2. Предшественником nbr устанавливается текущий узел currentVert.
  3. Расстояние nbr устанавливается равным расстоянию currentVert + 1.
  4. nbr добавляется в конец очереди. Это эффективно планирует дальнейшее исследование узла, но не прежде, чем будут исследованы прочие вершины из списка смежности currentVert.

Листинг 2

from pythonds.graphs import Graph, Vertexfrom pythonds.basic import Queue def bfs(g,start): start.setDistance(0) start.setPred(None) vertQueue = Queue() vertQueue.enqueue(start) while (vertQueue.size() > 0): currentVert = vertQueue.dequeue() for nbr in currentVert.getConnections(): if (nbr.getColor() == 'white'): nbr.setColor('gray') nbr.setDistance(currentVert.getDistance() + 1) nbr.setPred(currentVert) vertQueue.enqueue(nbr) currentVert.setColor('black')

Теперь давайте посмотрим, как функция bfs конструирует дерево поиска в ширину относительно графа на рисунке 1. Начиная с “FOOL” мы берём все смежные с ним узлы и вставляем их в дерево. Такими узлами являются “POOL”, “FOIL”, “FOUL” и “COOL”. Так же каждый из них добавляется в очередь. Рисунок 3 показывает состояние дерева вместе с очередью после этого шага.

Рисунок 3: Первый шаг поиска в ширину.

На следующем шаге bfs из начала очереди удаляется очередной узел (“POOL”), и процесс повторяется для всех смежных с ним узлов. Однако, когда bfs проверяет узел “COOL”, она обнаруживает, что цвет этого узла уже был изменён на серый.

Это говорит о том, что существует более короткий путь в “COOL” и что этот узел уже находится в очереди для дальнейшего рассмотрения. Единственным добавленным в очередь узлом при исследовании “COOL” стал “POLL”.

Новое состояние очереди и дерева показано на рисунке 4.

Рисунок 4: Второй шаг поиска в ширину.

Следующая вершина в очереди — “FOIL”. Единственным узлом, который она вставит в дерево, станет “FAIL”. После того, как bfs продолжит обрабатывать очередь, ни один из следующих двух узлов ничего нового не добавит. Рисунок 5 показывает очередь и дерево после исследования всех вершин второго уровня.

Рисунок 5: Поиск в ширину после заполнения первого уровня.

Рисунок 6: Итоговое дерево поиска в ширину

Вы можете продолжить работать по алгоритму самостоятельно, пока не почувствуете уверенное знание того, как он работает. Рисунок 6 показывает итоговое дерево поиска в ширину после того, как все вершины из рисунка 3 будут исследованы.

Потрясающим моментом решения с помощью поиска в ширину является то, что мы решили не просто задачу “FOOL–SAGE”, с которой начинали, но и множество других. Теперь можно начать с любой вершины дерева поиска в ширину и, пройдя по стрелкам предшественников в обратном направлении (к корню), найти кратчайшую словесную лестницу от любого слова до “FOOL”.

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

Листинг 3

def traverse(y): x = y while (x.getPred()): print(x.getId()) x = x.getPred() print(x.getId()) traverse(g.getVertex('sage'))

Источник: https://aliev.me/runestone/Graphs/ImplementingBreadthFirstSearch.html

Алгоритмы поиска пути в графе

Алгоритм поиска в ширину

Продолжение публикации здесь (Алгоритмы поиска пути в графе. Часть 2)

Алгоритмы поиска пути чаще всего используют в играх, но бывает и такое infostart.ru/public/1081085, где автор применяет алгоритм поиска А* для нахождения коротких путей на складе.

Вот статья на тему реализации некоторых алгоритмов поиска, в частности А* (Перевод здесь). На платформе 1С 8.3 (далее просто 1С) реализация таких алгоритмов будет следующей:

&НаКлиенте Функция Граф_ПоискВШирину(ВершинаКуда) Очередь = Очередь_Новый(); Очередь_Добавить(Очередь, ВершинаКуда); ПосещенныеВершины = Новый Структура; ПосещенныеВершины.Вставить(ВершинаКуда, Новый Структура(«Вершина, Стрелка», «А»)); Пока Не Очередь_Пустой(Очередь) Цикл Вершина = Очередь_Получить(Очередь); Соседи = Граф_ПолучитьСоседейВершины(Вершина); Для каждого Сосед Из Соседи Цикл Если Не ПосещенныеВершины.Свойство(Сосед.Ключ) Тогда Очередь_Добавить(Очередь, Сосед.Ключ); ПосещенныеВершины.Вставить(Сосед.Ключ, Новый Структура(«Вершина, Стрелка», Вершина, Карта_ПолучитьСтрелкуРеверс(Сосед.Значение))); КонецЕсли; КонецЦикла; КонецЦикла; Возврат ПосещенныеВершины; КонецФункции  Поиск в ширину с ранним выходом &НаКлиенте Функция Граф_ПоискВШиринуСРаннимВыходом(ВершинаКуда, ВершинаОткуда) Очередь = Очередь_Новый(); Очередь_Добавить(Очередь, ВершинаКуда); ПосещенныеВершины = Новый Структура; ПосещенныеВершины.Вставить(ВершинаКуда, Новый Структура(«Вершина, Стрелка», «А»)); Пока Не Очередь_Пустой(Очередь) Цикл Вершина = Очередь_Получить(Очередь); Если Вершина = ВершинаОткуда Тогда Прервать; КонецЕсли; Соседи = Граф_ПолучитьСоседейВершины(Вершина); Для каждого Сосед Из Соседи Цикл Если Не ПосещенныеВершины.Свойство(Сосед.Ключ) Тогда Очередь_Добавить(Очередь, Сосед.Ключ); ПосещенныеВершины.Вставить(Сосед.Ключ, Новый Структура(«Вершина, Стрелка», Вершина, Карта_ПолучитьСтрелкуРеверс(Сосед.Значение))); КонецЕсли; КонецЦикла; КонецЦикла; Возврат ПосещенныеВершины; КонецФункции &НаКлиенте Функция Граф_ЖадныйПоиск(ВершинаКуда, ВершинаОткуда) ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый(); ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, ВершинаКуда, 0); ВершиныОткуда = Новый Структура(ВершинаКуда, Новый Структура(«Вершина, Стрелка», «А»)); ВершинаЦель = Граф[ВершинаОткуда]; Пока Не ПриоритетнаяОчередь_Пустой(ПриоритетнаяОчередь) Цикл Вершина = ПриоритетнаяОчередь_Получить(ПриоритетнаяОчередь); Если Вершина = ВершинаОткуда Тогда Прервать; КонецЕсли; Соседи = Граф_ПолучитьСоседейВершины(Вершина); Для каждого Сосед Из Соседи Цикл Если Не ВершиныОткуда.Свойство(Сосед.Ключ) Тогда Приоритет = Граф_ПолучитьРасстояние(Граф[Сосед.Ключ], ВершинаЦель); ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, Сосед.Ключ, Приоритет); ВершиныОткуда.Вставить(Сосед.Ключ, Новый Структура(«Вершина, Стрелка», Вершина, Карта_ПолучитьСтрелкуРеверс(Сосед.Значение))); КонецЕсли; КонецЦикла; КонецЦикла; Возврат ВершиныОткуда; КонецФункции &НаКлиенте Функция Граф_АлгоритмДейкстры(ВершинаКуда, ВершинаОткуда) ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый(); ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, ВершинаКуда, 0); Дистанция = Новый Структура(ВершинаКуда, Новый Структура(«Вершина, Стрелка», «А»)); СтоимостьДвижения = Новый Структура(ВершинаКуда, 0); Пока Не ПриоритетнаяОчередь_Пустой(ПриоритетнаяОчередь) Цикл Вершина = ПриоритетнаяОчередь_Получить(ПриоритетнаяОчередь); Если Вершина = ВершинаОткуда Тогда Прервать; КонецЕсли; Соседи = Граф_ПолучитьСоседейВершины(Вершина); Для каждого Сосед Из Соседи Цикл НоваяСтоимость = СтоимостьДвижения[Вершина] + Граф_ПолучитьСтоимость(Вершина); ПрежняяСтоимость = Неопределено; Если Не СтоимостьДвижения.Свойство(Сосед.Ключ, ПрежняяСтоимость) Или НоваяСтоимость < ПрежняяСтоимость Тогда СтоимостьДвижения.Вставить(Сосед.Ключ, НоваяСтоимость); Приоритет = НоваяСтоимость; ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, Сосед.Ключ, Приоритет); Дистанция.Вставить(Сосед.Ключ, Новый Структура("Вершина, Стрелка", Вершина, Карта_ПолучитьСтрелкуРеверс(Сосед.Значение))); КонецЕсли; КонецЦикла; КонецЦикла; Возврат Дистанция; КонецФункции &НаКлиенте Функция Граф_АлгоритмА(ВершинаКуда, ВершинаОткуда) ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый(); ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, ВершинаКуда, 0); ВершиныОткуда = Новый Структура(ВершинаКуда, Новый Структура("Вершина, Стрелка", "А")); СтоимостьДвижения = Новый Структура(ВершинаКуда, 0); ВершинаЦель = Граф[ВершинаОткуда]; Пока Не ПриоритетнаяОчередь_Пустой(ПриоритетнаяОчередь) Цикл Вершина = ПриоритетнаяОчередь_Получить(ПриоритетнаяОчередь); Если Вершина = ВершинаОткуда Тогда Прервать; КонецЕсли; Соседи = Граф_ПолучитьСоседейВершины(Вершина); Для каждого Сосед Из Соседи Цикл НоваяСтоимость = СтоимостьДвижения[Вершина] + Граф_ПолучитьСтоимость(Сосед.Ключ); ПрежняяСтоимость = Неопределено; Если Не СтоимостьДвижения.Свойство(Сосед.Ключ, ПрежняяСтоимость) Или НоваяСтоимость < ПрежняяСтоимость Тогда СтоимостьДвижения.Вставить(Сосед.Ключ, НоваяСтоимость); Приоритет = НоваяСтоимость + Граф_ПолучитьРасстояние(Граф[Сосед.Ключ], ВершинаЦель); ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, Сосед.Ключ, Приоритет); ВершиныОткуда.Вставить(Сосед.Ключ, Новый Структура("Вершина, Стрелка", Вершина, Карта_ПолучитьСтрелкуРеверс(Сосед.Значение))); КонецЕсли; КонецЦикла; КонецЦикла; Возврат ВершиныОткуда; КонецФункции

Как могли заметить во всех алгоритмах используется абстактная структура данных Очередь, либо Приоритетная очередь. Как реализовать их в 1С можно почитать тут.

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

Теоретические описания алгоритмов приводить не буду. Выделю главные, на мой взгляд, моменты:

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

Жадный поиск использует расстояние до цели как критерий выбора следующей вершины.

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

Алгоритм А* использует такие понятия как стоимость перемещения и расстояние до цели (на самом деле эвристика может быть другой). Т.е. это жадный поиск и алгоритм дейкстры в одном.

Для наглядности сделал обработку, которая выглядит так:

Пример работы алгоритма А*:

Обработка сделана средствами платформы 1С 8.3.10 без использования внешних компонент. Карта, на которой отображается путь интерактивна т.е. можно мышкой переносить точки А и Б, ставить(убирать) стену, лес. Для алгоритмов А* и Дейкстры стоимость пути по лесу равна 3 единицам, по пустой ячейке 1.

Еще есть сайт где наглядно можно посмотреть и другие алгоритмы поиска пути.

UPD: Добавил волновой алгоритм

Волновой алгоритм визуально будет выглядеть как поиск в ширину с ранним выходом, только вместо стрелок будут указаны номера итерации (номера волн). А вот реализация будет отличаться, потому как на выходе получаем карту с волнами и по ней строим путь, выбирая соседа с наименьшим номером волны. Пока не дойдем до 0.

 Волновой алгоритм — распространение волны &НаКлиенте Функция Граф_ВолновойАлгоритм_РаспространениеВолны(ВершинаКуда, ВершинаОткуда) Очередь = Очередь_Новый(); Очередь_Добавить(Очередь, ВершинаКуда); ПосещенныеВершины = Новый Структура; ПосещенныеВершины.Вставить(ВершинаКуда, 0); // В значении храним номер волны Пока Не Очередь_Пустой(Очередь) Цикл Вершина = Очередь_Получить(Очередь); Если Вершина = ВершинаОткуда Тогда Прервать; КонецЕсли; НомерВолны = ПосещенныеВершины[Вершина]; Соседи = Граф_ПолучитьСоседейВершины(Вершина); Для каждого Сосед Из Соседи Цикл Если Не ПосещенныеВершины.Свойство(Сосед.Ключ) Тогда Очередь_Добавить(Очередь, Сосед.Ключ); ПосещенныеВершины.Вставить(Сосед.Ключ, НомерВолны + 1); КонецЕсли; КонецЦикла; КонецЦикла; Возврат ПосещенныеВершины; КонецФункции  Волновой алгорити — восстановление пути &НаКлиенте Функция Граф_ВолновойАлгоритм_ВосстановлениеПути(ПосещенныеВершины, ВершинаОткуда) НомерВолны = Неопределено; Путь = Новый Массив; ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый(); ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, ВершинаОткуда, 0); Пока Не ПриоритетнаяОчередь_Пустой(ПриоритетнаяОчередь) Цикл Вершина = ПриоритетнаяОчередь_ПолучитьБезУдаления(ПриоритетнаяОчередь); Путь.Добавить(Вершина); Если ПосещенныеВершины.Свойство(Вершина, НомерВолны) И НомерВолны = 0 Тогда // Достигли цели Прервать; КонецЕсли; ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый(); Соседи = Граф_ПолучитьСоседейВершины(Вершина); Для каждого Сосед Из Соседи Цикл Если ПосещенныеВершины.Свойство(Сосед.Ключ, НомерВолны) Тогда ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, Сосед.Ключ, НомерВолны); КонецЕсли; КонецЦикла; КонецЦикла; Возврат Путь; КонецФункции

ПС: поскольку обработка выполнена в стиле автоматного программирования, то к ней идет спецификация, состоящая из схем связей и графов перехода (диаграмм состояний).

Для полного тестирования требовалось лишь проверить поведение во всех состояниях по графу перехода. Тестирование проводилось интерактивно, для этого в обработке есть кнопка «Показать протокол тестирования».

 Список литературы по автоматному программированию и конечным автоматам:

[1] — http://is.ifmo.ru/books/_book.pdf — Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб 2008. 

[2] — http://is.ifmo.ru/automata/

[3] — http://softcraft.ru/auto/

Источник: https://infostart.ru/public/1088569/

Booksm
Добавить комментарий