PowerPoint プレゼンテーション

Size: px

Start display at page:

Download "PowerPoint プレゼンテーション"

ひとおえいさか
5 years ago
Views:

1 平成 0 年度 Fundamental Seminar 経路探索アルゴリズム東京工業大学工学部土木環境工学科朝倉研究室長崎滉大 0/05/

2 目次. はじめに p.. Dijkstra 法 pp.-. ラベル修正法 pp.-. ヒープ構造 pp.0-5. Dijkstra 法のプログラミング pp.5-5. A* アルゴリズム pp.-5. ZDD pp.5- 目次 0/05/

3 はじめに目的交通ネットワークの問題を解くに当たって最も基本となる最短経路探索について学習しこの先の利用者均衡配分などに応用できるようにする 0/05/

4 経路探索例えば右のようなネットワークがあるとして例えばノードからに行くにはいろいろな経路が考えられるや 5 など特に理由もないのに遠回りする人はあまりいないすなわち大部分の人間が一番短いルートを用いるしたがって最短経路を探索することは交通計画において重要視される経路探索 0/05/

5 最短経路探索アルゴリズム代表的な二つ Dijkstra 法 ( ラベル確定法 ) ラベル修正法ある一つの起点からすべての終点までの最短経路とその費用を同時に求められる方法おおまかには Dijkstra 法と同じラベルが修正されうることからラベル修正法と呼ばれるラベル ( 後述 ) を確定させていくこちらはリンクコストが負でためラベル確定法ともよばれるあっても使えるすべてのリンクコストが非負である時にのみ用いることができる Edsger Dijkstra 最短経路探索アルゴリズム 0/05/ 5

6 Dijkstera 法とは前述のようにある一つの始点から全ての終点への最短経路とその費用が同時に求められる全てのノードを集合 K と K に分ける集合 K は起点 o からの最短経路と最小交通費用 ( これをラベルという ) が確定されたものでそれ以外は集合 K に属している交通ネットワークの均衡分析 ( 土木学会 ) 曰くこの説明でわかる人はいないのできちんと解説していきます Dijkstra 法 0/05/

7 Dijkstra 法第ステップ右のようなネットワークを考えノードからその他への最短経路とその費用を計算するこのとき始点のノードはラベル 0 が確定しており集合 K に属している簡単に言うとノードまでの一番早い行き方その費用が移動なしの 0 と決まってもうこの先の議論には出てこないということ 5 これから集合 K に属しているノードは赤くする Dijkstra 法 0/05/

8 Dijkstra 法第ステップまずから一発で行けるノードを列挙するその結果,,5 が挙げられる各費用は,, である一番安いのはノードに行く費用であるのためを集合 K へ移動するそれと同時にこのまでの最小費用はで確定するこのときほかの二つのノードまでの費用も据え置くこのときに行くときの最短経路での直前にあるのはであるための先行ポインタ F について F = とする 5 ここまでが第二ステップこれを残りのノードすべてで行う Dijkstra 法 0/05/

9 Dijkstra 法第ステップから一発で行けるノードを列挙するその結果, が挙げられるまた先ほどのノード 5 も候補に含むこのときノード,,5 に行くための現在の最小費用は 0,, である一番安いのはノードに行く費用であるのためを集合 K へ移動するに行くにはを経由するよりもから直接行くほうが安いため先行ポインタについて F = とする 0 5 各費用を据え置く Dijkstra 法 0/05/

10 Dijkstra 法第ステップから一発で行けるノードを列挙するその結果 5, が挙げられるまた先ほどのノードも候補に含むこのときノード,5, に行くための現在の最小費用は 0,, である一番安いのはノードに行く費用であるのためを集合 K へ移動する先行ポインタについて F = とするノード 5 への最小費用がこのステップでからに変更された 0 5 各費用を据え置く Dijkstra 法 0/05/ 0

11 Dijkstra 法第 5 ステップから一発で行けるノードを列挙するその結果, が挙げられるまた先ほどのノード 5 も候補に含むこのときノード,5, に行くための現在の最小費用は,, である一番安いのはノードに行く費用であるのためを集合 K へ移動する先行ポインタについて F = とするノードへの最小費用がこのステップで 0 からに変更された 5 各費用を据え置く Dijkstra 法 0/05/

