・近藤発表 DijkstraとA*でそれぞれ書いた.結構時間が違うことを確認.他2回行った場合も同じ 均衡配分を回したら環七と環八が多かったが,ODの偏在がその要因だった. 新宿のODのOを自宅にしてみたら,それでも結構環七・環八の方に回った. 西側の南北が少ないのが印象的だった. <質疑> 黛さん 中間点くらいにもっと均一に配分したほうがよかったかも ODを変えたら,すごい交通量が多かったエリアは変わった? 近藤 あまり変わっていない,新宿のを移したので,そこは減ったけど他のODを変えていないのでそれが原因かも. 小林さん 設定を変えた方は青梅街道の方が混雑している様にぱっと見見える ・【村橋パート】 小林:村橋くんはヒープでやってみた? 村橋:ヒープ資料UpDateしたからその説明を先にする >ヒープ・ZDD 村橋:ZDDの表現が前回少し語弊があったかもしれないから修正した 羽藤:えーと,ヒープの説明の前に,具体のネットワークがあって,そのネットワークの経路情報はどのように格納されるのかって書かないと,実装できないので,具体の実ネットワークを書いて,格納コードを書いて確認しないとわかんないんじゃないですかね,, 羽藤:ZDDの例も形態素解析の事例=abとかacだとわかんないから,交通ネットワークで説明したほうがわかりやすいのでは. 浦田:p.18は飛ばしたけれど? 村橋:p.18では、ZDDは情報を格納しておくのが簡単ということを言っている 羽藤:グラフ理論は中小規模なネットワークだと使えるので,経路の繰り返し計算たくさんやるなら,他の人も使ってみるといいと思います. 村橋:p.18のスライドの赤の2、ではなく1。1+2 =3が正しそう? 浦田:各接点以下の経路数、とは? 望月:各接点を含む経路ってことですよね? 村橋:そう。二分木で考えると複雑だけど、ZDDだと各接点以下を足し合わせてだせる、ということ。 望月:ネットワークがヒープに落とし込めるとはどういうこと?Dijkstraをヒープで描いていたと思うが、ヒープ、つまり二分木でかけるの?優先度のある構造を使えば経路というか大小関係が一方向にないような保存ができるのはわかるが… ヒープというのは、優先度がある中でも二分木でやるもののことをいうの? 村橋:ヒープ、のなかに二分木がある。2だけじゃなくて3とかもあると思う 望月:さっきのDijkstraにつかってたコードがあったが、イメージが湧いてない 村橋:Dijkstraのなかでヒープが使われているのは、コストを逐一計算すると思うがそのコストをヒープで格納しているってこと? 鈴木: 「最短経路をヒープ=木構造で表すこと」と思っておいて、Dijkstraとかの中で用いる時はまた別のことと思った方が混乱しないと思う 最短経路を書きたい時は 2分ヒープじゃなくても書くことがあるけど、Dijkstraにヒープを用いるときは絶対2になる 鈴木:ヒープ構造は親が子よりも小さい値を持つ構造だから、根のノードを取り出せば良い。根を取れば最小値になっているから 増田:普通にリストで取り出す必要ないということ? 鈴木:データ消去とかデータ追加して格納するときにヒープにすれば、後から取り出しやすいよということ 近藤:Dijkstraでヒープを使う、というのは隣接頂点の集合(疑似コードの中のS)に格納するときに、D[w]順に格納していくってことですか? 小林:上の質問プラス、その時は課題のコードをどう書き換えれば良いのか? 村橋:ヒープで格納していくことに対して、Pythonで書こうと思ったが今日には間に合わなかった 「隣接頂点の集合(疑似コードの中のS)に格納するときに、D[w]順に格納していくってこと」ではなく、一時ラベルをつけておいて、隣接集合の中で一時ラベルが一番小さいものを取り出すということ。 その取り出すときに、一時ラベルの方をヒープで格納するのだと思っていたがまだ実装してないからうまくいくかは未確認。 近藤の言うように、「隣接頂点の集合(疑似コードの中のS)に格納するときに、D[w]順に格納していく」とすると、ヒープの構築を毎回する必要が出てきてしまうから、一時ラベルをヒープで格納するのではないかと思っている。 Pythonで書く場合は…配布コードだと一時ラベルのindexがノードの番号になるように管理していたのでこのままではうまくいかないと思うが、一時ラベルをヒープとして管理できるように書き換える必要があると思う。 Insertやdeleteを用いていくのではないかと思っている。 鈴木:一時ラベルの集合をヒープで持っておいて、一時ラベルが更新するごとにヒープを修正していく 羽藤:近藤さんの指摘どおり,ダイクストラ法で仮の最短距離が更新される度にその値をヒープの末尾に挿入し,上に移動させるとヒープ性が確保されるから,規模が大きくなると早いことが確認できるはずです. 羽藤:優先度付きキューというのは、ヒープのことです。 >課題 小林:江東区の南北交通が多い、交通量が多いから物流とかかな? 小林:リンクが古い? 鈴木:中身を見ると現状と異なっているから…出どころが不明 小林:NWが今のものにするとまた結果は変わってくるだろう 鈴木:Dijkstraの方が計算時間の分散が大きくなりそう。言われてみらればそうだけどそんなに出なかったね。 Bellman-fordは遅いから、リンクコストが負のものを扱う以外はDijkstraかA*がいいです 均衡配分は東京23区のODだから千葉との交通とかは含まれていなくて過小評価かなと思う ・増橋さん 1はコードを読んで、書いた。 Oを固定して、Dを変えていった。各Dに対して5回分平均を取った。 A*アルゴリズムの方がDijkstraよりも早かった(有意かは微妙)。 計算時間が終点に依存するかなと思ったが、差はみられなかった。回数重ねれば? 均衡配分は交通量よりも混雑度を出せば良かったかなと思った。交通容量を350と置いているのはなぜ?csvファイルの処理に時間がかかったが、首都直下の際の規制道路(警視庁が出しているやつ)から抽出して消した。上りと下り両方。交通がどこに流れるかをみたかった。QgisでリンクIDを調べて、コードを書いて削除しようとした。時間かかっちゃったが、関数使ってやると早くなるらしい。リンク削除によって支店終点のどちらにもならないノードがあることによる?エラーが起きてしまった。→csvファイルを作成したが、回らない。→ODを繋ぐ経路がひとつもなくなってしまったのではないか。 週報にも書いてくれたが、demonのようなランダムに削除するのを追加しても良いかなと思った。 浦田 A*のヒューリスティックスはユークリッド。マンハッタンとかもある。基礎ゼミなので、その辺も理解して回してください。 鈴木 交通容量は基本、可能…とある。基本はたしか1車線1200だった。それで計算するとうまく回らなくて、交通センサスで逆算すると、だいたい350が1車線の交通容量。 浦田 1時間あたり350…実際の値からパラメータ調整するのが一般的。ODは24時間のデータ。 ・望月 小林 工夫がされていてよかった。 鈴木  ベルマンフォードで閉回路をやっていたこと、途中で計算を打ち切るようにしていたのが工夫があって良かった。 均衡配分で利用者が経路に関する情報を持っており、最短経路を洗濯するというのが良かった。ワードロップ第一原則と第二原則で比較しても面白かったかも。 小林 スケールバーのオーダーが違う。気をつけてね。 グラデーションの色が分かりやすいものだとさらにいい。 黛 9ページの右側の図は、GISと連動したKplerを使って3Dで可視化できたらいいのではないか。これはUberが開発して、QGISのデータをそのまま持っていけるから使いやすい。可視化に優れている 考察で3つ比較していて面白かった。基本的には、αを変えているということでいい? 望月 真ん中の配分は均衡配分。左は最短経路配分をそのままにしたもの。右はαはゼロだけど実際のことを考えた。 黛 車線数との関係の分析があったら分かりやすかったかも。 均衡配分の結果と混雑を意識しない場合で、車線数が多いと容量や移動量が多いから、比較だったら簡単にできたかも。 ・小島分 質疑 小林 QGISは,他人の資料を見て,自分がやりたい表現をしている人に聞いて勉強するといい. 浦田 QGISは昨年の基礎プロで月田君が資料をまとめてくれたので,聞いてみてください. 小林 アルゴリズムと計算時間の関係のページについて.仮説を立てて検証する構成がいい. 浦田 A*は線形に伸びていく.ヒューリスティクス関数がある程度正しいと,たしかにリンク数に依存しそう.村橋君がやっていたような計算量の算出や計算回数の足し算をやるとよい.計算時間は繰り返し計算を何回したかによる.小さいNWで手計算でやるといい. 村橋 計算時間がA*で綺麗に伸びていくのは,通るリンク数が増えるとゴール方向に向かってその周りを探索していくから.ダイクストラは全部探索するから,調べ終わったところで計算時間は落ち着くのではないか.A*は距離計算で時間がかかっているのではないか. 小島:その通りだと思う. 鈴木:経由リンク数と計算時間の関係が面白かった. ・//増田さん ========================= /最短経路 コードの実装 自分のコードとお手本:Nympy配列かリストか 計算時間の比較 2 ODペア * 5回計算時間を比べた。 Dijkstraでは増田、A*では鈴木 考察 一般的にfor分よりリスト内包の方が速い リストを一つずつより、Numpyの方がはやい A*は、増田コードはDistanceをforごとに呼び出した。お手本では一気に出してリストで呼び出した。 ------------------------- >羽藤 規模が小さいとnumpyのよさがでないのと,pythonのforループは特に遅いから, for文便利だからつかっちゃうけどねw >鈴木 最短経路探索:コードの比較面白かった。 ========================= /均衡配分 広域避難シナリオ ODを単純に。 江東5区を発地とするトリップ。着地は0 隅田川周辺 デフォと広域避難シナリオ、あまり変わらない。 ・混雑度を使えばよかったか。 ・シナリオ:数日前に広域避難し、その後十分時間がたったときの状態と考えられる。→あまり現実的でない ・表現したかったこと、橋がボトルネックになり、渋滞が発生する。でも均衡状態を計算しているから突発的な状況を表すことは難しい。 ・何を表現したいかによって適切な手法があるな。 ------------------------- >小林 差分を表したらわかりやすかったかも。問題の設定は面白かった。 >浦田 内々はないよね。総トリップ数は?もう少し劇的に変化させてみたらよかったのかも。 >自家用車が全部出ていく、というシナリオにしているので結構課題かな、と思ったのだが。 5区で動いてる部分がなくなって、その分が他に行った。配分としては変わっていない。 >羽藤 リンクを切ろうとは思わなかった?逆に増橋さんはこの方法は考えなかった? >ますはし 技術的にこっちができるかなと思った。 >羽藤 災害時の評価、リンク切るのは、ハザードの設定。外を変える。行動を変化させたのは面白い。 >黛 合計の交通量はあまり変わっていない、これで全員増える、と表現できているのかはわからない。 公共交通が遮断されることを考えてプラスに補正してもよかったかも。 --Chat-- 12:34:41 開始 Risa KOBAYASHI : 近藤さん,村橋さん,増橋さん,望月さん 12:34:48 開始 Risa KOBAYASHI : 小島さん,増田さん 12:35:23 開始 Risa KOBAYASHI : の順番でお願いします! 12:36:18 開始 EIJI HATO : BellmanーFordおせーな 12:36:26 開始 EIJI HATO : 名前カッコイイのに 12:37:22 開始 EIJI HATO : なんだその設定は.. 12:37:34 開始 EIJI HATO : 都庁移転か! 12:40:00 開始 EIJI HATO : セントロイド近傍で混んじゃうから,ソース/シンクノードを均等でばらすのも手だよね. 12:40:40 開始 EIJI HATO : 首都直下だと,立川に移転だっけ. 12:43:17 開始 EIJI HATO : 新宿に皇居移転というべきか.. 12:44:11 開始 Taiki Suzuki : 質疑の際にはスライドショーではなく、全スライドが見える画面の方が良いと思います! 12:44:42 開始 EIJI HATO : 距離=配置がかわるわけだから,分布交通そのものが距離依存で変化しそうだよね. 12:47:38 開始 EIJI HATO : 均衡配分は需要変動型配分というのもあって,Networkの所要時間を変化させると,分布交通そのものを,所要時間の関数で書いて,変化させて配分することで,潜在需要の発生を評価するみたい配分計算方法があります.計算の前提条件どう設定するかはとても重要ですね. 12:55:35 開始 EIJI HATO : えーと,ヒープの説明の前に,具体のネットワークがあって,そのネットワークの経路情報はどのように格納されるのかって書かないと,実装できないので,具体の実ネットワークを書いて,格納コードを書いて確認しないとわかんないんじゃないですかね,, 12:56:44 開始 EIJI HATO : ZDDの例も形態素解析の事例=abとかacだとわかんないから,交通ネットワークで説明したほうがわかりやすいのでは. 13:00:26 開始 EIJI HATO : graphillionは中小規模なネットワークだと使えるので,経路の繰り返し計算たくさんやるなら,他の人も使ってみるといいと思います. 13:02:51 開始 望月 陽介 : 各接点を含む経路ってことですよね? 13:17:51 開始 Aiko Kondo : Dijkstraでヒープを使う、というのは隣接頂点の集合(疑似コードの中のS)に格納するときに、D[w]順に格納していくってことですか? 13:23:59 開始 EIJI HATO : 近藤さんの指摘どおり,ダイクストラ法で仮の最短距離が更新される度にその値をヒープの末尾に挿入し,上に移動させるとヒープ性が確保されるから,規模が大きくなると早いことが確認できるはずです. 13:24:14 開始 Taiki Suzuki : 優先度付きキューというのは、ヒープのことです。 13:27:12 開始 浦田淳司 : 全員ですが,有効数字に配慮した表の作成をお願いします.可視性も悪いですし.. 13:27:21 開始 EIJI HATO : Bellman-Fordさんかわいそう.. 13:29:32 開始 浦田淳司 : A*は,どのひゅーりティクス使っているんですかね?全員,説明を省いてる? 13:30:54 開始 EIJI HATO : 乱択で計算手続きの性能評価するのは,センスいいと思います.信頼性の評価指標になってますよね.ふやすと結果が収束するか,距離が遠くなると,違いは大きくなるか,小さくなるかといえば,どっちですかね. 13:34:11 開始 浦田淳司 : ODノードと,通常のネットワークを結ぶリンクってどうなってますか?(>黛さん) 13:35:47 開始 Aiko Kondo : A*のヒューリスティックは緯度経度から算出している距離だと思います。 13:35:51 開始 takuma murahashi : 説明省いてしまいましたが,僕はヒューリスティクスはマンハッタン距離を使いました 13:36:51 開始 Aiko Kondo : pandas ではto_csvするときに、index=Falseとすればindexなしで出力されます 13:39:12 開始 望月 陽介 : ユークリッドでは? 13:42:59 開始 浦田淳司 : 便宜的には,コストを大きくすることでやりたいことに近いことは計算できる,という感じですね.最初のプラン通りで計算するとすれば,切断した後に,経路を持っているかの確認するための最短経路探索を全ODに対して回して,ネットワークの接続性を確認したあとに,均衡配分するという感じですかね. ファイル形式とかデータ構成が,コードが一致していないと,計算が回らないので,コードが読めるようになれば,色々工夫できますね. 13:43:59 開始 EIJI HATO : 距離が遠い方が,A*が早くなりそうだけどね. 13:46:11 開始 Fuga Mayuzumi : ODノードと,リンクを結合させたCSVファイルに,linkID,OD番号,リンクの車線数・最大速度,ODの緯度経度が入っています(浦田さん) 13:46:51 開始 EIJI HATO : 交通容量は少なすぎるね.. 13:47:23 開始 EIJI HATO : きにするのはわかる.BPRの他のパラメータで合わせてる感じになってると思います. 13:50:13 開始 EIJI HATO : おー,閉路いいね. 13:50:32 開始 EIJI HATO : 災害時は右往左往するしなー 13:53:08 開始 EIJI HATO : 配分原理ごとに比較したのも面白いね.研究ではオーソドックスな方法なので,結果の比較の見せ方はそれぞれ工夫するといいでしょう. 13:53:34 開始 浦田淳司 : 車線・1時間あたり,2500*(道路空間や大型車混入による補正率)で1800台/車線・hが可能交通容量ですかね. 14:00:15 開始 Taiki Suzuki : ですよね,,道路交通センサスの混雑度と交通量とのデータから計算すると交通容量が350台/時間・車線とかになったんですよね確か,,なんでなんですかね,, 14:01:03 開始 Taiki Suzuki : あ,あとset()の件についてはすみませんでした.昨年の解答コードを使い回してしまい確認不足でした,, 14:02:27 開始 EIJI HATO : set関数のもとコードの使い方がおかしかったんですかね. 14:02:27 開始 増橋 佳菜 : 皆さんの書いたcodeや考察がとても参考になるので、今回の発表資料も事後で良いのでPDFか何かで#7フォルダで入れておいて共有いただけると嬉しいです。理解できる段階になってから見直したり試したりしたいです。 14:02:50 開始 Fuga Mayuzumi : https://kepler.gl/ 14:03:12 開始 望月 陽介 : ありがとうございます!kepler使ってみます! 14:05:23 開始 Fuga Mayuzumi : keplerの個人的に嬉しいところは,csvを入れるだけで可視化表現ができるところと,QGISで作成したshapeファイルをgeojson形式でエクスポートすればそのまま適用できるところです. 14:08:05 開始 Taiki Suzuki : set()の件,L = list(set(L))でいけると思います.遅いかもだけど,, 14:08:41 開始 浦田淳司 : A*は線形に伸びていくんですね.ヒューリスティクス関数がある程度正しいと,たしかにリンク数に依存しそう.村橋君がやっていたような計算量の算出や計算回数の足し算をやるとよさそうです. 14:09:10 開始 浦田淳司 : QGISは昨年の基礎プロで月田君が資料をまとめてくれたので,聞いてみてください. 14:10:34 開始 takuma murahashi : 計算時間がA*で綺麗に伸びていくのは 14:15:21 開始 浦田淳司 : A*は頑張れば,もっと早くなるのでは,という気もする. 14:16:38 開始 EIJI HATO : これはおもしろい. 14:21:13 開始 EIJI HATO : 規模が小さいとnumpyのよさがでないのと,pythonのforループは特に遅いから,for文便利だからつかっちゃうけどねw 14:22:41 開始 EIJI HATO : おもしろいね,川近傍混まなかったってこと?混みそうだけど.. 14:26:03 開始 EIJI HATO : まあfor文使うけどねww 14:26:40 開始 EIJI HATO : suge-na 14:27:32 開始 浦田淳司 : 江東区から出ていく人は増えたけど,江東区の内内をなくしているから,こまなかったのではないかと. 14:27:33 開始 EIJI HATO : 実際には江東5区内も増えそうだよね.シンゴジラみてると右往左往しちゃうから, 14:27:53 開始 EIJI HATO : ナイナイは配分できかないよ. 14:29:07 開始 EIJI HATO : ますはしみたいに切断するのと,ますだみたいに需要ふやすので,シナリオの立て方に違いがあって面白いね. 14:30:17 開始 Taiki Suzuki : 江東区の住民じゃなくても,避難勧告時に江東区に来ていた車も発生交通量に入るから,更に増やしても良いかもね 14:31:34 開始 Taiki Suzuki : 容量は全てのリンクで一括で設定されているので,リンクごとに容量を変えるのは難しいですね,, 14:34:11 開始 EIJI HATO : ナイナイ以外は比率(20%増くらい)で変化してるから,元の配分結果と同傾向になってんのかな. 14:39:21 開始 浦田淳司 : ヒープリーダー!! 14:39:31 開始 Taiki Suzuki : いきなりヒープとZDDは難しいですよねw 14:40:22 開始 浦田淳司 : 青本を貸してあげたほうが,dijkstraとの中での使い方が分かりやすいかも.あったよね? 14:47:26 開始 Taiki Suzuki : 黛さんはC言語どうやって勉強しました? 14:48:18 開始 Fuga Mayuzumi : 本を読んで自分で演習って感じですね、、 14:48:48 開始 Taiki Suzuki : 結構時間かかりましたよね…? 14:48:56 開始 望月 陽介 : そうですね。今はサイトでやってるので、本あったら教えて欲しいです! 14:49:11 開始 望月 陽介 : c++ですが。 14:49:22 開始 Taiki Suzuki : 柴田さんの本がおすすめ.セットで問題集もあるので. 14:49:56 開始 Taiki Suzuki : https://www.amazon.co.jp/新・明解C言語-入門編-明解シリーズ-柴田-望洋/dp/479737702X 14:50:06 開始 Taiki Suzuki : https://www.amazon.co.jp/新・解きながら学ぶC言語-柴田-望洋/dp/4797384093/ref=pd_bxgy_img_2/356-7762649-2640149?_encoding=UTF8&pd_rd_i=4797384093&pd_rd_r=541c3368-f09c-48c6-bd3c-2e9369ddd927&pd_rd_w=J9ub6&pd_rd_wg=GdaXI&pf_rd_p=105d6769-bacf-43d4-85ea-a25cec858a3c&pf_rd_r=8G3NS129QNQWSFE4E5PT&psc=1&refRID=8G3NS129QNQWSFE4E5PT 14:50:08 開始 Taiki Suzuki : これ 14:50:30 開始 望月 陽介 : 同じのみてました!ありがたいです。 14:50:32 開始 Fuga Mayuzumi : 都市と交通の分野との接続は過去のコードとかがないと大変ですね 14:54:41 開始 望月 陽介 : c++より先にCをまず勉強した方が良いんですかね? 14:55:08 開始 Taiki Suzuki : うん,C++はCの上位互換的か感じだから,Cを理解してないと難しい 14:59:30 開始 望月 陽介 : なるほど…ありがとうございます。 15:04:51 開始 浦田淳司 : パラメータ推定も,C++で,できますよ!w 15:05:01 開始 Taiki Suzuki : w 15:12:58 開始 Taiki Suzuki : すみません,, 15:14:31 開始 Taiki Suzuki : 授業聴きながらきついので抜けます,すみません.あとでC言語についてまたSlackで聞くようにします! 15:14:38 開始 Risa KOBAYASHI : ありがとう!