【事例演習2】               2001年11月更新      「最短経路探索 (1)」           その1      解 説    “最短ルート探索のアルゴリズム”

Slides:



Advertisements
Similar presentations
シミュレーション演習 G. 総合演習 ( Mathematica 演 習) システム創成情報工学科 テキスト作成: 藤尾 光彦 講義担当: 尾下 真樹.
Advertisements

組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
メモリとポインタ. プログラムの前提 コンピュータは、0と1で計算をし、 0と1でデータを保存している。 メモリを学ぶのに必要な知識である。
【事例演習5】  字句解析     解 説  “ハッシュを用いた字句解析の方法”.
イベント イベント: マウスの操作、キーボードの操作、ファイル操作など システムやユーザーからの入力・出力のこと
2001年11月更新 2章 Windowプログラムの構成 Windowsプログラムおよび       PiasTkプログラムの基本構造.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
【事例演習1】 CGプログラム基礎      解 説        “Windowsプログラムにおける      ダイアログボックスの作成方法”    
アルゴリズムとデータ構造 第2回 線形リスト(復習).
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
情報処理演習 (9)グラフィックス システム科学領域 日浦 慎作.
  スケジュール管理手法PERT-Time      解 説    “最早開始時間計算のアルゴリズム”
エクセル(1)の目次 起動法、ブック、シート、セル ブックの開き方 エクセル画面 マウスポインターの種類 シート数の調節 データの入力法
7/10 if 文課題 力作が多くて感心! 演習1:キーボードから2つの整数を入力し、小さい方の数字を 表示せよ。
プログラムのパタン演習 解説.
情報処理 第12回.
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング入門 電卓番外編 ~エクセルで関数表示~.
プログラミング言語としてのR 情報知能学科 白井 英俊.
HSPでのミニゲーム作成 早稲田実業学校PC班 Y氏.
エクセル(1)の目次 起動法、ブック、シート、セル ブックの開き方 エクセル画面 マウスポインターの種類 シート数の調節 データの入力法
基礎プログラミングおよび演習 第9回
地理情報システム論 第3回 コンピュータシステムおける データ表現(1)
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 2011年6月13日
プログラミング論 II 電卓,逆ポーランド記法電卓
システム開発実験No.7        解 説       “論理式の簡略化方法”.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
二分探索木によるサーチ.
イベント,キーコード,イベントハンドラ, アクション,座標
基礎プログラミング演習 第10回.
C言語を用いたシューティング ゲームの作成
P2P方式によるオンラインゲームの研究、開発
DirectX勉強会 第5回.
EVENT プログラミングのスタイル 手続き型: ある決められた場所から開始され, その後は純粋に上から下に流れて行く方式. 実行したいことを, 順番に記述してゆく. 逐次処理形式コーディングの方法である。 今までの授業(情報処理2や3)で 行ってきたプログラミングの演習 bcc32やmake 手続き型.
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
電界中の電子の運動 シミュレータ作成 精密工学科プログラミング基礎 資料.
プログラミング 4 記憶の割り付け.
データ構造と アルゴリズム第4回 知能情報学メジャー 和田俊和.
講義では、Cプログラミングの基本を学び 演習では、やや実践的なプログラミングを通して学ぶ
情報とコンピュータ 静岡大学工学部 安藤和敏
第6回:ラケットを動かそう! (キーボードによる物体の操作)
P2P方式と構成の一般化 負荷の分散、ゲームセッションのデザイン.
・タイプ別のフレームワーク ・デジタルTips(小技テクニック情報)
Cプログラミング演習 第10回 二分探索木.
先進的計算基盤システムシンポジウム SACSIS2007併設企画 マルチコアプログラミングコンテスト 「Cellスピードチャレンジ2007」
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
第2回課題 配布した通り.氏名・学生番号を忘れないこと.
アルゴリズムとデータ構造 2011年7月8日課題の復習
15.cons と種々のデータ構造.
情報知能学科「アルゴリズムとデータ構造」
アルゴリズムとプログラミング (Algorithms and Programming)
JAVA GUIプログラミング 第3回 イベント処理① マウスイベント.
アルゴリズムとデータ構造 2012年7月2日
Windowsアプリケーション プログラミング
vc-2. Visual Studio C++ のデバッガー (Visual Studio C++ の実用知識を学ぶシリーズ)
アルゴリズムとデータ構造 2012年6月11日
福井大学大学院工学研究科機械工学専攻 川谷 亮治
アルゴリズムとデータ構造 2011年6月28日
オペレーティングシステムJ/K (管理のためのデータ構造)
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造1 2009年6月15日
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズム入門 (Ver /10/07) ・フローチャートとプログラムの基本構造 ・リスト ・合計の計算
プログラミング基礎演習 第4回.
cp-15. 疑似乱数とシミュレーション (C プログラミング演習,Visual Studio 2019 対応)
アルゴリズムとデータ構造 2010年6月17日
新人研修発表 平成13年5月14日(月) 探索アルゴリズム ハッシュ法について 株式会社 エーアイネット・テクノロジ          須田 哲生.
Presentation transcript:

