Как рассчитать кратчайший путь между двумя точками в сетке

Ответ 1

Алгоритм Ли: http://en.wikipedia.org/wiki/Lee_algorithm

В основном это поиск BF, вот пример: http://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf

Чтобы эффективно реализовать его, проверьте мой ответ здесь: Измените FloodFill-Algorithm, чтобы получить территорию Вороного для двух точек данных? - когда я говорю "отметка", вы отмечаете ее число, на которое вы пришли с + 1.

Например, если у вас есть эта сетка, где * = препятствие, и вы можете перемещаться вверх, вниз, влево и вправо, и вы начинаете с S и должны перейти к D, а 0 = свободная позиция:

S 0 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

Вы помещаете S в свою очередь, затем "расширяете" его:

S 1 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

Затем разверните все его соседи:

S 1 2 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

И все соседние соседи:

S 1 2 3
* * 3 *
* 0 0 *
0 0 * *
* 0 0 D

И так далее, в конце вы получите:

S 1 2 3
* * 3 *
* 5 4 *
7 6 * *
* 7 8 9

Таким образом, расстояние от S до D равно 9. Время работы - O (NM), где N = количество строк и M = количество столбцов. Я думаю, что это самый простой алгоритм для реализации на сетках, и он также очень эффективен на практике. Это должно быть быстрее, чем классический dijkstra, хотя dijkstra может выиграть, если вы реализуете его с помощью куч.

Ответ 2

Используйте алгоритм A Star (A *).

Ответ 3

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

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

Следовательно, вы можете легко интерпретировать свою сетку как график (тогда ограничения, такие как диагонали, могут быть учтены) и запустить поиск Dijkstra для кратчайшего пути от A до B. Это действительно вопрос моделирования вашей проблемы, а не того, что вам нужен какой-то фантастический алгоритм.

Ответ 4

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

Ответ 5

Что я не понимаю, если вам нужен самый короткий путь между A и B, вам все равно нужно смотреть на A-C и A-D, если C и D указывают на B? Ваш самый короткий путь вполне может быть A-C-B или A-D-B. Вам просто нужно выкинуть несвязанные узлы. В одном из моих проектов я взял точки A и B, проверил, какие другие точки были связаны, а те, которые не были удалены со всего графика. Затем я продолжил использование алгоритма Дейкстры.

Ответ 6

Здесь выполняется реализация кратчайшего пути на основе python в матрице от (0,0) до (0, m-1) с использованием BFS. Вы можете изменить его для соответствия переменным точкам.

n,m,k1,k2=[int(i) for i in input().split()]
arr=[[int(j) for j in input().split()] for i in range(n)]
x=[[-1 for i in range(m)] for j in range(n)]
x[0][0]=0
vis={}
q=[(0,0)]
while len(q)!=0:
    curr=q[0]
    rem=q.pop(0)
    vis[curr]=True
    r=curr[0]
    c=curr[1]
    if r-1>=0 and arr[r-1][c]==0:
        if vis.get((r-1,c),-1)==-1 or vis[(r-1,c)]!=True:
            q.append((r-1,c))
            x[r-1][c]=x[r][c]+1
    if r+1<n and arr[r+1][c]==0:
        if vis.get((r+1,c),-1)==-1 or vis[(r+1,c)]!=True:
            q.append((r+1,c))
            x[r+1][c]=x[r][c]+1
    if c-1>=0 and arr[r][c-1]==0:
        if vis.get((r,c-1),-1)==-1 or vis[(r,c-1)]!=True:
            q.append((r,c-1))
            x[r][c-1]=x[r][c]+1
    if c+1<m and arr[r][c+1]==0:
        if vis.get((r,c+1),-1)==-1 or vis[(r,c+1)]!=True:
            q.append((r,c+1))
            x[r][c+1]=x[r][c]+1
    #for i in x:
        #print(i)
ans=x[0][m-1]
if ans==-1:
    print(-1)
else:
    print(ans)

• входная матрица должна состоять из 0 и 1. 0 для возможного перемещения.
• n - количество строк.
• m - количество столбцов.
• arr - заданная матрица.
• x - матрица расстояний от (0,0).
• vis - словарь, предоставляющий логическое значение, если посетитель посещает node.
• вывод -1 показывает, что такого пути нет.

Ответ 7

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

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

Изменить: я просмотрел ответ, который вы разместили, но я не уверен, что этот код должен/делать. Например, он имеет: if(y>=0) max(abs(x),y);. Это не кажется (по крайней мере для меня), чтобы иметь смысл - результат от max просто выброшен. Чтобы выполнить что-то полезное, оно должно быть возвращено или назначено или что-то в этом порядке. Как бы то ни было, самое лучшее, на что вы можете надеяться, это то, что компилятор видит это как мертвый код и ничего не генерирует для него.

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

Ответ 8

использовать алгоритм A * для нахождения пути между двумя точками в 2D сетке. http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html