Алгоритм поиска графа

Question

Я ищу алгоритм графа с некоторыми необычными свойствами.

Каждое ребро на графике представляет собой либо «верхний» край, либо «нижний» край.

Допустимый путь может содержать неопределенное число «вверх», за которым следует неопределенное количество «вниз», или наоборот. Однако он не может изменить направление более одного раза.

Например, правильный путь может быть «до» B «до» C «вниз» Е «вниз» F неверный путь может быть «до» B «вниз» C «до» D

Что такое хороший алгоритм для нахождения кратчайшего допустимого пути между двумя узлами? Как найти все кратчайшие пути равной длины?

Answer 1

Предполагая, что у вас нет эвристики, достаточно выбрать вариант dijkstra's algorithm. Каждый раз, когда вы рассматриваете новый край, храните информацию о своих «предках». Затем проверьте инвариант (только одно изменение направления) и откат, если он нарушен.

Предки здесь - все ребра, которые были пройдены, чтобы добраться до текущего узла по кратчайшему пути. Один хороший способ сохранить информацию о предках будет представлять собой пару чисел. Если U вверх, а D - вниз, предки конкретного края могут быть UUUDDDD, которые будут парой 3, 4. Из-за инварианта вам не понадобится третье число.

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

Answer 2

Возможно, вы можете преобразовать свой граф в нормальный направленный граф, а затем использовать существующие алгоритмы.

Одним из способов было бы разделение графика на два графика: один со всеми краями вверх и один со всеми вниз ребрами и с направленными ребрами между всеми узлами на графе один и соответствующим узлом на графике два.

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

Answer 3

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

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

Answer 4

A* со специальной производительностью (оценка G) и эвристической функцией (H score) могут справиться с этим.

За эту стоимость вы можете отслеживать количество изменений направления в пути и добавлять бесконечную стоимость при втором изменении (т. Е. Отключить поиск этих ветвей).

Эвристика требует больше внимания, особенно если вы хотите сохранить эвристику допустимой (никогда не переоценивайте минимальное расстояние до цели) и монотонную. (Только способ гарантировать, что A * находит оптимальное решение.)

Возможно, у вас есть информация о домене, созданный для создания эвристики? (т. е. x, y координаты узлов на графике?)

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

Answer 5

Если у вас есть стандартная функция поиска на графе, скажем Graph.shortest(from, to) в библиотеке, вы можете петлю и свести к минимуму, в C#/псевдокоде:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min) 

Если вам нужно помнить, минимальный путь/пути и это так случается, что ваша стандартная функция возвращает вам данные, вы также можете произносить

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)] 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin) 

где myMin должен сравнить два [fst, nxt, C, AC, BD] кортежей и оставить тот, который имеет более низкое расстояние, или оба, и предполагая reduce - это умная функция.

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