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