問題タブ [np-hard]

最近、私は次のようなセミナー作品を読みました。

[一般的なグラフの] マッチング アルゴリズムは、重み付きの場合に拡張できます。これは、多項式時間で解くことができる「最も難しい」組み合わせ最適化問題の 1 つと思われます。

すぐに次の疑問が頭に浮かびました。

他の「P-hard」問題を知っていますか?

今のところ、P-hard を次のように定義したいと思います。(または、多項式時間で問題を解決する決定論的アルゴリズムが既にある場合、どのように「ハード」をより適切に定義できますか?)

決定論的アニーリングのコードのオープン ソースの例を見つけたいと思います。C、C++、MatLab/Octave、Fortran など、ほぼすべての言語で使用できます。シミュレートされたアニーリング用の MatLab コードを既に見つけたので、MatLab が最適です。このアルゴリズムを説明する論文は次のとおりです。

決定論的アニーリングは、コスト関数のグローバルな最小値を見つけようとする最適化手法です。この手法は、ローカル情報を使用して最適化を実行しながら、ランダム性を使用してコスト面の大部分を調査できるように設計されています。この手順は、コスト関数を変更してランダム性の概念を導入することから始まり、広い領域を探索できるようにします。各反復でランダム性の量 (Shannon Entropy [2] で測定) が制限され、局所的な最適化が実行されます。課される乱数の量が徐々に減少し、終了時にアルゴリズムが元のコスト関数を最適化し、元の問題に対する解が得られます。

NP完全であるが、「迅速な」アルゴリズムを知っている言語はありますか? ナップザックのように平均的にうまくいくという意味ではありません。最悪の場合でも、実行時間は 2^n^epsilon のようなものであり、結果は 0 より大きい任意の epsilon に対して保持されるため、任意に 0 に近づけることができます。

分類アルゴリズムを試しているときに、次のアルゴリズムの問​​題が発生しました。要素は多階層に分類されます。これは、単一のルートを持つ半順序集合であると私は理解しています。集合被覆問題によく似た次の問題を解決する必要があります。

ラテックスで作成した問題の説明をここにアップロードしました。

1と2を満たす近似アルゴリズムを考案するのは非常に簡単です。Gの頂点から開始して「上に移動」するか、ルートから開始して「下に移動」します。ルートから開始し、頂点を繰り返し展開してから、少なくともk個の副格子ができるまで不要な頂点を削除するとします。近似限界は、頂点の子の数に依存します。これは、私のアプリケーションでは問題ありません。

この問題に固有名があるかどうか、または問題のツリーバージョンがあるかどうかを誰かが知っていますか？この問題がNP困難であるかどうかを知りたいと思います。おそらく、誰かがNP困難な問題を減らすためのアイデアを持っているか、問題を解決するための多項式アルゴリズムを持っているかもしれません。あなたが両方を持っているならば、あなたの百万ドルの価格を集めてください。;）

部分和問題の興味深いバリエーションを、職場の友人から教えてもらいました。

サイズ n の正の整数の集合 S と、整数 a および K が与えられた場合、(集合 S の) 部分集合 R のうち、要素 を正確に含み、その合計が K に等しいものはありますか?

彼は、これは時間計算量 O(nka) で実行できると主張していますが、私はこの実行時間を達成する動的計画法のアルゴリズムを思いつくことができませんでした。それはできますか？

多分誰かが石（異なる重量）を異なるサイズのバックパックに入れるためのアルゴリズム、またはそれがどんな名前を持っているか知っていますか？私はPrologでそれをするべきです。石の重さとバックパックの容量を示します。プログラムは私にこれらすべての石をバックパックに入れる方法を教えてくれるはずです。

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

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

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

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

放物線があるとしましょう。今では、すべて同じ幅の棒もたくさん持っています (はい、私の描画スキルは素晴らしいです!)。放物線が使用するスペースをできるだけ最小限に抑えるために、これらの棒を放物線内に積み重ねるにはどうすればよいですか? これはナップザックの問題のカテゴリに分類されると思いますが、このウィキペディアのページでは、現実世界の解決策に近づくことはできません。これは NP 困難な問題ですか?

この問題では、垂直領域を含む、消費される領域 (例: Integral) の量を最小限に抑えようとしています。

最近、 NPとPに関する記事を読みました。与えられた単語の組み合わせを見つける問題は NP 問題ですか? たとえば、指定された単語antoの場合、結果は anot、toan などになります。私が知ったように、多項式時間で問題の解を確認できるときはいつでも、それは NP の下にあることを意味します。組み合わせの問題は NP に入るのですか？

これは、私が NP と P をよく理解しているかどうかを知るためのものです。

問題をNPとPに分割する主な意図または主な用途は何ですか? これには歴史的な理由がありますか、それとも私たちを助けるためにこれらの概念を作成したのでしょうか? もしそうなら、これらはどこで私たちを助けることができますか?