12

グリッドを表すポイントのコレクションがあります。ポイントAとBの間の距離を最短にするアルゴリズムを探しています。任意のポイント（AとBを除く）のキャッチは、パスを妨げる障害物になる可能性があります。したがって、迂回する必要があります。パスは対角線上を移動できない場合があります。

このタイプの問題を解決しようとしている他の人にとって、私はこれらの参照が非常に役立つことに気づきました。

http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html

http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29#chunk%20def:visit%20each%20vertex%20u,%20always%20visiting%20vertex%20with%20smallest%20minDistance%20first

4

2 に答える 2

24

これは、障害物が存在する場合でもポイント間の最適なパスを非常に迅速に見つけるヒューリスティック検索アルゴリズムであるA*検索アルゴリズムを使用するのに最適なスポットです。グリッドをグラフに変換するという考え方です。このグラフでは、グリッド内の各セルがノードであり、互いに遮られていない2つの隣接するセルの間にエッジがあります。このグラフができたら、探している答えは、開始ノードから宛先ノードまでのグラフ内の最短経路です。

A *を使用するには、グリッド上の任意のポイントから目的の正方形までの距離を「推測」するヒューリスティック関数が必要です。このための優れたヒューリスティックの1つは、2点間のマンハッタン距離を使用することです。

最短経路を見つけるためのより簡単でありながら非常に効率的なアルゴリズムを探している場合は、A*のより単純なバージョンと考えることができるダイクストラのアルゴリズムを調べることを検討してください。A *よりも少し遅いですが、それでも非常に高速に実行され、最適な回答が保証されます。

お役に立てれば！

于 2011-03-14T19:40:51.207 に答える
6

これは、幅優先探索を使用して解決できる単純な問題です。

 /**
  * computing distance of each cell from the starting cell 
  * avoiding obstacles, 0 represents obstacle 1 represents non obstacle
  * we can take only one step x-1;x+1;y-1;y+1
 */

#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;

class XY
{
 public :
 int x;
int y;
};

int main()
{
int grid[8][8] = {
    {1,1,1,1,1,1,1,1},
    {1,0,0,0,1,1,1,1},
    {1,1,0,0,1,1,1,1},
    {1,1,0,0,1,1,1,1},
    {1,1,1,2,0,1,0,0},
    {1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1}
};


int rows = 8;
int cols = 8;

int distance[rows][cols];

for(int m = 0;m<rows;m++)
{
    for(int n =0;n<cols;n++)
    {
        distance[m][n] = -1;
    }
}

queue<XY> iterator;


XY xy;
xy.x = 0;
xy.y = 0;
distance[0][0] = 0;
iterator.push(xy);

while(!iterator.empty())
{
    xy = iterator.front();
    iterator.pop();
    //printf("popped %d+%d\n",xy.x ,xy.y);
    for(int p = -1;p<2;p++)
    {
        for(int q = -1;q<2;q++)
        {
            if(p == q)continue;
            int i = xy.x + p;
            int j = xy.y + q;

            if(i<0)i=0;
            if(j<0)j=0;
            if(i>rows-1)i=rows-1;
            if(j>cols-1)j=cols-1;

            if(i== xy.x && j == xy.y)continue;

    //              printf("i,j = %d,%d\n",i,j);

            if(distance[i][j] == -1)
            {
     //                 printf("******\n");
                if(grid[i][j] != 0)
                {
     //                 printf("assigned distance %d to %d+%d\n",distance[xy.x][xy.y] + 1,i,i); 
                distance[i][j] = distance[xy.x][xy.y] + 1;
                XY xyn;
                xyn.x = i;
                xyn.y = j;  
                iterator.push(xyn);
      //                    printf("pushed %d+%d\n",xyn.x,xyn.y);
                }
            }

        }
    }
}

for(int x = 0;x<rows;x++)
{
    for(int y =0;y<cols;y++)
    {
        printf("%d ",distance[x][y]);   
    }
    printf("\n");
}
return 0;
}
于 2014-11-24T19:18:14.377 に答える