問題タブ [np-complete]

ここからの問題です

ACM International Collegiate Programming Contest Asia Regional Contest, 横浜, 2006-11-05

x から始めて を繰り返し掛けると、30 回の掛け算でx計算できます。x^31

与えられた正の整数x^n から始まる乗算と除算によって計算する演算の最小数を見つけるプログラムを作成し、xnn<=200

n = 31 の場合、最小操作数は 6
n = 50 の場合、最小操作数は 7

どんなアイデアでも大歓迎です。

数日前、リソース割り当ての既知の問題を解決するために間隔グラフに取り組んでいました。多項式時間でこの問題 (彩色数) を解決し、間隔グラフの各頂点の色を提供する貪欲なアプローチがあることがわかっているためです (一般的なグラフで彩色数を見つける問題は NP-Complete (Karp による 3-充足可能性削減) です。

私は疑問に思っていました: 区間グラフではないグラフがあった場合、それは長さ > 3 の弦のないサイクルが 1 つだけあるためです (それを削除するとグラフが区間グラフになるというエッジがあります)、この種のグラフで彩色数を見つける問題を NP-Complete にしますか?

集合 A = {a ₁ ,a ₂ ,...,a _n }が与えられます

_{B 1}、B ₂、...、B _mという名前の A のサブセットが与えられます。H という名前の A のサブセットが、指定されたすべての B と交差する場合、H を「カバー サブセット」と呼びます。与えられた A と B に対してサイズ K (H のカーディナリティは K) の「カバーするサブセット」はありますか? この問題が NP 完全であることを証明してください。

いくつかの既知の問題を「サブセットをカバーする」問題に減らす必要があります。

Vertex-Cover 問題 (VC、既知の Np-Complete 問題) の 2 近似アルゴリズムに関する質問を見たことがありますが、答えがわかりません。問題は次のとおりです。「スパニング ツリー」を使用して、頂点カバー問題の 2 近似アルゴリズムを見つけます。さて、VC に関しては既に多くの貪欲なアプローチが提示されていますが、「スパニング ツリー」を使用した特殊なアルゴリズムは挑戦的です。何か案が？

次の問題が NP-HARD にあることを知っています: 単純なグラフ G=(V,E)、2 つの頂点 v、V の v'、整数 B、および非負の長さ関数 len: E-> Z+ が与えられた場合、長さが B 未満の v から v' への単純なパスはありますか?

私の質問は次のとおりです。以前と同じ条件が与えられた場合、頂点 v から v' までの G 内の必ずしも単純ではない最長のパスを見つけることに関心がある場合、問題はまだ NP-HARD にありますか?

注: ハミルトンパスをそれに還元しようとしましたが、NP に還元可能な問題があるかどうかを証明することはまだできません。ゲイリー＆ジョンソンも調べましたが、見つかりませんでした。

この問題が NP-HARD であるかどうかを証明するためのヒントを教えてください。前もって感謝します！

2 つのラベル付きグラフ G と T があり、アルゴリズムは、G が T のサブグラフであり、メイン グラフ T とサブグラフ G の対応する頂点が同じラベルを持つべきかどうかを判断すると仮定します。

これが質問です。明確で効率的な証拠があるかどうか疑問に思っています:

頂点カバー: 入力無向 G、整数 k > 0。すべてのエッジをカバーする頂点 S のサブセット (|S|<=k) はありますか?

Dominating Set: input undirected G, integer k > 0. すべての頂点を支配する頂点 S のサブセット (|S|<= k) はありますか?

頂点は、そのインシデント エッジをカバーし、隣接するエッジとそれ自体を支配します。

VC を NPC とすると、DS が NPC であることを証明せよ。

ハミルトニアン パス問題のわずかに修正されたバージョンを解こうとしています。開始点と終了点が与えられ、解が存在するかどうかを判断する代わりに、解の数(0 の場合もある) を見つけたいという点で変更されています。

グラフは 2D 配列として与えられ、ノードは配列の要素です。また、移動できるのは水平または垂直のみで、斜めには移動できません。言うまでもなく、1 つの都市から 2 つの都市に移動することはできません。そのためには、1 つの都市を 2 回訪問する必要があります。

各ノードで 4 つ (エッジ上のノードの場合は 3 つまたは 2 つ) の可能な移動をすべて試行し、ソリューションの数をカウントするブルート フォース ソリューションを作成しました (これは、ゴールに到達し、他のすべてのノードも見たときです)。適度なサイズの入力（たとえば、7x7配列など）で途方もない時間実行されました。

目標がわかっているので双方向検索を使用することも考えましたが、フリンジを満たしたいだけでなく、すべてのノードが訪問されたことを確認したいので、これはあまり役に立ちませんでした。さらに、すべてのノードが 2 つのフリンジ間で使い果たされると、結合できないような形で終了する可能性があります。

力ずくの解決策しか残されていないように感じます。問題自体は NP 完全であることはわかっていますが、ブルート フォースに対する改善点があるかどうか疑問に思っています。誰かが何か他のことを提案できますか?

- 編集 -

双方向検索を使用しても実際には役に立たないと言いましたが、そう考えた理由を明らかにしたいと思います。左上と右下のノードがそれぞれ開始点と目標点である 2x3 グラフを考えてみましょう。双方向検索のフリンジをスタートから右に移動させ、ゴールから左に移動させます。2 回の移動の後、すべてのノードが訪問されますが、1 つのノードから一方向にしか移動できないため、フリンジに参加する方法はありません。ただし、David が以下の回答で指摘したように、いくつかの変更を加えてアルゴリズムを機能させることは可能かもしれません。

これが私の問題です。P2P ネットワークには、同じデータ ブロックを要求する n 個のピアがあります。そして、いくつかの制約があります。1. 独自のアップロード帯域幅を持つピア。平均帯域幅はデータ ブロックのサイズです。2. ピアには、このデータ ブロックに関する異なる期限があります。1 つのピアが期限までにブロック全体を取得できなかった場合、サーバーのヘルプを検索する必要があります。3. ピアは、データ ブロック全体を持っている場合にのみ、データ (部分的または全体的) を転送できます。

目的は、サーバーの総アップロードを最小限に抑えることです。最適なアルゴリズムがあるのか​​、それとも NP 問題なのかはわかりません。締め切り優先または最大帯域幅優先の状況では対処できない場合があります これに似た NP の問題はありますか? これはグラフ フローの問題や命令スケジューリングのようなものですが、締め切りとサプライヤーの総帯域幅の増加を同時に処理しなければならないため、難しいことがわかりました。解決策についての指示やリソースを入手できることを願っています:)ありがとう。

グラフの最小帯域幅を見つけるための NP 完全な「最小帯域幅」問題に興味があります。よく知らない人のために、ここにリンクがあります...

http://en.wikipedia.org/wiki/Graph_bandwidth

Cuthill-McKee アルゴリズムを実装しました。これは、帯域幅が削減された頂点の順列を与えるのに非常に成功しました。ただし、帯域幅が狭いだけでなく、最小帯域幅を探しています。この問題を経験したことがある人がいる場合、削減だけでなく最小のソリューションを提供するアルゴリズムは何ですか? アルゴリズムの実際の実装は必要ありません。実際の最小帯域幅を生成するために調査するアルゴリズムについて提案が必要なだけです。