12 Dijkstra 法第ステップから一発で行けるノードを列挙するその結果 5 が挙げられるまた先ほどのノードも候補に含むこのときノード,5 に行くための現在の最小費用は, である一番安いのはノード 5 に行く費用であるのため 5 を集合 K へ移動するこのとき 5 に行くにはを経由するよりから直接行くほうが安いため先行ポインタについて F 5 = とする 5 Dijkstra 法 0/05/

13 Dijkstra 法第ステップ残りはノードのみであり先ほどまでのステップを踏んでも 5 から一発で行けるノードは全て K に含まれているためノードが次に K に含まれる先行ノードは F = となる全てのノードが K に含まれたため全てのステップは完了 5 Dijkstra 法 0/05/

14 Dijkstra 法表今までのステップを表にまとめると以下のようになるもし手で Dijkstra 法をするなら表を書いたほうがいい ( そんな奇人いないと思うけど ) 5 Dijkstra 法 0/05/

15 Dijkstra 法表の見方各ノードへの最短経路は先行ポインタをたどっていけばわかる 5 例えばの先行ポインタはの先行ポインタはの先行ポインタはなのでへの最短経路は Dijkstra 法 0/05/ 5

16 Dijkstra 法の問題点もし仮にノードからまでのコストが - 00 万だったら? 現実的にはほぼ起こりえないがその道を通ると確実に 00 万円拾うような道があるとするこのときコストは負であると考えられる 5 への最短経路は先ほどのステップ 5 でと確定しておりその時点でノードは K に属するため経路探索の対象とはならないしかしまでの最短経路が確定した後にのように行くと最小費用は更新されるそれに伴い他の費用も変更しうる -00 万このようにリンクに負の数が存在すると適用できなくなってしまう Dijkstra 法 0/05/

17 ラベル修正法とは Dijkstra 法と同じくある一つの始点から全ての終点への最短経路とその費用が同時に求められる大きな違いがその名の通りラベルが修正されうる点にある集合 K の代わりにリストという概念を取り入れているもう一度交通ネットワークの均衡分析 ( 土木学会 ) 曰くやっぱりわかりづらいので説明しますラベル修正法 0/05/

18 ラベル修正法第ステップ先ほどと同様のネットワークを考えノードからその他への最短経路とその費用を計算するこのとき始点のノードはラベル 0 が確定しているリストにノードを追加する [] 以下リストに加えられているノードを [V] で表現し緑丸で表現する 5 現在の始点を赤丸で表現するラベル修正法 0/05/

19 ラベル修正法第,, ステップ step step step まずノードからへの経路を考えノードにコストをラベリングするノードをリストに入れる [] 次にノードからを考えコストをラベリングするノードをリストに入れる [,] 同様にノード 5 についてコストをラベリングする 5 ノード 5 をリストに入れる [,,5] ラベル修正法 0/05/

20 ラベル修正法第 5, ステップ 5step step リストの一番左にあるノードを始点として考える先ほどと同様にノードからノードを考えるこのときコスト 0 をラベリングするノードをリストに入れる [,5,] ノードについて考えるこのときラベルは変更されない (<+ より ) ラベルが変更しないためリストの変更も起こらない [,5,] 0 5 ラベル修正法 0/05/ 0

21 ラベル修正法第, ステップ step step リストの一番左にあるノードを始点として考える先ほどと同様にノードからノード 5 を考えるこのときコストをラベリングする (>+ より ) 5 は元よりリストに含まれているため変更はなし [5,] ノードについて考えるこのときコストをラベリングするノードをリストに入れる [5,,] 0 5 ラベル修正法 0/05/

22 ラベル修正法第,0 ステップ step 0step リストの一番左にあるノード 5 を始点として考える先ほどと同様にノード 5 からノードを考えるこのときラベルは変更されない (<+ より ) ラベルが変更しないためリストの変更も起こらない [,] ノードについて考えるこのときコストをラベリングするノードをリストに入れる [,,] 0 5 ラベル修正法 0/05/

23 ラベル修正法第ステップリストの一番左にあるノードを始点として考える先ほどと同様にノードからノードを考えるこのときラベルは変更されない (<0+ より ) ラベルが変更しないためリストの変更も起こらない [,] ここでもしノードからまでのコストが -00 万だったら? 0 5 ラベル修正法 0/05/

24 ラベル修正法第, ステップ step step リストの一番左にあるノードを始点として考える先ほどと同様にノードからノードを考えるこのときコストをラベリングする (0>+ より ) ラベルが変更があったためリストにを加える [,] ノードについて考えるこのときコストをラベリングする (>+ より ) は元よりリストに含まれているため変更はなし [,] 5 ラベル修正法 0/05/

