ダイクストラ法について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
閉鎖
HamachiOnsen
記事: 7
登録日時: 14年前

ダイクストラ法について

#1

投稿記事 by HamachiOnsen » 14年前

　初めまして、HamachiOnsen（はまち温泉）といいます。
いきなりですが、最近二角取り(四川省)をC言語を用いて作っています。
しかし、牌と牌の最短経路を算出するのにダイクストラ法を用いたところうまく動きません。

　ある程度まで答えを求めてくれているようなのですが、答えをすべて出す前に終了してしまっているようです。
その結果、二角取りの二回まで曲がれる、という部分を調べる部分で答えが出ていないため
最終的にアクセス違反が起こり、プログラムが強制終了してしまいます。

　具体的なコードは以下のような感じです。

コード: 

#define X_SIZE 20
#define Y _SIZE 13
#define MAX_SIZE (X_SIZE * Y_SIZE)
#define WALL 9

int dn[4] = { -20, 1, 20, -1 };
int visit[MAX_SIZE], cost[MAX_SIZE], prev[MAX_SIZE];
/*
    data[MAX_SIZE].stage = {
         9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
         9,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,9,
         9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9
    };
*/
void Search(int start)
{
	int i,min,next,dist;

	cost[start] = 0;
	prev[start] = start;

	do{
		min = MAX_VALUE;
		next = -1;
		visit[start] = TRUE;

		//頂点選択
		for( i = 0; i < 4; i++ ){
			if( visit[ start + dn[i] ] != FALSE || data[ start + dn[i] ].stage == WALL ) continue;
			dist = cost[start] + data[ start + dn[i] ].stage;
			if( cost[ start + dn[i] ] >= dist ){
				cost[ start + dn[i] ] = dist;
				prev[ start + dn[i] ] = start;
			}
			if( cost[ start + dn[i] ] < min ){
				min = cost[ start + dn[i] ];
				next = start + dn[i];
			}
		}
		//ここまで

		start = next;
	}while( start != -1 );

	return;
}
使用環境としては
　Windows7 32bit
VisualStudio2010 Professional

どなたかご助言いただけると助かります。というか助けてくださいお願いします。（TДT）
ページトップ
初級者
記事: 200
登録日時: 14年前

Re: ダイクストラ法について

#2

投稿記事 by 初級者 » 14年前

助言は、そうですねぇ、

まずは、コードにコメントを付けてみましょう

かな。
ページトップ
HamachiOnsen
記事: 7
登録日時: 14年前

Re: ダイクストラ法について

#3

投稿記事 by HamachiOnsen » 14年前

　すみません、コードを貼った時点で満足してしまいました。（；＝＝）
普段自分でしか見ないものですから、コメントも読みにくいかもしれませんが、このような感じでいいでしょうか；
不手際が多くてすみません、改めてご助言いただけると幸いです。

よろしくお願いします。

コード: 

#define X_SIZE 20					//X軸の最大サイズ
#define Y _SIZE 13					//Y軸の最大サイズ
#define MAX_SIZE (X_SIZE * Y_SIZE)	//最大サイズ
#define WALL 9						//壁
 
//移動変位配列,UP,RIGHT,DOWN,LEFT
int dn[4] = { -20, 1, 20, -1 };
//　確定済みかを格納, 　移動コスト,    現在頂点の一つ前を格納
int visit[MAX_SIZE], cost[MAX_SIZE], prev[MAX_SIZE];

/*　移動コストの配列　　// 9 = 壁, 5 = 牌, 1 = 空き
    data[MAX_SIZE].stage = {
         9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
         9,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
         9,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,9,
         9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9
    };
*/
 
