問題タブ [np]

検索アルゴリズムとバックトラック プログラミングにかなり興味を持っています。今のところ、正確なカバー問題を解決するためにアルゴリズム X を実装しました (こちらの他の投稿を参照してください:競合のないセットを決定しますか? )。これは非常にうまく機能しますが、バックトラッキングのより基本的なバリアントでこれを解決することに興味があります。どうすればこれができるのかわかりません。問題の説明は以前と同じです。

セットの束があり、各セットにはいくつかのサブセットがあるとします。

Set1 = { (バナナ、パイナップル、オレンジ)、(リンゴ、ケール、キュウリ)、(タマネギ、ニンニク) }

Set2 = { (バナナ、きゅうり、にんにく)、(アボカド、トマト) }

...

SetN = { ... }

ここでの目標は、各セットから 1 つのサブセットを選択することですが、各サブセットは他の選択されたサブセットと競合しないようにする必要があります (1 つの要素が他の選択されたサブセットのいずれにも含まれていません)。

例として、2 つの Java クラスを作成しました。セットは 1 文字で識別され、要素は単純な数値です。

具体的には次の 2 つの問題があります。

• ヒューリスティックを使用できるようにすべてのセット/サブセットを反復処理する方法 (最小要素、最小コストなどのサブセットを選択)
• 選択したセットとサブセット、およびそれらに含まれる要素を維持する方法。

私が見つけることができる他のすべての例は、数独または n-Queens のいずれかであり、すべて固定 for ループを使用しています。それに加えて、選択したパス/セットが以前に選択したサブセット/要素と競合する可能性があるかどうかを確認するために、関数「isPossiblePartialSolution」を使用できるというかなり一般的なアプローチについて考えていました。

以下に 2 つの Java クラスを示します。

と

NP 問題を使用したリダクションを理解するのに苦労しており、明確にしたいと思います。次の問題を検討してください。

この件に関しては他にも話題があることは知っていますが、このような削減がどのように行われるかはまだわかりません.

これが、このような問題にアプローチする方法であることを理解しています。

1. 与えられた問題が多項式時間で解けると仮定します。
2. 与えられた問題を使用して、多項式時間で NP 困難であることがわかっている問題を解きます
3. これは矛盾を生み出すので、仮定は間違っているに違いない
4. したがって、与えられた問題は多項式時間で解けてはなりません

では、このような問題の場合、これは適切なアプローチでしょうか?

1. グラフのハミルトニアン サイクルの長さとして k を選択した場合 (ハミルトン サイクルがあると仮定)、この問題を使用してグラフのハミルトン サイクルを見つけることができます。
2. ハミルトニアン サイクルは NP 時間でしか見つからないため、この問題も NP 時間でしか解けないはずです。

したがって、問題は次のとおりです。ツリーであるグラフと、使用できるエッジの数が与えられます。v1 から、既に訪れた頂点のいずれかから外れるエッジを選択します。

例：

この例では、最適なアプローチは次のとおりです。

最初は、これは A から始まる長さ k の最大パスを見つける問題ですが、これは些細なことですが、ポイントはいつでも別の方法を選択できるため、そのアプローチは機能しませんでした。

私がこれまでに考えたこと：

1. 木を k で切断し、すべての可能性をブルート フォースします。

2. すべてのエッジのエッジに行くコストを計算します。コストには、移動しようとしているエッジの前のすべてのエッジの合計を、そのエッジに到達するために追加する必要があるエッジの量で割った値が含まれます。そこから、すべてのエッジの最大値を選択し、コストを更新して、k に達するまでこれを繰り返します。

2 番目のアプローチは良さそうに見えますが、ナップザックの問題を少し思い出します。

私の質問は次のとおりです。これに対するより良いアプローチはありますか? この問題はNPですか？

編集:トリミングの答えの反例:

この配列には一連の 6 桁の数字があります。

6 桁の数字のそれぞれから時間を取得するにはどうすればよいですか? 例えば：

その時間を計算に使いたい。

それらの完全な対応物は、NP - 完全が NP 問題で最も難しく、co-NP-complete が co-NP 問題で最も難しいことを意味することを知っていますが、2 つの違いは何ですか? 教科書に「はい・いいえが逆」と書いてありましたが、あまり手がかりがありません。

数週間前、私は、巡回セールスマン問題のバリエーションに事実上分解した問題に遭遇しました。ねじれは次のとおりです。

複数の売り子がいます。都市のリストは動的に増加します (ライブ入力のように) 各都市は限られた時間だけ完全に利益を上げます.一定時間後に都市が返す報酬が少なくなります.全体的な時間制限があります.

明らかに、この問題は NP です。この問題に適合するように修正できる、適切な TSP 近似があるかどうか疑問に思っていました。

より多くの反応を引き出すために、MathExchange に相互投稿しま​​した。

================================================== ==============================

元の質問を StackOverflow で書いていたときに、以前に質問されたことに気付きました。

部分和問題と呼ばれるものがあることが判明したので、ウィキペディアに行ってこの部分を見つけました。

しかし、ウィキペディアに書かれた疑似コードを理解するのに問題があります。

たとえば、目的は S に一致する最も近い数のセットを見つけることだと思いました。

しかし、ここで S はリストです。この要素が 0 の S リストは何ですか?

そして、一体何 if y + cs/N < z ≤ sですか？これをコードに書き出すにはどうすればよいですか？

誰かがこれをphpコードに翻訳するのを手伝ってくれることを望んでいました.

少なくとも私はそのことに精通しています。完全な翻訳である必要はありません。

答えがこのおおよそのアルゴリズムを理解して、自分でphpコードで書くのに十分である限り、それで十分です。