Есть ли способ сохранить приоритеты направления в *? (т.е. создание того же самого пути, что и ширина)

Ответ 1

Я придумал два способа сделать это. Оба требуют продолжения алгоритма, в то время как верхняя часть очереди имеет расстояние до начала g-value <= g (end- node). Поскольку эвристика, используемая в *, допустима, это гарантирует, что каждый node, принадлежащий к некоторому лучшему пути, в конечном итоге будет расширен.

Первый метод заключается в том, что когда мы приходим к конфликту (т.е. находим два узла с тем же f-значением, которые потенциально могут быть родителями некоторого node вдоль наилучшего пути), мы разрешаем его возвращаясь к первой точке вдоль пути, с которым они встречаются (мы можем сделать это легко в O(path-length)). Затем мы просто проверяем приоритеты направления обоих путей и переходим к тому, какой путь имеет более высокий приоритет в BFS-поиске.

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

Мы делаем это, сохраняя наилучший путь до сих пор для каждого node. Обычно это было бы громоздким, но поскольку у нас есть 4-связный граф, мы можем сделать это довольно эффективно, сохраняя каждое направление по пути. Это займет всего 2 бита за node. Таким образом, мы можем по существу кодировать путь с помощью целых чисел - с 32-битными регистрами мы можем сравнивать по 16 узлов за раз; 32 узла с 64-битными регистрами; и 64 (!) узлов с 128-разрядными регистрами (например, регистры SSE в процессорах x86 и x64), что делает этот поиск очень недорогим даже для путей со 100 узлами.

Я реализовал оба эти метода вместе с алгоритмом @generic для проверки скорости. На сетке 50x50 с 400 башнями,

• @generic человеческий алгоритм работал примерно на 120% медленнее, чем обычно A *
• мой алгоритм обратного отслеживания работал примерно на 55% медленнее, чем обычно A *
• Алгоритм целочисленного кодирования работает только на 10% медленнее, чем A *

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

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

Ответ 2

Если исходный алгоритм был BFS, вы ищете наименьший из кратчайших путей, где "наименьший" соответствует лексикографическому порядку, вызванному некоторым общим порядком Ord по краям (и, конечно, "кратчайший" соответствует к длине пути).

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

К счастью, это все еще можно сделать с помощью двух простых и недорогих модификаций для A *:

• Как только мы достигнем цели, вместо того, чтобы возвращать произвольный самый короткий путь к цели, мы должны продолжать посещать узлы до тех пор, пока длина пути не увеличится, поэтому мы посетим все узлы, принадлежащие кратчайшему пути.
• При восстановлении пути мы создаем набор узлов, которые вносят вклад в кратчайшие пути. Этот набор имеет структуру DAG при рассмотрении всех кратчайших границ пути, и теперь легко найти наименьший путь лексикографии от start до goal в этой DAG, что является желательным решением.

Схематически классический A *:

path_length = infinity for every node
path_length[start] = 0

while score(goal) > minimal score of unvisited nodes:
    x := any unvisited node with minimal score
    mark x as visited
    for y in unvisited neighbors of x:
        path_length_through_x = path_length[x] + d(x,y)
        if path_length[y] > path_length_through_x:
            path_length[y] = path_length_through_x
            ancestor[y] = x

return [..., ancestor[ancestor[goal]], ancestor[goal], goal]

где score(x) означает path_length[x] + heuristic(x, goal).

Мы просто превратим строгое неравенство цикла while в нестрогий и добавим фазу восстановления пути:

path_length = infinity for every node
path_length[start] = 0

while score(goal) >= minimal score of unvisited nodes:
    x := any unvisited node with minimal score
    mark x as visited
    for y in unvisited neighbors of x:
        path_length_through_x = path_length[x] + d(x,y)
        if path_length[y] > path_length_through_x:
            path_length[y] = path_length_through_x

optimal_nodes = [goal]
for every x in optimal_nodes:  // note: we dynamically add nodes in the loop
    for y in neighbors of x not in optimal_nodes:
        if path_length[x] == path_length[y] + d(x,y):
            add y to optimal_nodes

path = [start]
x = start
while x != goal:
    z = undefined
    for y in neighbors of x that are in optimal_nodes:
        if path_length[y] == path_length[x] + d(x,y):
            z = y if (x,y) is smaller than (x,z) according to Ord
    x = z
    append x to path

return path

Предупреждение: процитировать Кнута, я только доказал это правильно, не пробовал.

Что касается влияния производительности, оно должно быть минимальным: цикл поиска посещает узлы со счетом, который на 1 единицу выше классического A *, а фаза восстановления является квазилинейной по числу узлов, принадлежащих кратчайший путь. Влияние меньше, если, как вы подразумеваете, в большинстве случаев есть только один самый короткий путь. Вы можете даже оптимизировать этот специальный случай, например. вспомнив ancestor node, как в классическом случае, который вы установили для специального значения ошибки, когда имеется более одного предка (то есть, когда path_length[y] == path_length_through_x). Когда цикл поиска закончен, вы пытаетесь получить путь через ancestor, как в классическом A *; вам нужно всего лишь выполнить полную реконструкцию пути, если при построении пути возникло значение ошибки.

Ответ 3

i построил бы предпочтение по порядку пути непосредственно в эвристической функции

Сначала я бы посмотрел первый алгоритм хлеба

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

рассмотрим, что мы запускаем алгоритм глубины и на n-й глубине ранее сделанные решения по алгоритму: x_i\in {U, R, D, L} обозначим U = 0, R = 1, D = 2, L = 3

затем определите:

g(x_1,..,x_n) = sum_{i=1}^n x_i * (1/4)^i

исправьте этот шаг g как g ' на каждом шаге, когда алгоритм видит более глубокий node, чем этот, функция g() будет больше.

на каждом следующем шаге, когда изменяется значение {1..n} x_i, будет больше, поэтому верно, что g-функция всегда поднимается во время выполнения первой-первой.

обратите внимание: если алгоритм глубины-первого успешный, он выбирает путь с минимальным значением g()

Примечание: g() < 1 beacuse max (L, R, U, D) = 3

добавление g к эвристической функции A * не будет мешать кратчайшей длине пути, так как длина минимального края >= 1

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

для примера:

h_bread=g(DLLLU) = (23330)_4 * c
h_astar=g(LULLD) = (30332)_4 * c

() _ 4 - base4 с - постоянная (4 ^ {- 5})

для примера: h_bread < h_astar

Ответ 4

В общем, нет нетривиального способа сделать это:

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

Пример: если узлы рассматриваются в порядке A, B, C, то Node A < Node C. Таким образом, если существует связь между кратчайшим путем, начинающимся с A и одним, начинающимся с C, то найдена с A.

С другой стороны, поиск A * найдет кратчайший путь младшего порядка, определяемый эвристическим значением node. Таким образом, эвристика должна учитывать самый низкий лексикографический путь к каждому node. И единственный способ найти это BFS.