//ダイクストラによる探索
void Search(int start)
{
    int i,min,next,dist;
 
	//スタート地点のコストを0,prevに現在値を設定
    cost[start] = 0;
    prev[start] = start;
 
    do{
        min = MAX_VALUE;
        next = -1;
        visit[start] = TRUE;	//現在地を確定する。
 
        //--------頂点選択------------
 
		//移動先0～3,0ならば上,1ならば右,2ならば下,3ならば左
        for( i = 0; i < 4; i++ ){
			//確定済みか、あるいは移動先が壁ならばコンティニュー
            if( visit[ start + dn[i] ] != FALSE || data[ start + dn[i] ].stage == WALL ) continue;
			//スタート地点から移動先までへのコストを格納
            dist = cost[start] + data[ start + dn[i] ].stage;
			//distが移動先に設定されているコスト以下ならば、コストとprevを更新
            if( cost[ start + dn[i] ] >= dist ){
                cost[ start + dn[i] ] = dist;
                prev[ start + dn[i] ] = start;
            }
			//移動可能な場所の中で最も少ない距離で進める場所を求め、nextに設定する。
            if( cost[ start + dn[i] ] < min ){
                min = cost[ start + dn[i] ];
                next = start + dn[i];
            }
        }
        //------------ここまで-------------
 
        start = next;
    }while( start != -1 );
 
    return;
}
ページトップ
アバター
h2so5
副管理人
記事: 2212
登録日時: 14年前
住所: 東京
連絡を取る:
h2so5 に連絡する

Re: ダイクストラ法について

#4

投稿記事 by h2so5 » 14年前

visit , cost などの配列はどこで初期化しているのでしょうか？
ページトップ
HamachiOnsen
記事: 7
登録日時: 14年前

Re: ダイクストラ法について

#5

投稿記事 by HamachiOnsen » 14年前

　Search関数を呼ぶ前に、ini_daikstra()という形で初期化関数を呼ぶようにしています。

コード: 

//配列初期化
void ini_daikstra()
{
	int i,j;

　　　　　　//visit,cost,prevの初期化
	for( i = 0; i < MAX_SIZE; i++ ){
		visit[i] = TRUE;
		cost[i] = MAX_VALUE;
		prev[i] = 0;
	}
            //壁以外の場所を初期化
	for( i = 1; i < Y_SIZE-1; i++ ){
		for( j = 1; j < X_SIZE-1; j++ ){
			visit[ i * X_SIZE + j ] = FALSE;
		}
	}
}
ページトップ
box
記事: 2002
登録日時: 14年前

Re: ダイクストラ法について

#6

投稿記事 by box » 14年前

HamachiOnsen さんが書きました:

コード: 

#define Y _SIZE 13					//Y軸の最大サイズ
このコードは、ご自分のところで実際にコンパイルされたものですか？
Y
と
_SIZE
との間の空白には
どういった意味があるのでしょうか。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
HamachiOnsen
記事: 7
登録日時: 14年前

Re: ダイクストラ法について

#7

投稿記事 by HamachiOnsen » 14年前

　ご指摘を頂いた点などを色々と修正いたしました。
あまりレスを長くしすぎるのもアレですので、こちらを編集する形で失礼します。
　box様から
このコードは、ご自分のところで実際にコンパイルされたものですか？
Y
と
_SIZE
との間の空白には
どういった意味があるのでしょうか。

という事でしたので
改めてダイクストラの部分を抜き出し、実際にコンパイル、実行できるようにしたコードを掲載いたします。
また、Yと_SIZEの間の空白は単純にコピーミスです。すいません；

コード: 

#include <stdio.h>
#include <memory.h>

#define X_SIZE 20
#define Y_SIZE 13
#define MAX_SIZE (X_SIZE*Y_SIZE)
#define WALL 9
#define CARD 5
#define MAX_VALUE 9999

//　確定済みかを格納, 　移動コスト,    現在頂点の一つ前を格納
int visit[MAX_SIZE],cost[MAX_SIZE],prev[MAX_SIZE],stage[MAX_SIZE];

//移動変位配列,UP,RIGHT,DOWN,LEFT
int dn[4] = { -20,1,20,-1};

void printboard()
{
	int i,j;

	for( i = 1; i < Y_SIZE-1; i++ ){
		for( j = 1; j < X_SIZE-1; j++ ){
			printf("%4d",cost[i * X_SIZE + j]);
		}
		printf("\n");
	}
	printf("\n");
}

