C言語関係掲示板

過去ログ

No.288.迷路の最短経路

[戻る] [ホームページ]

No.1729

教えてください!
投稿者---ひろ(2002/06/16 23:37:05)


迷路をとくプログラムをつくっているのですが、最短経路を求めるやり方がわからないんです。ソースファイルと実行結果を添付しますので、教えてください!

*****ソースファイル*****
#include <stdio.h>

int m[7][7] = {{2,2,2,2,2,2,2},
{2,0,0,0,0,0,2},
{2,0,2,0,2,0,2},
{2,0,0,2,0,2,2},
{2,2,0,2,0,2,2},
{2,0,0,0,0,0,2},
{2,2,2,2,2,2,2}};

int Si,Sj,Gi,Gj,goal,sp,ri[100],rj[100];

int main(void)
{
int visit(int,int);

int o,p;

printf("maze\n\n");

for(o=0;o<7;o++){
for(p=0;p<7;p++)
printf("%d ",m[o][p]);
puts("");


}

puts("");

sp=0;
goal=0;
Si=Sj=1;
Gi=Gj=5;

if(visit(Si,Sj)==0)
printf("Could't find Goal\n");

}

int visit(int i,int j)
{
int k;

m[i][j]=1;

ri[sp]=i;
rj[sp]=j;

sp++;

if(i==Gi && j==Gj) {puts(""); puts(""); puts("saitan");
for(k=0; k<sp; k++) printf("(%d,%d) ",ri[k],rj[k]);

goal=1;
}

if(goal != 1 && m[i][j+1]==0) {printf("(%d,%d) ",i,j); visit(i,j+1);}

if(goal != 1 && m[i+1][j]==0) {printf("(%d,%d) ",i,j); visit(i+1,j);}

if(goal != 1 && m[i][j-1]==0) {printf("(%d,%d) ",i,j); visit(i,j-1);}

if(goal != 1 && m[i-1][j]==0) {printf("(%d,%d) ",i,j); visit(i-1,j);}

if(goal != 1 && (m[i][j]==1 || m[i][j]==2))
printf("(%d,%d) ",i,j);

sp--;

return goal;

}
**********

*****実行結果*****
maze

2 2 2 2 2 2 2
2 0 0 0 0 0 2
2 0 2 0 2 0 2
2 0 0 2 0 2 2
2 2 0 2 0 2 2
2 0 0 0 0 0 2
2 2 2 2 2 2 2

(1,1) (1,2) (1,3) (1,4) (1,5) (2,5) (1,5) (1,4) (1,3) (2,3) (1,3)
(1,2) (1,1) (2,1) (3,1) (3,2) (4,2) (5,2) (5,3) (5,4)

saitan
(1,1) (2,1) (3,1) (3,2) (4,2) (5,2) (5,3) (5,4) (5,5)
**********

この場合はうまくいっているように見えます。でも、例えば迷路を

2 2 2 2 2 2 2
2 0 0 0 0 0 2
2 0 2 0 2 0 2
2 0 2 0 2 0 2
2 0 2 0 2 0 2
2 0 0 0 0 0 2
2 2 2 2 2 2 2

のように変えて、ゴールを(3,3)にしたりすると、このプログラムでは、最短経路を求めることができません。
長くなってすいません!よろしくお願いします!

No.1730

Re:教えてください!(迷路の最短経路)
投稿者---kikk(2002/06/17 01:13:08)


ども。


迷路を解く方法はいろいろ考えられますが、最短経路はダイクストラ法
くらいしかないので、これを適用するのがよいかと。ただしダイクストラ法
のデータ構造は節点と道からなっているので、現在の形式から変換する必要
があります。具体的には迷路の座標を節点とみなし、隣り合っている行ける
方向(座標)への距離は1、行けない方向と隣り合っていない座標への距離を
無限大(十分大きな値)とします。

迷路データの保持を、現在の座標方式から、ダイクストラ法の方式に変換
するルーチンをつくるといいと思います。元が迷路なので、ダイクストラ法
のデータ構造で最初から打ち込むといろいろ苦労しそうなので。。

あ、ダイクストラ法の具体的なアルゴリズムは検索すればすぐにでてくると
思います(たぶんコードつき)。


では。

p.s.
http://www9.plala.or.jp/sgwr-t/c_sub/bbs.html
も御覧になって下さいませ。