問題タブ [np]

たとえば、集合カバー決定問題は NP 完全問題として知られています。この問題の入力は、ユニバース U、U のサブセットのファミリ S、および整数 k () です。

私が混乱していることの 1 つは、k=1 とすると、S の各要素をチェックするだけで、明らかに時間 |S| で問題を解決できるということです。より一般的には、k が定数の場合、問題は次のようになります。 |S| の多項式時間で解かれます。このように、|S|/2、|S|/3... のように、k も |S| とともに増加する場合にのみ、時間計算量は指数関数的に高くなります。

だからここに私の質問があります：

1. 私の現在の理解では、NP 完全問題の時間計算量の測定は、最悪のケースで測定されます。理解が正しいかどうか誰か教えてください。

2. 私は誰かが別の問題が NP 困難であることを証明するのを見ました<U,S,|U|/3>。なぜ彼は??<U,S,|U|/3>ではなく、だけを証明したのだろうと思っています。<U,S,ARBITRARY k>そのような証拠は信頼できますか？

どうもありがとう！

次の問題が NP-Complete であるかどうか、またはそれを解決する特定のアルゴリズムがあるかどうかを知りたいです。

たとえば、特定の金額 (0.01 ユーロ、0.05 ユーロ、5.00 ユーロなど) の硬貨や手形が 30 ユーロあるとします。

私たちが持っているコインと紙幣の量が与えられ、あなたはそれを何人かの人々 A、B、Cなどに分配しなければなりません.

Aには一定の金額 (たとえば 10 ユーロ) を持たせ、B には異なる金額または同じ金額を持たせたいとします。

「要求された」お金の合計は、私たちが持っているお金より大きくありません。

したがって、質問は次のとおりです。is there a distribution of coins and bills such that every person has the quantity of money that belongs to him?

前もって感謝します！

概念を理解しているように感じますが、受け入れアルゴリズムと決定アルゴリズムを区別できないようです。私は現在、「アルゴリズムの紹介」(コーメン) を読んでいますが、次の章の NP 完全性に問題があります。

「チューリングの停止問題などの他の問題については、受け入れアルゴリズムは存在しますが、決定アルゴリズムは存在しません」。

これは私にとってこの時点までは理にかなっていますが、さらに進んで次のように言います。

そして、P も

「言語のクラスは多項式時間アルゴリズムによって決定されるため、L が多項式時間アルゴリズムによって受け入れられる場合、多項式時間アルゴリズムによって決定されることを示すだけで済みます。」.

次に、受け入れアルゴリズムの動作をさらに検査し、前のアルゴリズムが入力を受け入れた場合は 1 を、そうでない場合は 0 を出力する受け入れアルゴリズムのシミュレーションを作成します。

しかし、そのようなアルゴリズムを構築できる場合、停止問題に決定アル​​ゴリズムがなく、受け入れアルゴリズムがある可能性はありますか?

ウィキペディアで、この図を見つけました。p=np という仮定の下で、p=np=np-complete を取得する方法がわかりません。

点 D から R までの最短経路を見つけなければなりません。これらは不動点です。これは状況の例です:

ボックスには壁も含まれており、壊さない限り通り抜けることはできません。壁を壊すたびにコストがかかります。たとえば、「a」ポイントとしましょう。ここで、「a」は正の整数です。壁を必要としない各移動には、1 ポイントかかります。

使命は、最小コストのすべてのパスから、壊れた壁の数が最も少ないパスを見つけることです。

ボックスの幅は最大で 100 セルになるため、バックトラッキングを使用する必要はありません。遅すぎる。私が思いついた唯一の解決策はこれです：

1. 壁がなければ東か南に行く
2. 南に壁がある場合は、西に壁があるかどうかを確認します。西に壁がある場合は、南の壁を壊します。西に壁がない場合は、壁のない南のセルが見つかるまで西に進みます。このプロセスを南と東で、この順序で壊れた壁のコストを超えるまで繰り返します。西からのパスが南の壁を壊したのと同じ場所に入り、コストが「a」ポイント以下の場合は、このパスを使用し、そうでない場合は南の壁を破ります。
3. 上に何もない場合は、ボックスの境界に応じて、南または東の壁にブレーキをかけます。

「乗客」が点 R に到着するまで、手順 1、2、3 を繰り返します。これら 3 つの手順の間には、「else-if」関係があります。

より良い問題アルゴリズムを思い付くことができますか? C++でプログラミングしています。

これはコーディングの問題に関するインターンシップの面接の質問であるため、回答を探しているわけではありません。むしろ、正しい方向に向かうための手がかりを探しています。

基本的に、ユーザーは 2 つのパラメーターを入力します。アイテムの数と価格ポイント。たとえば、ユーザーがアイテムに 3 と価格ポイントに $150 を入力した場合、アルゴリズムは価格ポイント 150 に近いできるだけ多くの組み合わせを見つける必要があります。

私はこの問題について真剣に考えました。私の最初の試みは、価格をアイテムの総数で割ることでした。しかし、この回答では、各アイテムの範囲が制限されているだけです。

この質問は P NP タイプの質問ですか?

Subgraph Isomorphism (SI) 問題は、2 つのグラフ G と H が入力として与えられる計算タスクであり、G に H と同型のサブグラフが含まれているかどうかを判断する必要があります。

これはNP 完全問題です。

SAT問題との関係を知りたいです。特に、この問題のインスタンスを SAT ソルバー ( miniSAT
など) 全体で解決できるようにしたいと考えています。SI から SAT 問題へのマッピングを多項式時間で実行できるアルゴリズムが必要であり、SAT 割り当てを使用してノードからマッピングを見つけることができます。 G から H のノードへ。

何か案が ？？？