問題タブ [np]

NP のどの問題も決定論的な指数時間で解決できます。または、NP のどの言語も時間 2^O(n^k) で実行されるアルゴリズムによって決定できると言えます。つまり、NP ⊆ EXP

非公式に言えば、考えられる解決策を 1 つずつ試してから決定するだけです。

しかし、私が作ったアイデアのどこが悪いのかわからないという単純な例があります

ここにあります..

巡回セールスマン問題 : 無向グラフ G=(V,E) V=|n| が与えられた場合

これはよく知られた NP 完全問題であるため、実際には NP に属します。

そして、私は実行時間を分析しようとします..次のように:

考えられる解決策をすべてリストアップしただけで、(n-1) 個あります。可能なツアーの合計

次に、それらのそれぞれをチェックします。可能なツアーごとに O(n) かかります

合計実行時間は O(n!) になります

2^O(n^k)、つまり指数時間で上に制限できるようには見えません

この分析の落とし穴はどこですか？

言い換えれば、巡回セールスマン問題をどのように説明できますか? 実際には、時間 2^O(n^k) で実行されるアルゴリズムによって決定できます。

オブジェクトのセットを取り、それらを特定の領域に整理して、すべての形状を囲むボックスが最適化されるようにするアルゴリズムを作成しようとしています (使用される領域によって、または次元の 1 つに沿ってスパンを最大化するなどによって) .)。すべての形状は閉じていて境界があります。

この目的は、レーザー カッターの使用による材料の無駄を最小限に抑えることです。形状は CAD で生成され、このアルゴリズムに読み込むことができます。次に、アルゴリズムは、作業領域 (有効なレーザー切断領域) と任意の 2 つのオブジェクト間の最小間隔の引数を取得し、領域の使用を最小限に抑えながら、指定された寸法内でオブジェクトを編成しようとします。あるいは、アルゴリズムは、1 つの軸に沿ってオブジェクトの位置を最大化し、他の次元に沿ってスパンを最小化しようとすることもできます。これは、切り取るために小さなワークピースを切り離すことに似ています。

理想的には、アルゴリズムは平行移動と回転を行うことができますが、回転は必要ありません。

たとえば、この画像は必要な変換を示しています。

任意ですが、少数 (<25) のオブジェクトで動作するはずです。

最後に、誰かがこれを解決してくれるとは思っていませんが、これを実行できるアルゴリズムを見つけるか、独自のアルゴリズムを開発するための助けをいただければ幸いです。ありがとうございました。

一連の人物がいてJ、それぞれの人物の写真を撮る必要があるとします。写真家は 1 人だけであり、写真家が各写真を撮影できる回数は限られていますT( |T|> |J|)。tから引き出された任意の時点Tで、写真家は 1 枚の写真しか撮影できません。の各人Jは、 の一部の時間帯のみ写真を撮ることができますが、T各人は少なくとも 1 回は撮影できる時間を選択するよう求められています。基本的に、各人の利用可能性に基づいて、写真家は利用可能な各時間枠に 1 人を割り当てようとします。T誰もが写真を撮れるように。この問題を解決する多項式時間アルゴリズムはありますか? そうでない場合、どの非多項式時間問題が多項式時間でこの問題に還元されPますか?

例：

カメラマンは時々利用できます[1, 12, 15, 33, 45, 77]。
Aさんは時々対応可能です[12, 33]。
Bさんは時々対応可能です[1, 12]。
Cさんは時々対応可能です[1, 12]。

人物
A:33
人物B:1
人物C:12

12A: 、 B:を選択することから始めた場合1、 の場所を見つけることができませんC。つまり、バックトラックして A を に再割り当てする必要があり33ます。

基本的に、適切な時間の割り当てが存在する場合はそれを見つけ、それ以外の場合は適切な割り当てが存在しないことを報告できる多項式時間アルゴリズムを探しています。

無向グラフでソースから宛先への頂点独立パスの最大数を見つける方法は? エッジに重みはありません。プログラムは、パスの数を表示し、各パスも表示できる必要があります。