25 ラベル修正法第,5 ステップ step 5step リストの一番左にあるノードを始点として考える先ほどと同様にノードからノード 5 を考えるこのときラベルは変更されない (<+ より ) ラベルが変更しないためリストの変更も起こらない [] ノードについて考えるこのときラベルは変更されない (<+ より ) ラベルが変更しないためリストの変更も起こらない [] 5 ラベル修正法 0/05/ 5

26 ラベル修正法第ステップリストの一番左にあるノードを始点として考える先ほどと同様にノードからノードを考えるこのときラベルは変更されない (<+ より ) ラベルが変更しないためリストの変更も起こらない [ ] リストから全てのノードが消えたため終了する 5 ラベル修正法 0/05/

27 ラベル修正法表今までのステップを表にまとめると以下のようになる 5 Dijkstra 法では一つのノードからの費用をまとめて計算しておりこちらはそれを分けて書いているためステップ数は増加するラベル修正法 0/05/

28 ラベル修正法のメリット先ほどのノードからまでのコストが - 00 万だったらどうなるかという問題がラベル修正法だと解決できる第ステップにおいてを計算するためここでのラベルが変更できそれにともない,5, とラベルの変更が行えるこのようにリンクに負の数が存在すると適用できなくなってしまう実際は交通ネットワークにおいてコストが負になることは稀である混雑料金を定義することによって遠回りしたほうが相対的にコストが負になることはあるが絶対的に負になることは一般的には無い 0-00 万 5 ラベル修正法 0/05/

29 Dijkstra 法とラベル修正法ネットワークリンクが負でない一般的な交通ネットワークにおいてはどちらの方が最短経路探索アルゴリズムとして優れているのか? Dijkstra 法は同じノード間に対しての計算を行わないのに対してラベル修正法はその特性上同じノード間に対して計算を行うことがある Ex) ステップとステップそのため計算量が少ない Dijkstra 法の方が交通ネットワークの最短経路探索アルゴリズムとして優れているといえる二つのアルゴリズム 0/05/

30 ヒープ構造ネットワークが複雑になると一度に取り扱うラベルの数が膨大になる元々据え置かれていたラベルに加え新しくラベリングされたものが加えられ大規模になればなるほど最小値を探すのに時間がかかるヒープ構造とは Dijkstra 法におけるラベルの最小値を効率よく見つけ出すデータ構造である 5 5 ヒープ構造ヒープ構造 0/05/ 0

31 ヒープ構造のルールヒープ条件根以外の全てのノード g について (g の親ノードのラベル ) (g のラベル ) 二分木における性質親ノードの配列順位 n のとき子の配列順位は n,n+ 5 5 配列順位 i 5 ヒープ構造を使って何を行うのか? ラベル X(i) 5 ヒープ構造 0/05/

32 ヒープ構造新たなデータを挿入新たなデータが配列順位に追加されるするとヒープ条件が崩れてしまうためデータの入れ替えを行う子が親より小さいラベルを持っていたら交換するヒープ条件が成立するまで繰り返す Dijkstra 法において新しいラベルが追加されたときに適用するヒープ構造 0/05/

33 ヒープ構造データの削除ヒープ条件より一番小さいデータの配列順位はである Dijkstra 法においてノードが集合 K に移動すると最小のデータが一つヒープ構造から削除されるまず配列順位最後尾のデータを根に持っていくヒープ構造 0/05/

34 ヒープ構造データの削除その後親のラベルと小さいほうの子のラベルを交換するこれをヒープ条件が成立するまで繰り返す Dijkstra 法において次に確定されるであろうラベルが根に来るヒープ構造 0/05/

35 R による Dijkstra 法上のネットワークに関して R で Dijkstra 法を実施しノードから各ノードへの最小リンクコストを算出するプログラミング(R) 0/05/ 5

36 R による Dijkstra 法コードの全容プログラミング(R) 0/05/

