夏学期ゼミ#6 4/23 ヒープ-村橋, マルコフ過程の交通量配分-増橋 ------ヒープ構造に関する小発表 by村橋 分離しているものを森, 木の名からで唯一の頂点がルートと特別視されたものは根付き木 サイクルがないので,各頂点までの経路は一通り 根からの最大長を深さ /ヒープ構造とは ラベルが膨大になると複雑になる. ラベルの最小値を効率よく見つけるデータ構造 根以外のノードg gの親ラベル<=gのラベル Dijkstra→始点が決まっている,閉構造がないので,ヒープで表現可能 データが追加されたとき,データの入れ替えは高々ヒープの深さ以内 /ZDD 一つのODペアの前経路を効率的に探索するために使われるアルゴリズム 二本木だと,NWが複雑になったときにノードが多すぎる. ---------------------------- >浦田 二本木は二分木,二進木ともいいます. >羽藤 コードの例があるとよかったかも >小林 確かに.アルゴリズムを書いてみたりするとよかったかも. -ODのOが決定すると,Oをrootとして捉えることができる.rootが1個目,繋がっているのを次の階層. >鈴木 ヒープは二分木で,常に親より大きいor小さいラベルを格納していくデータ構造. 計算量を単純に線形探索すると計算量はO(n)ですが,ヒープを使うと常に親が子より小さく/大きくなるような操作の計算量O(logn)で済む. 速い. >浦田 Dijkstraのどこで使われているの? >鈴木 最小値の探索を行うところ.ヒープで格納しておくと計算が速くなる. >羽藤 普通にリストでやらない方がいいよ,という意味です. >小島 p6の図の右側がZDDで,左側が二本木? -そうです.実線の矢印が1,点線の矢印0は,ある,ないを表している. >浦田 四角の1,0はどういう意味? -四角の0は,要素集合の中に0は存在しない,1は存在する. >浦田 p9,全部列挙した上でODに対応するものを抜き出すのではなく,ZDDで書けば,簡素に書ける. >小林 効率的に探索するために,と書いてあるが,何を探索したいのか. -二分木で考える場合だと,ヒープで保存すると楽だと話があったが,実際のODで適用すると,ヒープで表したときに無駄が多い.記憶しないといけないことをZDDでした方が簡潔. >Dijkstra等に渡すときにZDDで渡した方がいいということ? -そういう認識です. >望月 ヒープで保存する,というのが実際どういう風に格納しているかがわからない.01行列? >羽藤 次回までに実際コードでどう格納されているか発表してください. >鈴木 Dijkstraは経路を全部列挙しない.ZDDは全列挙するのでは? -Dijkstraには使わないかも?次回までに説明します. https://www.codereading.com/algo_and_ds/ds/source/heap.c ↑ヒープ構造のコードの例 by 羽藤先生 ========================================== ------吸収マルコフ過程による交通量配分理論 by増橋 >羽藤 定義をちゃんと説明するのは研究では大事ですね >浦田 p7.I+Q+Q^2+...はどういうことですか? Q^2は? -一回の遷移で非吸収状態に移動したけど,次も非吸収状態に遷移する確率...? >鈴木 補足です.Q^nは,n回遷移したとき,次も遷移. 一台の車が地点iから地点jにいくかの期待値 0回遷移したときから,無限回数遷移する期待値. ---------------------------- EIJI HATO まじよくできてるなー,この式. 八幡浜のRL問題やん! 重ねあわせ便利やなー ---------------------------- >増田 p7.交差点を通る期待値.これは計算したら,そうなるということ? -数学的に成り立つ,と解釈すればいいのかな,思った -数学的に成り立ちます https://manabitimes.jp/math/1421 -鈴木 >増田 Iがなんでしたっけ? -Iはずっと吸収状態,Q+Q^2+Q^3...がずっと非吸収状態だと解釈している -黛 >村橋 p26(pdf).混雑している場合を考えている.「実際のOD交通量と一致していれば,差し支えない」全然違う回り方をしていても,1つので表していいのかが納得いかない. -巨視的にみている場合.全然違う経路を通ってもいいのはおかしい,という指摘だと思うが,全体的にどう見えるか. 交差点でどうなっているか.各個人がどういう経路を通ったからではなくで,交通量がどう分布しているかを把握するには意義があるのでは. -そういう理解でいいと思います.ミクロにみたら課題があるモデルと言えるけれど,交差点における遷移確率から,マクロな交通流を予測することができているという点でメリットがある. 交差点に立って,どのODなのかはわからなかったが,今はPP等を用いて検証もできる. -浦田 >羽藤 RLでも同じように書けるの?遷移確率って,リンクの選択確率みたいなものだよね. -RLだと,逐次的にみているので,交差点という捉え方が巨視的ではないので違う?あらゆる交差点の遷移確率を最初に与えるのは違うのではないか. >渋谷の交差点の中で,繰り返し推移確率をみて,記述できないか?RLモデルは,βが0だったら,マイオティックな,直前の一次マルコフ 時間割引が1のRLは,普通のロジット.佐佐木のマルコフとの関係性が気になった.ロジットモデルで全経路列挙して,計算するのとなにが違うのか? 考えてみてほしい. >村橋 追加の質問.実際のOD交通量と一致していれば,差しつかない,とあったが,どれくらい一致していればいいのか.一致しないときはどう処理しているのだろうか. -どれくらい一致しているか,一致していないのかはτを用いて,極端に離れているかをみて(極端の基準はわからないが) >一致してないときは発展モデルはあるのか? -この論文の中では,4.のODごとのモデルになるのだと思うが. >鈴木 現実とどれくらいずれているかの指標としてτ.RLを時間構造化NWにあてはめて,時間制約を考えながら配分する,というモデルがあって, 時間という意味ではある程度現実に即したようになるモデルはあります. >浦田 均衡配分は,最短経路で,BPR関数を使って こっちは,交差点ごとに,どっち行くかを考えて. 配分結構違うモデル.実際の車等の交通は最短経路が多いので,均衡配分が多く使われているが. まちなかの回遊は,最短経路だけではないので,そういう行動を想定すれば適用可能なのではないか. τを計算すると,確かに結構齟齬は出ると思うが,行動をかんがえながら予測していく >羽藤 交通計画で一番?大事なのは需要を予測する. 数量がわかれば,それにあわせて空間を設計する.NWを設計する. 数量の計算で,一番最初に出てきたモデルが佐佐木のマルコフモデル. 最も基本的で,非常に重要なモデル.今日化学種うのRLにも拡張可能ということで,注目している. 計算の操作性がいい,ということでサイクリックフローが出るというのが計算の都合上出てくる.いやだ→マイクロシミュレーション. 研究レベルでは一意に解が出る. >羽藤 ますはしさんどうだった? >増橋 自分で書き下しているとわかっていると思っても,質問されるとわかっていないな,と実感したり. みんなの反応がわからないのも大変 >羽藤 書いてあることを全部読んでいたが,less than moreなのでどこが一番大事なのか.これが一番重要です,というだけで意識が高まる. >増橋 基本行列の部分と,最終的だとp29(pdf) >羽藤 自分のレコーディングみると恥ずかしいと思うし,茫然自失になると思うが,が勉強になると思います. >羽藤 鈴木くんまとめコメントをください >鈴木 logitモデルとか,均衡配分は経路ベースで効用最大化 マルコフは交差点ごとに,次の交差点.逐次選択. そこの違いを明確にしていくと,logitとの違いとか,理解していけると思います. >羽藤 交差点の選択を繰り返したら,経路になるよね. >鈴木 RLは逐次選択だが,時間割引を1にしたら,普通のlogitと同じになるのが面白いところ.