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

Question

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

Каждое ребро на графике является либо ребром "вверх", либо ребром "вниз".

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

Например, допустимый путь может быть A "вверх" B "вверх" C "вниз" E "вниз" F неверный путь может быть A "вверх" B "вниз" C "вверх" D

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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.