Diceこの広告は、90日以上更新していないブログに表示しています。2012の10日目の記事です。はじめにBoost.Graphでは様々なグラフの問題を扱うことができます。効率よく解くためのA*アルゴリズムや、平面グラフに対する彩色問題を解くためのアルゴリズムも提供されています。Worldといった用語を見つけることができます。巡回セールスマン問題)についてのBoost.Graph内での扱いを調べてみました。それに付随して、その中で使われているBoost.Graphの機能とか考え方についてを簡単に述べます。Problem、TSP)は、都市の集合と各2都市間の移動コスト(たとえば距離)が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める(セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める)組合せ最適化問題である。問題としては非常に有名な問題で、厳密解を得る場合はNP困難*1な問題であることが知られています。これらの「困難な」問題に対するアプローチとしてはいくつかあります。遺伝的アルゴリズムを用いて探索を行い、厳密解を求める事を放棄しつつもより良い解を求めていく方法や、解の質をある程度保証しつつも、より現実的な時間で何らかの経路を導きだす方法があります。NPとして証明されない限り*2は、「どのような場合においても*3その厳密解を得る」ことは非常に難しいと考えられています。metric_tsp_approxこの関数がBoost.Graph内でTSPを解くために提供されている関数です。この関数は巡回セールスマン問題の解(候補)である経路を返します。関数の説明としては、以下の内容が与えられています。http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/metric_tsp_approx.html上記の説明から、Boost.Graphを使って巡回セールスマン問題を解くために提供されている関数は以下の特性を持っている事が分かります。graph)であること。inequality)*4を満たす事。この実装によって得られる解は厳密解ではない(かもしれない)が、どのような場合でも厳密解の2倍以下の値であること。(近似率2であること)関数の名前にapprox(近似の)という名前が入っていることからも本当は分かるのですが、上記の制約を満たす問題・解で満足できるのであればBoost.Graphを使って巡回セールスマン問題の(近似)解を得る事ができます。アルゴリズムの実装としてアルゴリズムイントロダクションのp.1029にある実装を元にしている、とマニュアルに記述があるのですが、記事の執筆段階では残念ながら私は所有していないため、実際に書籍にどのような記述があるかは分かりません。マニュアルの同じページにアルゴリズムの概略が示してあります。L)http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/metric_tsp_approx.html簡単に上記の概略を読み取ると、以下のようになります。対象となるグラフGと辺の重み(距離情報)wを受け取る頂点rをグラフGの頂点から1つ選択するrをrootとするGの最小全域木Tをプリム法*5によって求めるLを木Tを先降順*6で訪問した順の頂点リストとする上記で求めたLの中から、ハミルトン経路Hを返す以上の方法で近似率2となる学術的理由については、上記の本がないため分かりませんが、やっていること自体は単純なようです。マニュアルを読み進めていくと、以下の記述が見つかります。[2].この事から、TSPを解くためのグラフに無向グラフかつ、何らかのモデルが必要となることが分かります。このモデル、ならびにGraphのアルゴリズムに対して、どのように解法を追加するかを少し見ていきます。Conceptグラフのデータ構造には様々なものがあります。>の様に頂点集合と辺集合を直接持つことで表現する事もできますし、行列を使った表現方法もあります。これらの表現方法は、解きたい問題によって有利不利があります。「この頂点から出ている辺の本数」を求める場合なら、前者の例では辺集合を全て探す必要がありますが、後者であれば該当する辺の行を1行走査するだけですみます。(もちろん、工夫によってある程度は改善できますが、ここでは単純なケースのみを考えます)ならば全ての機能を備えておけばいいように思いますが、そうした場合はメモリ容量を食いますし、グラフの変更時などに時間がかかりますので、結局のところトレードオフとなるのです。そこで、Boost.Graphではデータの特徴に対してコンセプトが定義されています。その中の1つ、VertexListGraphでは「グラフ中の全ての頂点を効率よく走査できること」を示す構造に対して設定されるコンセプトです。アルゴリズムを実施する際に上記の性質が必要であるなら、これを要求できます。事実、metrix_tsp_approxのインタフェースとして、VertexListGraphが要求されていることを確認できます。vis)http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/metric_tsp_approx.htmlVertexListGraphのモデル(具体的な実装)としては、Boost.Graphでおなじみのadjacency_listがあります。metric_tsp_approxはVertexListGraphとIncidenceGraphの両方の特性を持つグラフを要求しています。ここのところは自信がないのですが、続く注釈[2]と実装のインタフェースを鑑みるに、実際はVertexListGraphのグラフを渡してやればよいのですが、adjacency_listを渡した場合で特定の場合に処理効率が悪くなるため、別途IncidenceGraphの性質を要求しているのではないのかと思います。この両方の特性を満たすモデルとしては、adjacency_matrix(隣接行列)がありますので、今回の実装ではこれを利用します。visitorBoost.Graphにはvisitorという概念が存在します。これは、STLでいうfunctor(関数オブジェクト)のようなものです。私たちは、問題を解くためにグラフを作り、既存のアルゴリズムの中に注入しますが、グラフの問題を解いているいずれかのタイミングで何らかの処理をしたくなることがあります。このように、問題の決められたタイミングでコールバックを行ってくれる関数オブジェクトを登録することができ、問題を拡張することができるようになっています。そのため、functorは大体1つの呼び出し(operator())しか持ちませんが、visitorは複数の関数を持つ場合があります。Visitorを挙げます。BFS)を実行する関数breadth_first_searchのVisitorとして提供されています。アルゴリズムの実行中、まだ未探索のノードを見つけたとき」などなどの様々なタイミングで処理ができるように関数が定義されています。Visitorというものが定義されています。このVisitorにはvisit_vertexという関数が1つだけしか定義されていません。実装を見てみたところ、上記のアルゴリズムでハミルトン経路が求められた後、その経路を順に呼び出しているだけ見たいです。下の関数metric_tsp_approx_from_vertexの実装内を参照)なので、上記Visitorのコンセプトを満たしているものとしてtsp_visitorが定義されていますが、専ら経路・距離の出力用に使用されています。解を求めた後に順番に呼び出しているので、この場合のVisitorを活用して問題を拡張するのは難しいように思います。実装これまでの説明をふまえて、実際にTSPアルゴリズムを使ってみました。ソースコードは以下の通りです。Githubにも問題とあわせてアップロードしてあるので、そちらもご参照ください。namespaceの使い方が酷いですが、目をつぶってください。アルゴリズムに渡すさえ守ればOKです。関数別に見ていきますget_inputでファイルの入力内容を(x,y)のペアのvectorに変換しています。make_graphでグラフを作成しています。今回のグラフは隣接行列なので、グラフのインスタンス化のためにはノード数を指定することで、そのノード数を持つ辺0のグラフができます。vertices(g)が返すのはstd::pairです。今回は自身をのぞく他の頂点と無向辺を結びます。三角不等式を守るために入力頂点を座標と見なして距離を算出します(これも頂点のプロパティマップとする方が良かったと思いますが、今回はしていないです)。辺のプロパティマップに2頂点間の距離を辺の重みとして設定します。my_tsp_tourでmetric_tsp_approxを実施しています。len_visitorを使用することで、経路とその経路の距離がまとめて取れます今回はグラフが作成できることを前提としているので、そのエラーチェックなどは行っていません。実際に入力を行ってみます。Run1つ目は簡易なテストデータを用意しました。下記の文字イメージが示すような格子イメージの頂点です。->ということで、一応ハミルトン閉路の出力は行われています。あるため、厳密解は得られていないことが分かります。これは解の求め方の性質上だとは思うのですが、、、TSPLIBTSPは広く研究されており、作成したアルゴリズムの性能比較のための問題セットが用意されています。(など)このページのトップにある画像は面白い問題で、最短経路を導けると「TSP」の文字が浮かび上がってくるようになっています。この問題はtsp225と呼ばれる問題です。実際にこの問題を解いてみました。問題入力の簡単化のため、端数は全て切り捨てて計算しているため、厳密に同じ問題を解いているわけではありません。結果は次の通りでした。->この問題の最適解は距離3919であるため、誤差を踏まえても最適解の2倍以下の距離の経路を解として出力している事が分かります。まとめBoost.Graphに用意されているTSPの仕組みを使って、限定された形ではありますが巡回セールスマン問題の近似解を求めることがかなり簡単にできることが分かりました。Graphは楽しいので、機会があれば別の機能も使ってみたいと思います。間違いなどありましたらご指摘いただければ幸いです。*1:NP完全問題よりも難しい問題。NP完全問題の例としては充足可能性問題(SAT)などがある。NP完全問題は解がYesかNoで答えられる決定問題が属するクラスであり、ある問題が決定問題より難しく、特殊例や部分問題がNP完全な問題である事を示せば、その問題はNP困難足りうる。巡回セールスマン問題に大しては、NP完全な問題であるハミルトン閉路問題を部分問題として含み、さらにそのコストが最小になるパターンを求めなくてはならないのでNP困難である。NPであるという主張の方が強い*3:勘違いされやすいですが、ノード数が増え過ぎるような「任意の」問題に対して難しいのであり、状況を限定する場合は現実的な時間で厳密解を得られる可能性があります*4:ユークリッド空間上での三角形の辺の長さに成り立つ関係。三角形の辺a,b,cに対して、長さがa*5:http://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95*6:ノードの子供より先に自分自身を評価して、次に子供を評価する方式。2012に...2012-05-14第4回プログラミングの基礎読書会まとめ5.3〜6章終了まで。月別アーカイブはてなブログをはじめよう!a-hisameさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。