37 R による Dijkstra 法前半部分は Dijkstra 法を実施するための下準備 # ダイクストラ法段階を踏み最小のリンクコストを持つノードを決定していくまだ調べていないリンクが最小だと認定されないように # 条件の設定 dijkstra<-function(matrix,startnode){ L<-matrix # 行列の作成 L[which(L==0)]<-Inf # すべてのノード間の最小交通費用を無限大にする ( 未開拓なノード ) diag(l)<-0 # 対角成分はゼロ ( 自ノード同士 ) n<-nrow(matrix) # ノード数 d<-rep(inf,n) # あるノードから全ノードへの最小交通費用を無限大にする ( 未開拓なノード ) d[startnode]<-0 # 自ノード同士はゼロ K<-:n # 最小交通費用が未定のノード集合 K<-K[-startnode] # 起点は除去 i<-startnode # このノードに関して最小交通費用を探索する同じノードへの移動はできないプログラミング(R) 0/05/

R による Dijikstra 法後半部分は Dijikstra 法を実践するコード # ダイクストラ法の実施 while(length(k)>0){ for (j in :n) d[j]<-min(d[j],d[i]+l[i,j]) # 最小費用が更新されたら i<-k[which(d[k]==min(d[k]))[]] #M の中で最小費用が最小のノードについて探索する

38 R による Dijikstra 法後半部分は Dijikstra 法を実践するコード # ダイクストラ法の実施 while(length(k)>0){ for (j in :n) d[j]<-min(d[j],d[i]+l[i,j]) # 最小費用が更新されたら i<-k[which(d[k]==min(d[k]))[]] #M の中で最小費用が最小のノードについて探索する K<-K[-which(K==i)] # 今まで起点としていたノードは最小費用が決定したから除去する } d # 起点 startnode から各ノードへの最小費用を算出 } # 先に描写した距離行列で実践 a<-as.matrix(read.csv("matrix.csv",header=f)) dijkstra(a,) 隣接行列をaに, 始点ノードをノードにプログラミング(R) 0/05/

39 R による Dijkstra 法結果ノードを始点としてノードへの最小リンクコストノードへの最小リンクコストノードへの最小リンクコストプログラミング(R) 0/05/

40 プログラミング先ほどの説明のように交通ネットワークにおいては Dijkstra 法がメジャーであるためプログラミングについては Dijkstra 法のみを取り扱うここでは python における Dijkstra 法を取り上げる FS_Dijkstra, Dijkstra_package, tokyo_train_network.csv の三つのファイルの確認をよろしくお願いしますスライドは一応作ってあるだけで主な説明はコード上でしますプログラミング(python) 0/05/ 0

41 Dijkstra 法プログラミング右のようなネットワークを考えるまず隣接行列を定義する 5 色々と定義するプログラミング(python) 0/05/

42 Dijkstra 法プログラミング後々使う未探索ノード集合の中で最小のラベルを持つ要素が何番目にあるのかを取得する関数を定義する Dijkstra アルゴリズムの一番肝の部分のコードプログラミング(python) 0/05/

43 Dijkstra 法プログラミング結果を表示するこれらを一気にやってくれるやつ隣接行列を作りさえすれば ( おそらく ) これで Dijkstra は回ります実際通常の隣接行列では大規模ネットワークを表現するとき疎行列 (sparse matrix) になることが多いため工夫して表現する必要があるプログラミング(python) 0/05/

44 Dijkstra 法パッケージで Dijkstra 法はかなり有名なアルゴリズムなのでパッケージが networkx に入って出回っている今回は例として関東近郊の JR 駅の路線ネットワークを使用 tokyo_train_network.csv に起点終点距離 ( コスト ) が入っているまず準備のために色々と定義するプログラミング(python) 0/05/

45 Dijkstra 法パッケージで Dijkstra 法を適用するこれらを一気にやってくれるやつ試しにいわきから横浜の最短経路を出すなんの面白味もない結果が出た始点終点をいじれば色々な経路が調べられるのでやってみよう! プログラミング(python) 0/05/ 5

46 A* アルゴリズム Dijkstra 法やラベル修正法が全ノードの探索対して A* は一つの目的地への最短経路を効率よく見つける方法とても簡単に原理を述べるとあるノード nn について ff nn : nn を経由した最小費用の推定値 gg nn : nn までの最小費用の推定値 h nn : nn から目的地までの最小費用の推定値としたとき ff nn = gg nn + h(nn) となりある程度適切な h(nn) を導入していき最短経路を探索するとてもとても簡単に説明すると近そうな方から調べていくアルゴリズムである二次元マップなどでは通常 h(nn) にユークリッド距離を適用する A* 0/05/

47 A* アルゴリズム例として東京の地下鉄路線図を用いる読売巨人軍の本拠地東京ドームがある後楽園 ( 緑丸 ) から東工大の所在地大岡山 ( 赤丸 ) までの最短経路を考える全ての駅 ( ノード ) は路線図の通りに立地しているとするよってユークリッド距離は単純な地図上の距離と等しいと考える A* 0/05/

