グラフの最小帯域幅を見つけるための NP 完全な「最小帯域幅」問題に興味があります。よく知らない人のために、ここにリンクがあります...
http://en.wikipedia.org/wiki/Graph_bandwidth
Cuthill-McKee アルゴリズムを実装しました。これは、帯域幅が削減された頂点の順列を与えるのに非常に成功しました。ただし、帯域幅が狭いだけでなく、最小帯域幅を探しています。この問題を経験したことがある人がいる場合、削減だけでなく最小のソリューションを提供するアルゴリズムは何ですか? アルゴリズムの実際の実装は必要ありません。実際の最小帯域幅を生成するために調査するアルゴリズムについて提案が必要なだけです。
それは興味深い問題ですが、Wiki (あなたのリンク) を読むと:
重み付けされていないバージョンと重み付けされたバージョンの両方が、二次ボトルネック割り当て問題の特殊なケースです。帯域幅の問題は、いくつかの特殊なケースであっても NP 困難です[4]。効率的な近似アルゴリズムの存在に関して、帯域幅は任意の定数内で近似するのが NP 困難であることが知られており、これは入力グラフがキャタピラー ツリーに制限されている場合でも当てはまります (Dubey, Feige & Unger 2010)。一方、多項式で解ける特殊なケースがいくつか知られています。
したがって、ウィキは、それを任意の定数で近似するのはNP-Hardであると述べています(したがって、この問題にはPTASはありません)。チャンスはヒューリスティックアルゴリズムを使用することです.ブルートフォースアルゴリズムが機能することを確認してください.起動、その後力ずくを使用) しかし、Caterpillar の解決には 1000 年を費やす必要があります。近似アルゴリズムや正確なアルゴリズムではなく、ヒューリスティック アルゴリズムを検索する必要があります。
あなたができる最も簡単な改善は、おそらくあなたのカットヒル・マキーアルゴリズムの結果を取り、それにタブーサーチを投げることです。
適用できるいくつかのアルゴリズムの概要については、この回答を参照してください。
NP 完全であるため、ある種の「ブルート フォース」アルゴリズムを使用する必要があります。したがって、主に、分岐限定または線形プログラミング (その LIP、つまり NP) など、オプションとしてさまざまなブルート フォースがあります。
NP 完全であるため、NP 完全性証明から問題インスタンスを変換し、アルゴリズムを適用して元に戻すことにより、別の NP 完全問題 (TSP、SAT など) のすべての解を取得することもできます。