交差点問題 - mad日記大学のアルゴリズムとデータ構造という授業で題材になってた問題。それにBGL(Boost Graph Library)で取り組んでみた。 交差点問題 左図の様な交差点がある。 全ての進路に信号が設置してある。 矢印方向にしか進むことができない。 交差する進路は同時に信号を点灯することができない。 効率良く車を進めることのできる点灯の仕方を求めよ。 という問題。 まず、こういった現実の問題を数学のモデルに置き換える。それが右図。 ABなどの一つのノードがA->Bなどと進む進路の信号を表す。 交差する進路は互いに線で結ばれている。 同時に点灯する信号のノードを同じ色で塗る。 線で結ばれているノードは同じ色で塗られていてはいけない。 色の数が最も少なくなるような塗わけかたを探せ。 という感じで、モデル化することができる。"色"という概念で考えるのは四色問題がその起源なのかな。 んで、この問題は「N