【事例演習2】               2001年11月更新      「最短経路探索 (1)」           その1      解 説    “最短ルート探索のアルゴリズム”

【 最短経路探索アルゴリズムはどこに役立つか 】 ①「カーナビゲーション・システム」や「駅すぱーと」等の   最短距離で到達できる経路探索に用いられるアルゴリズム   である(情報処理技術者試験にもよく出題される代表的な   アルゴリズム). ② 距離の変わりに,いろいろな計数を当てはめると,   通信ネットワーク経路の選択や,最適化問題にも用いること   ができる.

最短ルート探索の考え方(1): トークンが等速度で移動する 始点ノードから出発して,最初に終点ノードに到着したトークンの通った経路が, 最短経路である.実に単純明快!! リンクの距離 リンク(道路) ノード(交差点) 4.5 2 Miss トークン1 6 1.4 1.5 2.8 1.1 3 1.6 始点ノード 2.6 終点ノード 5 5.7 【考え方1】 同時にトークンが   等速度でスタートする 1 8 3.3 1.0 2.4 4 6.0 7 【考え方2】 トークンがノードに到着すると(計算上は一気に次のノードへ進ませる),そこからさらにトークンが等速度でスタートする

最短ルート探索の考え方(2):トークンの動きを記録する 知りたいのは,最短でノードに到着したトークンが経由してきた“距離”と“1つ前の 経由ノード”である.これはすべてのノードで同じ.そこで,各ノードは最短で到達 したトークンの“経由距離”と“1つ前の経由ノード”を記録する(トークンが到達す るまでは経由距離の初期値は ∞) 通過したトークンの記録係 ∞  - 経由距離 ∞  - 4.5 6 2 1つ前の経由ノード ∞  - 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 ∞  - ∞  -

最短ルート探索の考え方(3):トークンの動かし方 ● トークンの移動で考えるべき点は2つだけ!!    (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 ∞  - ∞  -

トークンがノードに到着したとき,何をするか 1 トークンがノードに到着したとき,何をするか  ① 後から到着したトークンの“経由距離”の方が短ければ,ノードの“経由距離”と     “1つ前の経由ノード”を,そのトークンのものに置き換える  (注) 計算上,トークンを距離に関係なく一気に進ませるため,後から到着したトークンの 方が経由距離が短い場合が生じる)  ② 後から到着したトークンの経由距離の方が長ければ,そのトークンは出発     させない(出発しても最短でないことは明らか) 1.4  1 ∞  - ∞  - 経由距離 4.5 6 2 2 1つ前の経由ノード 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 ∞  - ∞   -

次にどのノードのトークンを出発させるべきか 2 次にどのノードのトークンを出発させるべきか  “経由距離”の一番短いノードのトークンを出発させる. なぜなら,経由距離の一番短いノードからトークンが出発するとき,本来ならまだ ノードに到着してない(トークンはすべて等速で動いていることを思い出す.計算 上,トークンを一気に進ませるため,次のノードに到着したかのように見えるだけ). 1.4  1 経由距離 ∞  - ∞  - 4.5 6 2 1つ前の経由ノード  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 ∞  - ∞  -

最短ルート探索アルゴリズムの動作例 1.4 1 ∞ - 5.6 5 5.9 2 ∞ - 4.5 6 6 2 2 2.5 2 2.6 1 ∞ 【手順4】  次にトークンが出発可能なノードは,経過距離が一番短いもの    (なぜなら,他のトークンは実際の時間より早く次のノードに進んでいるから) 【手順1‘】 トークンを出発させる.以下同様な手順を,動きうるすべてのトークンが        終点ノードに到着するまで繰り返す  【手順2 】  トークンの経由距離がノードに書き込まれている距離より        短ければ,“1つ前の経由ノード”をトークンの出発ノードに変更する 【手順3 】  トークンが戻って来ないよう,出発ノードにフラッグを立てる 【手順1 】  トークンをつながっているすべてのノードへ進ませる 1.4  1 ∞  - 5.6  5 5.9  2 経由距離 ∞  - 4.5 6 6 2 2 1つ前の経由ノード 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 ∞  - ∞  -