48 A* アルゴリズムまず後楽園駅から直接つながっている駅である南北線東大前駅飯田橋駅丸ノ内線本郷三丁目駅茗荷谷駅を中間ノード候補とするこのとき gg nn + h(nn) が小さいつまり後楽園から近くてかつ大岡山にも近いノードは飯田橋となるよって飯田橋駅を中間ノード n とするこれを繰り返していく A* 0/05/

49 A* アルゴリズム次に飯田橋駅から直接つながっている駅である南北線市ヶ谷駅東西線九段下駅神楽坂駅を中間ノード候補とする先ほどと同様の操作により次の中間ノードは市ヶ谷となるこれを繰り返していくと四ツ谷赤坂見附青山一丁目表参道渋谷中目黒自由が丘大岡山という経路が導き出される実際は乗り換えなどがありこのルートを使う人は存在しないと思われる A* 0/05/

50 A* アルゴリズムここで nn までの費用の推定値 gg nn は探索済みの区間となるためある程度調べると真値 gg* nn に近づけることができるしかしこれから先の費用である h nn はどうしてもわからないそのため概ね正しいであろう値を h nn に導入するユークリッド距離が縮まればおそらく h nn も縮まるであろうということが言えるため二次元マップにはユークリッド距離を用いる h nn をヒューリスティック (huristic) 関数というこれは必ず正しい答えを導けるわけではないがある程度の精度の答えを導けるような関数である A* 0/05/ 50

51 A* アルゴリズム A* は Dijkstra 法と同様に全てのリンクコストが非負の時適用できる同様に h nn も非負でなくてはならない h nn について真のゴールまでの距離 h* nn を上回らない場合 h nn は許容的 (Admissible) であるという先ほどの条件とあわせて全てのノード nn について 0 h nn h* nn この条件が満たされているならば求まる経路は最短経路であることが保障されてるもし適当な h nn を導入するといつまで経っても探索が終わらなかったり終わっても不適当な経路が求まってしまう A* 0/05/ 5

52 A* アルゴリズム NetworkX 今回は詳細な説明は省くが NetworkX に Dijkstra 法と同じように A* のパッケージが存在する詳しくは etworkx.algorithms.shortest_paths.astar.astar_path Dijkstra 法は全てのノードに対して満遍なく探索していくのに対して A* は一つのノードに対して近そうな方向から探索していくので一つの OD ペアの最短経路を導き出すには A* が使いやすい A* 0/05/ 5

53 ZDD( ゼロサプレス型二分決定グラフ ) 今までのアルゴリズムは最短経路を効率よく導き出すもの ZDD は一つの OD ペアの全経路を効率よく見つける方法であるここにおける全経路とは同じ道同じ地点を二度通らない経路とするたとえば東京駅から品川駅の最短経路は山手線なりで直接向かうのが一番早いが東京近郊の範囲で行くルートはとてもたくさんある Ex) 東京千葉成田我孫子新松戸南浦和赤羽新宿品川全経路数は 55 通りも存在する全経路が出せるとどこを通らない経路やこの移動距離以下の経路などの融通がとても効く ZDD 0/05/ 5

54 ZDD とは例えば a,b,c の三つの要素の組み合わせの組み合わせは何通りか? まず a,b,c の組み合わせが通り存在する (λ, a, b, c, ab, ac, bc, abc) この通りの要素を採用するか採用しないかの通りずつなので組み合わせの組み合わせは通り存在する Ex) φ, {a,b,bc}, {λ, b, ac, abc}, {λ, a, b, c, ab, ac, bc, abc} 三つの要素だと 5 通りで通常のやり方でも列挙できるが要素が 0 個になると 0 通りとなり桁数が 00 桁以上になってしまい単純な方法では一生かかっても終わらなくなってしまうそこで ZDD はこの組み合わせ集合のグラフの簡略化を可能にする ZDD 0/05/ 5

55 ZDD によるグラフ表現 S = {ab, ac, c} という要素集合を考える通常の場合分け二分木と ZDD による表現は以下のようになる S={ab, ac, c} S={ab, ac, c} 圧倒的に簡略化される 0 a a よくよくたどってみると ZDD は三つの要素を表している 0 b b 0 c c c c 0 0 c 0 b 場合分け二分木 0 ZDD ZDD 0/05/ 55

