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

Question

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

Эвристика требует дополнительных размышлений, особенно если вы хотите сохранить эвристику допустимой (никогда не переоценивайте минимальное расстояние до цели) и монотонной.(Единственный способ гарантировать, что 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)

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

[ [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 это умная функция.

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