PowerPoint プレゼンテーション

【事例演習２】
「最短経路探索 (1)」
その１
解説
“最短ルート探索のアルゴリズム”
2001年11月更新
【最短経路探索アルゴリズムはどこに役立つか】
①「カーナビゲーション・システム」や「駅すぱーと」等の
最短距離で到達できる経路探索に用いられるアルゴリズム
である（情報処理技術者試験にもよく出題される代表的な
アルゴリズム）．
② 距離の変わりに，いろいろな計数を当てはめると，
通信ネットワーク経路の選択や，最適化問題にも用いること
ができる．
最短ルート探索の考え方（１）：トークンが等速度で移動する
始点ノードから出発して，最初に終点ノードに到着したトークンの通った経路が，
最短経路である．実に単純明快！！
リンクの距離
Ｍｉｓｓトークン１
4.5
2
1.4
1.1
2.6
始点ノード
1
同時にトークンが
等速度でスタートする
6
1.5
3
1.6
2.8
5
5.7
3.3
1.0
【考え方１】
リンク（道路）ノード（交差点）
4
【考え方２】
トークンがノードに到着すると（計算上は
一気に次のノードへ進ませる），そこから
さらにトークンが等速度でスタートする
2.4
6.0
7
終点ノード
8
最短ルート探索の考え方（２）：トークンの動きを記録する
知りたいのは，最短でノードに到着したトークンが経由してきた“距離”と“1つ前の
経由ノード”である．これはすべてのノードで同じ．そこで，各ノードは最短で到達
したトークンの“経由距離”と“１つ前の経由ノード”を記録する（トークンが到達す
るまでは経由距離の初期値は ∞）
∞
1.4
通過したトークンの記録係
4.5
2
1.1
3
2.6
1
始点ノード
∞
-
6
1.5
1.6
5
3.3
1.0
4
∞
-
∞
2.8
5.7
∞
-
2.4
6.0
7
∞
-
経由距離
１つ前の経由
ノード
∞
8
終点ノード
最短ルート探索の考え方（３）：トークンの動かし方
● トークンの移動で考えるべき点は２つだけ！！
(1) トークンがノードに到着したとき，何をするか
(2) 次にどのノードのトークンが出発すべきか
∞
-
4.5
2
1.1
3
1
1.6
5
3.3
1.0
-
1.5
-
2.6
始点ノード
6
∞
1.4
∞
2.8
5.7
∞
∞
-
6.0
8
2.4
4
∞
7
∞
-
終点ノード
トークンがノードに到着したとき，何をするか
１
① 後から到着したトークンの“経由距離”の方が短ければ，ノードの“経由距離”と
“1つ前の経由ノード”を，そのトークンのものに置き換える
(注）計算上,トークンを距離に関係なく一気に進ませるため，後から到着したトークンの
方が経由距離が短い場合が生じる）
② 後から到着したトークンの経由距離の方が長ければ，そのトークンは出発
させない（出発しても最短でないことは明らか）
1.4∞
11.4
4.5
2
1.1
2.6
1
始点ノード
2.5
∞
2.6
2
3 1
6
1.5
1.6
5
3.3
1.0
4
1.0∞
1-
∞
-
6.0
2.8
5.7
∞
-
2.4
7
∞
-
経由距離
１つ前の経由ノード
∞
8
終点ノード
次にどのノードのトークンを出発させるべきか
２
“経由距離”の一番短いノードのトークンを出発させる．
なぜなら，経由距離の一番短いノードからトークンが出発するとき，本来ならまだ
ノードに到着してない（トークンはすべて等速で動いていることを思い出す．計算
上，トークンを一気に進ませるため，次のノードに到着したかのように見えるだけ）．
1.4
∞
1
-
4.5
2
1.4
1.1
2.6
1
始点ノード
6
1.5
1.6
3.3
1.0
トークンが出発し終わ
ったら戻って来ないよう
“出発し終わった”ことを
示すフラッグを立てる．
3
2.6
∞
1-
4
1.0
∞
1-
∞
-
トークンが到着している
ノードの経由距離が最小
6.0
5
2.8
5.7
∞
-
2.4
7
∞
-
経由距離
１つ前の経由ノード
∞
8
終点ノード
最短ルート探索アルゴリズムの動作例
【手順１‘】
【手順２
【手順４】
【手順３】】次にトークンが出発可能なノードは，経過距離が一番短いもの
トークンの経由距離がノードに書き込まれている距離より
トークンを出発させる．以下同様な手順を，動きうるすべてのトークンが
トークンが戻って来ないよう，出発ノードにフラッグを立てる
【手順1 】トークンをつながっているすべてのノードへ進ませる
（なぜなら，他のトークンは実際の時間より早く次のノードに進んでいるから）
短ければ，“１つ前の経由ノード”をトークンの出発ノードに変更する
終点ノードに到着するまで繰り返す
1.4∞
11.4
4.5
2
1.1
3
2.6
1
始点ノード
6
6
2.5
2.6
∞
21
-
1.5
1.6
5
5
3.3
1.0
4
1.0
∞
1-
5.6
5.9
∞
52
2.8
4.1
4.3
∞
3
4-
5.7
１つ前の経由ノード
8.49.8
∞
65
-
8
2.4
6.0
経由距離
7
7.0
∞
4-
終点ノード
※ 最短ルート探索アルゴリズムをプログラムに
置き換えるときの考え方
① トークンが在るノードの番号を格納する変数Ｐを用意する
if（Ｐ＝＝８）
∞
-
2
Ｐ＝２；
// ノード８にトークンが在るかを調べる
// トークンが在るノード２に着目することを意味する
② トークンの移動先ノードを示す変数ｑを用意する
1.4
q＝２；
1
1.0
// ノード２にトークンを移動させる
③ノード１に接続するすべてのノードへの距離はノード1がもっている．
他のノードも同じ．
4
最短経路探索のアルゴリズム
経由経路表(route)の初期値として0，最短経由距離表(totalDist) の初期値として
∞をそれぞれ設定する
ｐに始点ノード番号をセットする
ｐが終点ノード番号に一致するまで繰返す
// トークンをｐに置く
// トークンがｐに到着するまで繰り返す
トークンがいるノードｐに接続するすべてのノードに繰返す // 接続先にトークンを移動
トークンの到着
ｑを接続先のノードの番号とする；
//トークンの１つの移動先をｑとする
ノードｑまでの距離をdist_q とする
/* (1)ノードｑに到着したトークンの経過距離比較 */
ノードqに出発済みのフラッグが立っていなくて，かつ
Yes
ノードｑの経由距離 > ノードｐまでの経由距離＋ dist_q
/* ノードｐを経由したルートの方が，経由距離合計が短いので
ノードｐ経由に変更する */
ノードｑの“経由距離”をノードｐまでの“経由距離 ”＋ dist_qにする；
ノードｑの“1つ前の経由ノード”をpにする；
ノードｑのフラッグを下げる
Yes
トークンが出発済みであることを示すために，ノードｐのフラッグを上げる
トークンの
出発
/* (2) 次にトークンを出発させるノードの決定 */
ネットーク全体からフラッグが立っていなくて，かつ経由距離の最も短い
ノードを選び出し，次にトークンを進めるべきノードをｐとする
No
ネットワークをどのようなデータ構造で表現するか
通常は2次元行列（ノード数ｎの二乗)
※無駄な記憶領域と計算スピードを上げるためのデータ構造
《
存在するノードのデータのみを格納する
》
ﾉｰﾄﾞ番号
2
１
ノード表
(Node)
３
１
８
・・・
３
４
22
３
リンク表において，ノード1の接続先デ
ータが格納されている要素の開始位置
(link_position)
ノード１に接続するノードの個数
(link_size)
１
リンク表
(Link)
２
接続先ﾉｰﾄﾞ番号
(connect_node)
２
1.4
３
３
2.6 ４
1.0 １
接続先ﾉｰﾄﾞまでの距離
(dist)
４
1.4 ３
５
６
1.1
６
4.5
22
５
5.7
23
６
24
2.8 ７
2.4
大規模なネットワークでもっと計算を早くするに
は！
次に出発すべきノードを見出す手順に，無駄が多すぎる！
1.4
1
4.5
2
1.4
3
2.6
1
1.0
1
1.0
6
2.6
1
1.1
4
1.5
1.6
5
3.3
３
6.0
４
ノード４からすべて出発した後，次に調べるべきノード
２
３
５
７
2.8
5.7
∞
-
わかりきっている
ので調べないよう
にする
∞
8
2.4
ノード１からすべて出発した後，次に調べるべきノード
２
∞
-
7
∞
-
待ち列（キュー）を利用すると
次に出発すべきノードが早く見出せる
①ノード１から出発したリンク先のノードを調べるべきノードとして追加する
２
３
キューに追加
４
最後の要素位置
②ノード４が次に出発すべきノードとわかったので取り出す
キューから
取り出す
２
３
③ノード４から出発したリンク先のノードを調べるべきノードとして追加する
２
３
５
７
キューに追加
「最短経路探索(1)」
その２
解説
“3次元オブジェクトの直接操作”
描画した3次元オブジェクトには必ず
オブジェクト番号が付く
ObjID_Runner = PiasSphere( gp , x , 0 , z , 20); // 球
オブジェクト番号を格納するint型変数：
ObjID_Runner
●オブジェクトに名前（例えば“Runner”）を付けてから，3次元オブジェクトを
描き，その名前でオブジェクト番号を調べる方法もある
PiasDeclareName(gp,“Runner”);
// これから作るオブジェクトの名前
PiasSphere( gp , x , 0 , z , 20);
// 球
ObjID_Runner = PiasObjectNumber(gp,"Runner");
画面上の座標x1，y1にある
オブジェクトの番号を調べるには
画面座標
X座標
Y座標
(x1,y1)
ObjNo = PiasTarget(gp, (XYZV) x1 , (XYZV) y1 );
この関数を用いる！
どうやって調べているのか
（案1）この領域の中に入っているかで調べる
ではこのような（ｵﾌﾞｼﾞｪｸﾄ1に穴があり，
そこからｵﾌﾞｼﾞｪｸﾄ2が見える）ときは，どうするか
指定した点
ｵﾌﾞｼﾞｪｸﾄ1
ｵﾌﾞｼﾞｪｸﾄ2
ここの点はｵﾌﾞｼﾞｪｸﾄ2のはず
この領域の中にあるを調べただけではダメ
PiasTargetが用いている方法
ダブルバッファ法を利用する．
ダブルバッファ法とは？
【表示中の画面】
2画面を切り換え，
スムーズな動きを作る
【バッファ画面】
ちょっと動かした画面を
表示中に再描画
(1) PiasTargetが呼び出されたとき，もう一方の描画バッファの方で，
オブジェクト番号を色番号と解釈してオブジェクトを描きなおす．
(2) 指定した画面座標のピクセルがどのような色（16ビット）であるかを
調べるOpenGLの関数を用いてオブジェクト番号を得る．
【参考】プログラミングの方法
キーと押下しながら,マウスの左ボタンを押したとき
その位置にあるオブジェクトの番号を知るには？
イベントハンドラ関数 PiasTK_LBUTTONDOWN( HWND hWnd , LPARAM lParam )
{
/*--------- マウス左ボタンが押下されたとき ---------*/ ｌParamにマウスの画面座標位置が
セットされている
if (指定したキーが押下の状態であるか)
{
//----
指定したキーが押下されている状態のとき ----
int objID_Node;
char str[20];
ｌParamの下半分はX座標
ｌParamの上半分はY座標
ObjID_Node =
PiasTarget(gp,
(XYZV) LOWORD( lParam ) ,
(XYZV) HIWORD( lParam )
sprintf(str, “始点ノード %d” , ObjID_Node);
MessageBox (hWnd, str, “ノードの確認”, MB_OK);
)+ 1 ;
押下されたキーの状態を記憶するには？
イベントハンドラ関数
PiasTK_KEYDOWN( HWND hWnd , WPARAM wParam )
{
Wparamには押下されたキー番号がセットされている
switch (wParam)
{
case VK_CONTROL: CntlSts = SKEYDOWN ; break;
case VK_SHIFT :
ShftSts = SKEYDOWN ; break;
case VK_TAB
TabSts = SKEYDOWN ; break;
default: break;
}
}
:

Download Report