演習１の雛形プログラムを以下に示します。
雛形はこちらからもダウンロードできます。
解答例ソースファイル
/* dijkstra1.c --- ダイクストラ法第１ステップ */
#include <stdio.h>
#include <math.h>
#include <string.h>
#define CrossingNumber 100 /* 交差点数=100 */
#define MaxName 50 /* 最大文字数50文字(半角) */
typedef struct {
double x, y; /* 位置 x, y */
} Position; /* 位置を表す構造体 */
typedef struct {
int id; /* 交差点番号 */
Position pos; /* 位置を表す構造体 */
double wait; /* 平均待ち時間 */
char jname[MaxName]; /* 交差点名 */
char ename[MaxName]; /* 交差点名 */
int points; /* 交差道路数 */
int next[5]; /* 隣接する交差点番号 */
double distance; /* 基準交差点までの距離：追加 */
int previous; /* 基準交差点からの経路（直前の交差点番号）：追加 */
} Crossing;
Crossing cross[CrossingNumber];
int map_read(char *filename)
{
// いままでとかわりません。
}
/* サーチとソートの演習のprint_crossを改変，距離を表示できるよう改造してます */
void print_cross(int i)
{
int j;
printf("交差点番号:%2d, 座標(%5.2lf,%5.2lf), 名前: %s ( %s ),",
cross[i].id, cross[i].pos.x, cross[i].pos.y,
cross[i].jname,cross[i].ename);
printf("\n 目的地までの距離 %5.1lf, 直前の交差点 :%d, 待ち時間:%5.1lf, 隣接交差点 :%d個 ( ",
cross[i].distance,cross[i].previous,cross[i].wait, cross[i].points); /* ここを改造 */
for(j=0; j<cross[i].points; j++) /* 交差道路数だけ繰り返し */
printf("%d ", cross[i].next[j]);
printf(")\n\n");
}
void print_cross_list(int num) /* num個表示 = 表示数制限可能 */
{
int i;
for(i=0;i < num; i++)
print_cross(i); /* 関数print_crossをnum回呼び出す */
}
int search_cross(int num)
{
/* サーチとソートで作成した search_cross をそのまま拝借 */
return f; /* 見つかっていたら、それを、なければ -1 を返します */
}
//この辺まで入力してあります
//ここからは自分で考えながら入力してください
/* 交差点 a と b の間の「距離」を与える */
double distance(int a, int b)
{
return hypot(cross[a].pos.x-cross[b].pos.x, /* この式を変えると */
cross[a].pos.y-cross[b].pos.y); /* 評価がかわります */
}
void dijkstra(int crossing_number,int target)
{
int done[CrossingNumber]; /* 確定済み:1 未確定:0 を入れるフラグ */
力試しに、全部やってみてください。cross[i].distance が全部
最短距離で埋まるように。できなさそうな場合 ↓に ある程度完成した
関数をおいておきますので、それを参考に。
時間はありますので、可能な限り、自分の頭で考えてみてください。
}
int main(void)
{
int crossing_number; /* 交差点数 */
int goal;
int i;
/* ファイルの読み込み */
crossing_number = map_read("map2.dat");
printf("loaded %d crossings\n",crossing_number);
for(i=0;i<crossing_number;i++)
{
cross[i].distance=0; /* 適当に初期化しておきます for print_cross */
cross[i].previous=-1; /* 適当に初期化しておきます for print_cross */
}
/* 目的地の取得 */
printf("目的地を決定します。");
goal=search_cross(crossing_number);
if(goal<0)
return 1; /* 目的地決定失敗 */
dijkstra(crossing_number,goal);
print_cross_list(crossing_number);
return 0;
}
|
さて、説明のところでいった別の方法とだめそうな方法について、 リストを示しておきましょう。あくまで示すだけですので、原則として、 ダイクストラ法が完成した人が試してみるにとどめてください。
/* お気楽簡単バージョン : 全部確定するまでひたすら while */
void calc_distance(int crossing_number,int target)
{
int i,j,n;
double d;
int f=1; /* 継続のフラグ */
for(i=0;i<crossing_number;i++)/* 初期化 */
cross[i].distance=1e100; /* 初期値は有り得ないくらい大きな値 */
/* ただし、基準の交差点は 0 */
cross[target].distance=0;
while(f)
{
f=0; /* ゼロのままなら終了 */
for(i=0;i<crossing_number;i++) /* 全交差点で */
{
for(j=0;j<cross[i].points;j++) /* どの隣りから来るのが近いか */
{
n=cross[i].next[j];
/* 評価指標 */
d=distance(i,n)+cross[n].distance;
/* 現在の暫定値と比較して、短いなら更新 */
/* となりまでの距離＋交差点間距離が最小 → 局所的な最短 */
if(cross[i].distance > d)
{
cross[i].distance = d;
cross[i].previous = n;
f++;
}
}
}
}
}
|
はまる確率がたかいので避けるべき直接的な方法。もう、直線距離をもとめるだけ。
/* 物凄くお気楽バージョン:はまる可能性あり */
void calc_distance2simple(int crossing_number,int target)
{
int i;
for(i=0;i<crossing_number;i++)
cross[i].distance=distance(i,target);
}
|
さて、最後に、ダイクストラ法がさっぱりわからない・わかるけど、 プログラムに書き起こせない、という人のために、あと一歩の関数を 示しておきましょう。苦労することなく動くように、「distanceが 最小の交差点を探す部分」以外を完成させてあります。これを完成させた 上で、どういうプログラムか良く理解してください。
void dijkstra(int crossing_number,int target)
{
int i,j,n;
double d;
double min_distance; /* 例によって「最小」を探すための変数 */
int min_cross;
int done[CrossingNumber]; /* 確定済み:1 未確定:0 を入れるフラグ */
for(i=0;i<crossing_number;i++)/* 初期化 */
{
cross[i].distance=1e100; /* 初期値は有り得ないくらい大きな値 */
cross[i].previous=-1; /* 最短経路情報を初期化 */
done[i]=0; /* 全交差点未確定 */
}
/* ただし、基準の交差点は 0 */
cross[target].distance=0;
for(i=0;i<crossing_number;i++) /* crossing_number回やれば終わるはず */
{
/* 最も距離数値の小さな未確定交差点を選定 → サーチのところ参照 */
min_distance=1e100;
for(j=0;j<crossing_number;j++)
{
/* 距離数値が最小の交差点の番号が min_crossに入るような、
プログラムを書きましょう。注意点としては、done が 0 の
もの、ゴールまでの距離が暫定最小距離より小さいだけが
対象になる、ということです。*/
/* _未確定？_ ______暫定最短より近い？_______ */
if((done[j]==0)&&(cross[j].distance < min_distance))
{
min_distance=cross[j].distance;
min_cross=j;
}
}
/* 交差点 min_cross は 確定できる */
done[min_cross]=1; /* 確定 */
/* 確定交差点周りで距離の計算 */
for(j=0;j<cross[min_cross].points;j++)
{
n=cross[min_cross].next[j]; /* 長ったらしいので置き換え(だけ) */
/* 評価指標「距離」の計算 */
d=distance(min_cross,n)+cross[min_cross].distance;
/* 現在の暫定値と比較して、短いならdistanceとpreviousを更新 */
if(cross[n].distance > d)
{
cross[n].distance = d;
cross[n].previous = min_cross;
}
}
}
}
|
さっきのプログラムに経路を探索する, pickup_path を追加します。
main() にも内容を追加します。そのため、このプログラムは
雛形はなしです。
/* 最短パス設定 */
int pickup_path(int crossing_number,int start,int goal,
int path[],int maxpath)
{
/*
* crossing_number: おなじみ交差点数
* start: スタート交差点番号
* goal: ゴール交差点番号 (dijkstra にも渡すもの)
* path[]: path[0]--path[maxpath-1]に探索した交差点番号を順にいれます。
* で、最後に -1 をいれます。
* maxpath: path[] の最大の大きさ
*
* 詳細は ↓
*
*/
}
int main(void)
{
int crossing_number; /* 交差点数 */
int goal,start;
int path[20];
int i;
/* ファイルの読み込み */
crossing_number = map_read("map2.dat");
printf("loaded %d crossings\n",crossing_number);
for(i=0;i<crossing_number;i++)
{
cross[i].distance=0; /* 適当に初期化しておきます for print_cross */
cross[i].previous=-1; /* 適当に初期化しておきます for print_cross */
}
/* 目的地の取得 */
printf("目的地を決定します。");
goal=search_cross(crossing_number);
if(goal<0)
return 1; /* 目的地決定失敗 */
dijkstra(crossing_number,goal);
print_cross_list(crossing_number);
printf("現在地を決定します。");
start=search_cross(crossing_number);
if(start<0)
return 1;
if(pickup_path(crossing_number,start,goal,path,20)<0)
return 1;
printf("経路確定しました\n");
i=0;
while(path[i]>=0)
{
printf("%2d %5.1lf %s\n",
i+1,cross[path[i]].distance,cross[path[i]].jname);
i++;
}
return 0;
}
|
ゴールは Nishitaga を入力
:
:
交差点番号:89, 座標( 1.66,-4.93), 名前: 長町IC ( Nagamachi-IC ),
目的地までの距離 5.7 待ち時間: 30.0, 隣接交差点 :2個 ( 62 81 )
現在地を決定します。交差点名を入力してください(ローマ字) ->Ekimae-Aoba
交差点番号: 0, 座標( 0.00, 0.00), 名前: 駅前青葉 ( Ekimae-Aoba ),
目的地までの距離 5.6 待ち時間: 30.0, 隣接交差点 :3個 ( 41 38 40 )
経路確定しました
1 5.6 駅前青葉
2 5.5 駅前南町
3 5.4 愛宕上杉南町
4 4.8 新寺
5 4.3 五橋駅
6 4.2 荒町
7 4.1 愛宕大橋
8 3.6 越路
9 3.1 根岸
10 1.4 鹿野二
11 0.0 西多賀
|
さて、pickup_path の中身を思いつかない人のために、時間が来たら、以下に概ねできている関数を示します。
それまでは自力で考えてみて下さい。
int pickup_path(int crossing_number,int start,int goal,
int path[],int maxpath)
{
int c; /* 現在いる交差点 */
int i,j,n;
double min_distance;
int min_cross;
path[0]=start;
i=1;
c=start; /* 現在値を start に設定 */
while(c!=goal)
{
/* 交差点 c の次に行くべき交差点を探す */
/* ダイクストラアルゴリズムによって「最短経路の直前の交差点番号」が
* previous に代入されています。
* previous を使えば、すぐに goal までたどり着けます。 */
c=cross[?].previous;
path[?]=???;
i++;
}
path[i]=-1; /* おしまいのマーク */
return 0;
}
|