NP-Complete と NP-Hard の違いを理解しようとしています。

以下は私の理解です

NP 困難な問題は、多項式時間では解けないが、多項式時間で検証できる問題です。
NP 完全問題は、NP 内にあり、NP 困難でもある問題です。

上記の定義は正しいですか？もしそうなら、NP ではなく NP-Hard の問題についてはどうですか。それらは NP 完全問題よりも難しくないでしょうか? 指数時間でしか解決および検証できないと言うのですか?

私はいくつかのクイズ ゲームを書いていますが、プレイヤーがクイズを解けない場合、クイズの 1 つのゲームを解くコンピュータが必要です。

与えられたデータ:

1. 使用する 6 つの数字のリスト (例: 4、8、6、2、15、50)。
2. 目標値。0 < 値 < 1000 (例: 590)。
3. 利用可能な演算は、除算、加算、乗算、および除算です。
4. 括弧を使用できます。

評価が目標値に等しい、またはできるだけ近い数式を生成します。たとえば、上記の数値の場合、式は次のようになります: (6 + 4) * 50 + 15 * (8 - 2) = 590

私のアルゴリズムは次のとおりです。

1. 上記 (1) から与えられた数値のすべてのサブセットのすべての順列を生成します
2. 順列ごとに、すべての括弧と演算子の組み合わせを生成します
3. アルゴリズムの実行時に最も近い値を追跡する

上記のブルート フォース アルゴリズムに対するスマートな最適化は考えられません。これにより、桁違いに高速化されます。また、サーバー上で多くのクイズ ゲームが同時に実行されるため、最悪のケースに合わせて最適化する必要があります。

この問題を解決するために今日書かれたコードは (プロジェクトから抽出された関連するもの) です:

((((4*6)+50)*8)-2) と表示されます。さまざまな値で少しテストしたところ、正しく動作しているようです。また、不要な括弧を削除する機能もありますが、質問と関係ないので掲載しません。

問題は、このすべての順列、組み合わせ、および評価のために、これが非常に遅く実行されることです。私の mac book air では、1 つの例で数分間実行されます。サーバー上で同時に多くのクイズゲームインスタンスが実行されるため、同じマシン上で数秒で実行できるようにしたいと考えています。質問は次のとおりです。

1. 現在のアルゴリズムを何らかの方法で (桁違いに) 高速化できますか?
2. この問題に対して、はるかに高速に実行される他のアルゴリズムがありませんか?

このためのアルゴリズムは存在しますか、それとも誰かが私を正しい方向に向けることができますか?

画像を持つユーザーの優先セットがあります。各画像の比率は 3:4、4:3、または 1:1 です。各ユーザーは、比率が異なる優先順位の異なる一連の画像を持っています。ギャップがゼロの無限スクロール xy 軸コラージュを作成したいと考えています。さまざまな形状の 2D ビン パッキングは NP 困難ですが、これを簡単にする「チート」がいくつかあります。

1. 各形状には、大、中、小の 3 つのサイズがあります (たとえば、3:4 には 3:4 大、3:4 中、3:4 小)。
2. コラージュ全体が任意の形状に収まる必要はありません。視聴者には端が見えないためです (無限スクロールです)。
3. 長方形、正方形以外の形状は、+/- 10 ピクセルで調整できます。新しい形状に合わせて、反対側 (幅または長さ) を拡大およびトリミングします。これにより、最大 20px のギャップをクリアできます。
4. すべての形状の間に 15 ～ 25 ピクセルの固定境界線が必要です。この境界線のサイズは変更できません。

これらのパラメーターを使用して、形状のグリッドを視覚的に構築することができました。私はこれらの 9 つのサイズから始めました: http://cl.ly/image/08373b0r311Lと 20px の境界線。次に、超大きな長方形に収まる「スーパー パターン」を使用して、コラージュ ( http://cl.ly/image/3h462O3i3k47 ) を作成しました。赤い形状は 3:4 の形状であり、+/- 10px でパディングされていることに注意してください。この場合、3:4 の画像をパディングするだけで済みました。

皆さんが提供できる助けをありがとう:)