問題タブ [np-complete]

それを解決するための汎用アルゴリズムのように見えるものを思いついたとき、サブセットサムの問題について読んでいました。

「set」は重複を含まないリストで、「sum」はサブセットを検索する合計です。"subsets" はコンス セルのリストで、"car" はサブセット リストで、"cdr" はそのサブセットの合計です。新しいサブセットは、要素を前面にコンスするだけで、古いサブセットから O(1) 時間で作成されます。

実行時の複雑さはわかりませんが、各要素の「合計」が大きくなると、「サブセット」のサイズが2倍になり、プラス1になるように見えるため、少なくとも2次のように見えます。

以前の印象では、NP完全問題は扱いにくい傾向があり、通常期待できる最善の方法はヒューリスティックであるという印象があったため、これを投稿していますが、CPUサイクルがあると仮定すると、これは汎用目的のソリューションのようです、常に正しい答えを教えてください。このような NP 完全問題を他にいくつ解くことができますか?

私の理解では、ラドナーの定理は基本的に次のとおりです。

P！= NPは、NPIがPになく、NPIがNP完全ではない集合NPIが存在することを意味します。

P！=NPではなくP= NPと仮定すると、この定理はどうなりますか？NP中間体が存在しない場合、P=NPであることがわかります。しかし、P = NPの場合、NP中間体は存在できますか？

光学式文字認識 (OCR) は正式にはどれくらい難しいですか? 人間に匹敵するエラー許容度を想定しましょう (これは、約 98% だと思います)。

言い換えれば、問題の複雑さと扱いにくさの P/NP スケールのどこに収まるのでしょうか?

それとも、そのスケールに収まりますか？いったいどのような問題なのでしょうか。

私は、問題の複雑さの正式な定義にあまり詳しくありません。私はただ興味があります。

少なくとも 1 つの出口 (コンテナーからの) があり、車がブロックされないように、駐車場にできるだけ多くの車 (すべての車が同じサイズであると仮定) を配置するために使用するアルゴリズム (総当たりかどうか) を使用します。または、この問題をプログラムで解決した例を誰かに見せてもらえますか。

駐車場の形状が変化するのはいいことですが、不変の形状であると想定したい場合は問題ありません。

別の編集: 駐車場での走行距離は要因ではないと仮定します (ただし、駐車場内の車の数に重み付けされた要因であれば、それはまったく素晴らしいことです)。

別の編集: 2 次元を仮定します (クレーンや車の運転はありません)。

別の編集: いったん駐車すると、車を移動することはできません (係員付き駐車場ではありません)。

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

3-cnf-sat 問題を次のように変更した場合:
各 c _iについて、 c _i = -x _i1 OR -x _i2 OR x _i3は、変数の 1 つだけが否定なしで表示されることを意味します。
また、x の一部 (またはすべて) に値 (0 または 1) が与えられます。
多項式時間で問題を解決できる必要があります (問題を満たす x の値を見つけるか、問題が満たされないことを証明します)。

1. この問題を解決する多項式実行時間アルゴリズムは何ですか?
2. 多項式時間で実行されることを証明します。

ヒント: c _i = -x _i1 OR -x _i2 OR x _{i3が c = (x i1} AND -x _i2 ) -> x _i3と等しいことを示す

装身具 (ランダムな量) で満たされたx個のビンの行があるとします (各ビンにいくつの装身具があるかがわかります)。これで、自分の番になったときにどちらかの端からビンを選ぶことができる 2 人のプレーヤーがいます。彼らは順番を忘れることはできません。プレーヤーが最大限の装身具を獲得するための戦略を考え出します。

×は偶数です。

これは np 完全な問題ですか? ブールSATに似ていますか？

私が作っているゲームの場合、数字のリスト（[7、4、9、1、15、2]（Aこれにちなんで名付けられた））と別の数字のリスト（[11、18） 、14、8、3]（名前付きB）–私に提供されました。目標は、の数の合計が。の数のすべての組み合わせを見つけることAですB。例えば：

