algorithm - 非決定的アルゴリズム

Question

非決定性アルゴリズムの簡単な説明が必要です。非決定性アルゴリズムを並列プロセッサを搭載したコンピュータと比較できますか? 非決定性アルゴリズムについて誰か正確に説明してください

Answer 1

非決定論的アルゴリズムは、非決定論的チューリング マシンで実行されるアルゴリズムです。
このアルゴリズムの各計算は、同時に計算される 2 つの計算に分岐できます。

なし決定論的アルゴリズムの例:
Set Cover : 頂点のサブセットを「推測」し、それが有効なカバーかどうかを確認します。
推測は次のとおりです。各要素について、それがセット内にあり、セット内にない可能性を 1 つ確認します。

ここ（非決定論的アルゴリズム）では分岐の数が制限されていませんが、並列プロセッサでは制限されているため、これは並列プロセッサではありません。並列計算では、2^n頂点カバレッジを見つけるための OP を実行する必要がありますが、非決定論的アルゴリズムではn、nさまざまなブランチで操作のみを実行します。

非決定論的なマシンは、並列処理よりも量子コンピューターに似ています。[もちろん、P!=NP と仮定すると、量子コンピューターは依然として非決定論的チューリング マシンよりも「弱い」ことに注意してください]。