Spaghetti Source - 無向中国人郵便配達問題
説明 グラフの全ての辺を少なくとも一度通る単純とは限らない閉路の中で，最短のものを求める問題を中国人配達問題という．グラフがオイラー閉路を持つならばそれが答えとなる．そうではない場合はグラフにできるだけ短い辺を追加してオイラーとなるようにする（オイラー補完）． 無向グラフがオイラー閉路を持つための必要十分条件は，奇点が無いことだった．そこで，グラフの奇点の間の最短経路長を長さとするような完全グラフを作る．この上で最小重みマッチングを求め，得られたマッチングに対応する最短経路をもとのグラフに付け足せば，最小オイラー補完となる． 一般グラフの最小重みマッチングは理論的には多項式時間で解けるが，決して簡単ではないため，ここでは動的計画法に基づく単純なアルゴリズムを示す． 計算量 O(o m log n + o^2 2^o)．-O2 をかけて o ≦ 18 程度が限界． 使い方 始点と終点を特定し
Spaghetti Source - 巡回セールスマン問題
説明 巡回セールスマン問題とは，グラフが与えられたとき，全ての頂点を一度ずつ通る巡回路で，経路長が最短のものを求める問題である． この問題は（判定問題にして）NP 完全であることが知られているので，多項式時間の解法は期待できない．単純に全ての経路を試すアルゴリズムは O(V!) 程度の計算量がかかるが，動的計画法に基づくアルゴリズムでは O(V 2^V) 程度の計算量に軽減できる． X[j][S + {j}] = E[j][i] + X[i][S] ここで X[i][S] は始点から i に至る S のすべての頂点を通る最小重み巡回路である．状態 S をビットで管理することによってプログラムが簡潔になる． 計算量 O(n 2^n)． ソースコード void rec(vector< vector<int> >& Y, int i, int S, vector<int>& path) { if
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