//ダイクストラ
void Search(int start)
{
	int i,min,next,dist;

	//スタート地点のコストを0,prevに現在値を設定
	cost[start] = 0;
	prev[start] = start;

	do{
		min = MAX_VALUE;
		next = -1;
		visit[start] = true;	//現在地を確定する。

		//--------頂点選択------------
 
        //移動先0～3,0ならば上,1ならば右,2ならば下,3ならば左
		for( i = 0; i < 4; i++ ){
			//確定済みか、あるいは移動先が壁ならばコンティニュー
			if( visit[ start + dn[i] ] != false ) continue;
			//スタート地点から移動先までへのコストを格納
			dist = cost[start] + stage[ start + dn[i] ];
			//distが移動先に設定されているコスト以下ならば、コストとprevを更新
			if( cost[ start + dn[i] ] >= dist ){
				cost[ start + dn[i] ] = dist;
				prev[ start + dn[i] ] = start;
			}
			//移動可能な場所の中で最も少ない距離で進める場所を求め、nextに設定する。
			if( cost[ start + dn[i] ] < min ){
				min = cost[ start + dn[i] ];
				next = start + dn[i];
			}
		}
		//------------ここまで-------------

		start = next;
	}while( start != -1 );

	return;
}

void ini_daikstra()
{
	int i,j;
	//visit,cost,prevの初期化
	for( i = 0; i < MAX_SIZE; i++ ){
		visit[i] = true;
		cost[i] = MAX_VALUE;
		prev[i] = 0;
	}
	//壁以外の場所の初期化
	for( i = 1; i < Y_SIZE-1; i++ ){
		for( j = 1; j < X_SIZE-1; j++ ){
			visit[ i * X_SIZE + j ] = false;
		}
	}
}

int main()
{
	int start;
	//移動コストの配列　　// 9 = 壁, 5 = 牌, 1 = 空き
	int arraystage[MAX_SIZE] = {
		9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
		9,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,9,
		9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
		9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
		9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
		9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
		9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
		9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
		9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
		9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
		9,1,5,5,5,5,5,5,5,1,1,5,5,5,5,5,5,5,1,9,
		9,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,9,
		9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9
	};

	//移動コストの設定
	memcpy(stage, arraystage, sizeof(arraystage) );

	//開始点を仮に45と設定
	start = 45;
	//ダイクストラ用配列の初期化関数
	ini_daikstra();
	//ダイクストラによる最短経路検索
	Search(start);

	//開始点から各頂点までの経路描画
	printboard();

	while(1);
	return 0;
}
ページトップ
box
記事: 2002
登録日時: 14年前

Re: ダイクストラ法について

#8

投稿記事 by box » 14年前

当方では、true と false の定義がない、というコンパイルエラーが出ました。
また、
HamachiOnsen さんが書きました:

コード: 

			//確定済みか、あるいは移動先が壁ならばコンティニュー
			if( visit[ start + dn[i] ] != false ) continue;
「移動先が壁ならば」という条件はどこに書いてあるんでしょうか。

# ダイクストラ氏に敬意を表するならば、daikstraなんていういいかげんなスペルではなく
# きちんとdijkstraって書く方がいいんじゃないかなぁ、なんて思います。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
HamachiOnsen
記事: 7
登録日時: 14年前

Re: ダイクストラ法について

#9

投稿記事 by HamachiOnsen » 14年前

　＞trueとfalseの定義がない
私の環境では問題なくコンパイルできるのですが・・・すみませんdefineしたほうがよかったですね
#define TRUE 1
#define FALSE 0

　＞「移動先が壁ならば」という条件はどこに書いてあるんでしょうか。
大本のプログラムからこれらのコードを抜き出すときにミスしたみたいです；すいません
正しくはこうなります

コード: 

            //確定済みか、あるいは移動先が壁ならばコンティニュー
            if( visit[ start + dn[i] ] != false || stage[ start + dn[i] ] == WALL ) continue;
#ダイクストラの正式なスペルってdijkstraなんですね、カタカナ読みしか見たことなかったので知りませんでした・・・；
#以降気を付けたいと思います。
ページトップ
アバター
softya（ソフト屋)
副管理人
記事: 11677
登録日時: 14年前
住所: 東海地方
連絡を取る:
softya（ソフト屋) に連絡する

