2019.4.18

・スタートアップゼミ2

最短経路探索のプログラム。ダイクストラ法がPythonで書かれる。ダイクストラ法をようやく理解した。

 

各ノードは,最短時間が特定された集合Kと未特定の集合K_barとに分類される.初めは,出発ノードのみKに入っており,出発ノードについては,旅行時間0を,それ以外のノードについては,仮旅行時間を無限大として割り振っておく.

で、たとえばループ1回目なら、唯一Kに入ってる始点ノードから、隣接するノードについて仮の最短旅行時間が計算され、それが,すでに各ノードに割り振られている仮旅行時間より小さければ,仮旅行時間を更新する.

こうして仮旅行時間を更新した後,K_barのうちで,最も仮旅行時間が小さいノードの仮旅行時間は,そのノードの真の最小旅行時間であり,集合Kに移すことができる.なぜなら,そのノードには,他のあらゆるノードから訪問した場合でも,すでに割り振ららている仮旅行時間を更新することはできないからである.

こうして1点がKに移ったら,今度はそのノードに隣接するノードについて,同様の操作をし,また,新たに一点がKに移る.これを繰り返せば,全ての点について,最短旅行時間を確定させられる.

なお,K_barからKにノードを移す際,どのノードに着目して仮旅行時間を計算した時にノードを写せたかをメモしておけば,最短経路も特定できる.

 

・VCGメカニズムの論文読み終える

難しい。よく分からなかった点は、profit-sharing と own-profit の incentive structure の違いか?また文字が多く、何から何を出しているのか、何を求めたいのか、などの流れかわかりにくい。VCGのよく見る式が多分1番最後に出てきてて、それまでたどり着けない。

 

・都市モデルの論文を読む。

従前の都市モデルはmonocentricな仮定、すなわち、都市内に一つの生産中心をもつという仮定を置いてやっていたが、この論文は、住民や従業員のロケーションを事前に与える必要がない。にも関わらず、パラメータをいじることで、様々な都市パターンを生成でき、特定のパラメータを境に、都市パターンの劇的な変化も起こすことが出来る。

アブスト、イントロ、結論しか読んでないので、詳細なモデルについては読めていないが、面白そうではあるので、明日の理論談話会で詳細を聞く。