56 ZDD の生成法二つ生成法によって ZDD を生成する (a) 冗長接点の削除あるノードからのの矢印が 0 の終端を指しているときそのノードを消す 0 a 0 a a 0 b b 0 c c c c 0 c b 0 c b c 0 0 c b ZDD 0/05/ 5

57 ZDD の生成法 (b) 等価接点の共有同じ種類のノードからでるリンクが同じ終端を指している時そのノードを共有 a a a 0 0 b 0 0 b 0 0 b c c c c 0 c この手順をどの順番で踏んでも同じ形が得られるこの最終形を ZDD という ZDD 0/05/ 5

58 ZDD の OD 経路列挙方法この方法がどうやって経路列挙に役立つのか? 例えば右のようなネットワークがあるとする O vv ee vv リンクの組み合わせは 5 通り存在する ee ee ee しかしこの中で OD 経路になりうるものはつしかない vv ee 5 vv D 集合で表すと {ee ee, ee ee ee 5, ee ee 5, ee ee ee } となり ZDD をうまく適用できそうな雰囲気となるでは OD 経路を効率よく見つけられれば経路列挙に ZDD を役立てることができるのではないか? ZDD 0/05/ 5

59 OD 経路が満さなければいけない性質 OD 経路になるための必要十分条件は以下の二つである Ⅰ. ノードに接続している経路内のリンクの本数を次数とすると始点終点の次数がそれ以外のノードの次数は 0 またはとなる Ⅱ. サイクルを含まない Ⅰ の条件は想像するとわかるがサイクルとは何か? O 右のネットワークは条件 Ⅰ は満たしているがこれは OD 経路とはいえないサイクルがある場合その周辺ノードは条件 Ⅰ を満たしてしまうので条件 Ⅱ が必要であることがわかる D ZDD 0/05/ 5

60 性質の条件式各ノードの次数を記憶する配列変数 deg を用いる次数を deg[vv] とする各ノードに対して deg[vv] の条件が満たされていれば条件 Ⅰ を満たしているまたそのノードが接続している一番小さいノード番号を記憶するcompという配列を用いる O 右図において comp[5],comp[] はとなるノード同士を繋ぐ際サイクルが発生すると comp が等しくなるためサイクルの有無の判定ができる各ノードに対して comp 値が等しいノードを繋ぐことを避ければ条件 Ⅱ が満たされている 5 D ZDD 0/05/ 0

61 フロンティア右の二つのグラフにおいて点線楕円の左側は処理済みの辺右側は未処理の辺であるこのとき二つのグラフの OD を完成させようとすると楕円の右側は同じ状態となる O D このような楕円内の頂点集合をフロンティアと呼ぶフロンティアの厳密な定義は既に処理したリンクと未処理のリンクが双方接続しているノードであるこの判定は deg と comp を用いて行う deg,comp が一致するようなときがフロンティアである O D この場合は同じ計算をすればいいため状態を共有する ZDD 0/05/

62 ZDD のまとめ先ほどのフロンティアについてフロンティア内に属しているノードのみ deg,comp の記憶を行えばいい左のノードは再び計算の対象にはならないため以上のような機構を用いて効率よく OD ペアを列挙することができる内容次第では全ノードを通る方法 ( 巡回セールスマン問題 ) などへの応用も効く ZDD のコードは本に記載されていたが古いコードであったため不具合が多発した興味があればぜひ本を手に取ってほしい ZDD 0/05/

63 まとめまだ紹介していないさまざまな経路探索アルゴリズムが存在するアルゴリズムには一長一短があり正しい知識を持って最も効率のよいものを使いこなすことが我々には必要なのではないか 0/05/

64 参考文献 Python ダイクストラ法で最短経路を求める NetworkX 交通ネットワークの均衡分析 ( 土木学会 ) 駅データ.jp 超高速グラフ列挙アルゴリズム ( 森北出版株式会社 ) 0/05/

PowerPoint Presentation

PowerPoint Presentation 最適化手法第回工学部計数工学科定兼邦彦 http://researchmap.jp/sada/resources/ 前回の補足グラフのある点の隣接点をリストで表現すると説明したが, 単に隣接点の集合を持っていると思ってよい. 互いに素な集合のデータ構造でも, 単なる集合と思ってよい. 8 3 4 3 3 4 3 4 E v 重み 3 8 3 4 4 3 {{,},{3,8}} {{3,},{4,}}