• 1 + 2 = 3
• 1 + 7 = 8
• 2 + 9 = 11
• 4 + 7 = 11
• 1 + 2 + 4 + 7 = 14
• 1 + 2 + 15 = 18
• 2 + 7 + 9 = 18

...等々。（この目的のために、はと1 + 2同じ2 + 1です。）

このような小さなリストの場合、組み合わせをブルートフォースするのは簡単ですが、これらの数が数千から数万になる可能性に直面しており、アプリケーションの存続期間にわたってこのルーチンを繰り返し使用します。100％のカバレッジで妥当な時間でこれを達成するために利用できるエレガントなアルゴリズムはありますか？これに失敗した場合、妥当な時間内に「十分に良い」組み合わせのセットを提供できる、適切なヒューリスティックを見つけることができますか？

私は、擬似コードまたはまともな人気があり読みやすい言語（そこにある「and」に注意してください....;）、またはこの種の検索の実装方法についての英語の説明でさえ、アルゴリズムを探しています。

追加するために編集：

これまでに提供された多くの良い情報。みんなありがとう！今のところ要約：

• 問題はNP完全であるため、妥当な時間で100％の精度を得るにはブルートフォースが不足することはありません。
• この問題は、サブセット和問題またはナップサック問題のいずれかの変形と見なすことができます。この問題に適応できる可能性のある、両方のよく知られたヒューリスティックがあります。

アイデアを続けてください！そして、もう一度ありがとう！

ドメイン名を構成単語と数字に分割したい

iamadomain11.com = ['i', 'am', 'a', 'domain', '11']

どうすればいいですか？複数のセットが可能である可能性があることは承知していますが、現在でも問題はなく、1 セットの可能性しかありません。

入力：グラフG出力：いくつかの独立したセット。すべての独立したセットに対するノードのメンバーシップは一意です。したがって、ノードは、それ自体のセット内のどのノードにも接続できません。パスの例を次に示します。

ここで明確化が求められたので、別の言い換え：

与えられたグラフをセットに分割して、

1. セット内のメンバーシップによって、ノードを他のすべてのノードと区別できます。たとえば、ノードiがセットAにのみ存在する場合、他のノードはセットAにのみ存在するべきではありません。

   ノードjがセットAとBに存在する場合、他のノードはセットAとBにのみ存在してはなりません。ノードのメンバーシップがビットパターンでコード化されている場合、これらのビットパターンには少なくとも1つのハミング距離があります。

2. 2つのノードがグラフ内で隣接している場合、それらは同じセットに存在してはならないため、独立したセットになります

例：Bには隣接ノードがありませんD => A、A => D

解決：

1. AB/
2. / BD

Aにはビットパターン10があり、そのセットに隣接ノードはありません。Bにはビットパターン11があり、隣接ノードはありません。Dには01があるため、すべてのノードのハミング距離は少なくとも1であり、隣接ノードはありません=>正しい

間違っています。DとAが接続されているためです。

1. ADB
2. / DB

Aのセットにはビットパターン10とDがあり、それらは隣接しています。Bにはビットパターン11があり、隣接ノードはありません。DにはBと同様に11があるため、このソリューションには2つのエラーがあるため、受け入れられません。

もちろん、少なくともlog(n)セットが必要なので、グラフ内のノードの数が増えるにつれて、これをより多くのセットに拡張する必要があります。

これにsat-solverを使用するために、私はすでにMAX-SATへの変換を作成しました。しかし、条項の数は非常に多いです。より直接的なアプローチがいいでしょう。これまでのところ近似値がありますが、正確な解または少なくともより良い近似値が必要です。

粒子群を使用して、任意のソリューションからより良いソリューションに向けて最適化するアプローチを試しました。ただし、実行時間はかなりひどく、結果は決して素晴らしいものではありません。動的アルゴリズムか何かを探していますが、この問題を分割統治する方法を理解することはできません。