※ 最短ルート探索アルゴリズムをプログラムに 置き換えるときの考え方 ※ 最短ルート探索アルゴリズムをプログラムに                     置き換えるときの考え方 ① トークンが在るノードの番号を格納する変数Pを用意する if(P==8) // ノード8にトークンが在るかを調べる ∞  - 2 P=2; // トークンが在るノード2に着目することを意味する ② トークンの移動先ノードを示す変数qを用意する 1.4 q=2;  // ノード2にトークンを移動させる 1 1.0 ③ノード1に接続するすべてのノードへの距離はノード1がもっている.   他のノードも同じ.  4

最短経路探索のアルゴリズム トークンの到着 トークンの 出発  経由経路表(route)の初期値として0,最短経由距離表(totalDist) の初期値として  ∞をそれぞれ設定する  p に 始点ノード番号をセットする         // トークンをpに置く  pが終点ノード番号に一致するまで繰返す     // トークンがpに到着するまで繰り返す Yes トークンの到着 トークンがいるノードpに接続するすべてのノードに繰返す // 接続先にトークンを移動    qを接続先のノードの番号とする;  //トークンの1つの移動先をqとする    ノードqまでの距離をdist_q とする        /* (1)ノードqに到着したトークンの経過距離比較 */        ノードqに出発済みのフラッグが立っていなくて,かつ        ノードqの経由距離 > ノードpまでの経由距離 + dist_q    /* ノードpを経由したルートの方が,経由距離合計が短いので                 ノードp経由に変更する */    ノードqの“経由距離”をノードpまでの“経由距離 ”+ dist_qにする;    ノードqの“1つ前の経由ノード”をpにする;    ノードqのフラッグを下げる  トークンが出発済みであることを示すために,ノードpのフラッグを上げる No /* (2) 次にトークンを出発させるノードの決定 */   ネットーク全体からフラッグが立っていなくて,かつ経由距離の最も短い   ノードを選び出し,次にトークンを進めるべきノードをpとする トークンの 出発

ネットワークをどのようなデータ構造で表現するか 通常は2次元行列 (ノード数nの二乗)

※無駄な記憶領域と計算スピードを上げるためのデータ構造 《 存在するノードのデータのみを格納する 》 ノード番号 1     2 8 ・ ・ ・ ノード表 (Node) 1   3   4   3        22 3 リンク表において,ノード1の接続先データが格納されている要素の開始位置(link_position) ノード1に接続するノードの個数 (link_size) 1    2   3   4   5   6 リンク表 (Link) 2  1.4 3 2.6 4 1.0 1 1.4 3 1.1 6  4.5 22 23 24 接続先ノード番号 (connect_node) 接続先ノードまでの距離 (dist)       5 5.7 6 2.8 7 2.4

大規模なネットワークでもっと計算を早くするには! 次に出発すべきノードを見出す手順に,無駄が多すぎる! ∞  -  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 2  3  4 ノード1からすべて出発した後,次に調べるべきノード ∞  - 2  3  5  7 ノード4からすべて出発した後,次に調べるべきノード

待ち列(キュー)を利用すると 次に出発すべきノードが早く見出せる 2 3 4 2 3 2 3 5 7 キューに追加 キューから 取り出す     次に出発すべきノードが早く見出せる ①ノード1から出発したリンク先のノードを調べるべきノードとして追加する 2  3  4 キューに追加 最後の要素位置 ②ノード4が次に出発すべきノードとわかったので取り出す キューから 取り出す 2  3   ③ノード4から出発したリンク先のノードを調べるべきノードとして追加する 2  3  5  7 キューに追加

      「最短経路探索(1)」           その2      解 説    “3次元オブジェクトの直接操作”

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次元オブジェクトを   描き,その名前でオブジェクト番号を調べる方法もある

ObjNo = PiasTarget(gp, (XYZV) x1 , (XYZV) 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 ) {   /*--------- マウス左ボタンが押下されたとき ---------*/ 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); lParamにマウスの画面座標位置が セットされている lParamの下半分はX座標 lParamの上半分はY座標

押下されたキーの状態を記憶するには? イベントハンドラ関数  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には押下されたキー番号がセットされている