Re: ダイクストラ法について

#10

投稿記事 by softya（ソフト屋) » 14年前

C++でのコンパイルならfalse、trueはエラーにはなりません。Ｃ言語だとC99未対応のコンパイラならエラーになると思います。
なのでお互いの環境を明確にしないままの議論はあまり意味がありません。
by softya（ソフト屋) 方針：私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います（代わりの方がいる保証は出来かねます）。
ページトップ
box
記事: 2002
登録日時: 14年前

Re: ダイクストラ法について

#11

投稿記事 by box » 14年前

仰せのとおりC++でコンパイル～実行してみると、下記の結果を得ました。
コンパイルの際、main() の最後にある while(1); はじゃまなので取っ払いました。
下記の結果が正しいかどうかはわかりません。

コード: 

  33  34  35   2   1   2   3   4   5   6   7   8   9  10  11  12  13  14
  32  37  10   5   0   5   8   9   6   7  12  13  14  15  16  17  18  15
  31  36  15  10   5  10  13  12   7  40  4599999999999999999999  21  16
  30  359999  15  10  15  18  13   8  39  4499999999999999999999  22  17
  29  34999999999999  24  19  14   9  38  4399999999999999999999  23  18
  28  33999999999999  25  20  15  10  37  4299999999999999999999  24  19
  27  32999999999999  26  21  16  11  36  4199999999999999999999  25  20
  26  31999999999999  27  22  17  12  35  4099999999999999999999  26  21
  25  30999999999999  28  23  18  13  34  3999999999999999999999  27  22
  24  27  26  25  24  23  22  19  14  33  36  35  34  33  32  31  28  23
  23  22  21  20  19  18  17  16  15  32  31  30  29  28  27  26  25  24
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
box
記事: 2002
登録日時: 14年前

Re: ダイクストラ法について

#12

投稿記事 by box » 14年前

もう一つ、わからないのは
prev[]
の使い道です。
ループの中で値を更新していますが、その更新値をどこで使っているかがわかりません。
もし不要ならば、削除していいんじゃないでしょうか。

将来、コードを追加して、そこで使う予定である、というならば、話は別です。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
HamachiOnsen
記事: 7
登録日時: 14年前

Re: ダイクストラ法について

#13

投稿記事 by HamachiOnsen » 14年前

　はい、boxさんが貼ってくださったような結果がでます、これだと9999の値の部分の探索が行えていないようなのと
たとえば一行目の左三つ目の部分は最短経路だと3でないとおかしいと思うのですが、うまくいきません
コードのどこかが悪いのだろうとは思うのですが、どこが悪いのかがわかりません；

　あとprev[]についてですが、これは後々求める開始地点から終了地点までのルートを表示するときに辿れるよう記憶しています。
ページトップ
アバター
GRAM
記事: 164
登録日時: 14年前
住所: 大阪

Re: ダイクストラ法について

#14

投稿記事 by GRAM » 14年前

prevは最短経路ツリー用ですね。大丈夫です伝わっています。
問題はnextの候補を現在のノードから4方向に絞っていることだと思われます

出力結果の

コード: 

  33  34  35   2   1   2   3   4   5   6   7   8   9  10  11  12  13  14
　32  37  10   5   0   5   8   9   6   7  12  13  14  15  16  17  18  15
  31  36  15  10   5  10  13  12   7  40  4599999999999999999999  21  16
  30  359999  15  10  15  18  13   8  39  4499999999999999999999  22  17
  29  34999999999999  24  19  14   9  38  4399999999999999999999  23  18
  28  33999999999999  25  20  15  10  37  4299999999999999999999  24  19
  27  32999999999999  26  21  16  11  36  4199999999999999999999  25  20
  26  31999999999999  27  22  17  12  35  4099999999999999999999  26  21
  25  30999999999999  28  23  18  13  34  3999999999999999999999  27  22
  24  27  26  25  24  23  22  19  14  33  36  35  34  33  32  31  28  23
  23  22  21  20  19  18  17  16  15  32  31  30  29  28  27  26  25  24
たとえば中央上部のやや右、この辺りをご覧ください
どうして7の下が40になるのでしょう？
それは4方向にしか探索していないからです。
0から右に探索していき、9999の周りをぐるっと探索してきてコストが40になります。
本来ならばこの探索中にコストが7を超えた時点で、先ほどの7のノードに戻り、そこから下に一つ下がって40は8のコストになるはずです。
ダイクストラは、順位キューを用いて探索可能な経路を把握しておき、
最もコストの少ないノードを確実に得た後、それを最短経路ツリーに登録します。

最もコストの少ないノードがどうして現在のノードの隣4方向に限られるといえるのでしょうか？
そんなはずはありません。
ページトップ
xxx
記事: 26
登録日時: 14年前

Re: ダイクストラ法について

#15

投稿記事 by xxx » 14年前

少し気になったんですが増加するコストが1の場合にダイクストラを適用した場合ダイクストラの恩恵は受けるのでしょうか？
ページトップ
アバター
GRAM
記事: 164
登録日時: 14年前
住所: 大阪

Re: ダイクストラ法について

#16

投稿記事 by GRAM » 14年前

roxion1377 さんが書きました:少し気になったんですが増加するコストが1の場合にダイクストラを適用した場合ダイクストラの恩恵は受けるのでしょうか？
それはroxion1377さんがダイクストラの恩恵というものをどうお考えかによると思います。
ページトップ
xxx
記事: 26
登録日時: 14年前

Re: ダイクストラ法について

#17

投稿記事 by xxx » 14年前

始点から終点まで探索するとき任意の点まで来るのにかかるコストより大きい物を無視して無駄な探索を省けるかどうか、ということです。

と思ってたんですがこの場合始点から全点に対するものだったんで気にする必要はありませんでした。無視してください
ページトップ
HamachiOnsen
記事: 7
登録日時: 14年前

Re: ダイクストラ法について

#18

投稿記事 by HamachiOnsen » 14年前

　ご指摘ありがとうございます。
GRAM さんが書きました: 問題はnextの候補を現在のノードから4方向に絞っていることだと思われます
　二角取りを作る、ということで探査範囲は４方向だ・・・と考えてあのようなコードにしてたのですが、それがいけなかったんですね；
GRAMさんの指摘通りに、nextを求めている部分を現在のfor文から外して、全てのノードから候補を求めるように改変したところ、無事始点から全点への最短経路を求めることができました。

無事次に進むことができそうです。
質問に答えていただき、本当にありがとうございました！（*＾-＾）

以下改変後のコード

コード: 

void Search(int start)
{
    int i,next,dist;
 
    //スタート地点のコストを0,prevに現在値を設定
    cost[start] = 0;
    prev[start] = start;
		
	do{
		next = -1;
        
		//--------頂点選択------------
        //nextを全ノードを探査して決定する。
		for( i = 0 ; i < MAX_SIZE; i++ ){
			//既に訪れているか、i地点までの最小コストが不明のときcontinue
			if( visit[i] != false || cost[i] == MAX_VALUE )
				continue;

			//nextが-1かiの現時点の最小コストが小さいとき、nextを更新する
			if( next < 0 || cost[i] < cost[next]){
				next = i;
			}
		}

		visit[next] = true;	//現在地を確定
		
		//移動先0～3,0ならば上,1ならば右,2ならば下,3ならば左
		for( i = 0; i < 4 ; i++ ){
			//移動先が壁ならばコンティニュー
			if( stage[ next + dn[i] ] == WALL ) continue;

			//スタート地点から移動先までへのコストを格納
			dist = cost[next] + stage[ next + dn[i] ];

			//まだ訪れていない移動先(ノード)
			//あるいは、distが移動先に設定されているコスト以下ならば、costとpreviewを更新
			if( cost[next + dn[i]] == MAX_VALUE || dist < cost[next + dn[i]] ){
				cost[next + dn[i]] = dist;
				prev[next + dn[i]] = next;
			}
		}	
        //------------ここまで-------------

        start = next;
    }while( start != -1 );
 
    return;
}
ページトップ
閉鎖

“C言語何でも質問掲示板” へ戻る