だから私は少なくとも2人の教授に、バックトラッキングはアルゴリズムを非決定論的にするが、それがなぜであるかについてあまり説明しないと述べた。これがどのように起こるかは理解していると思いますが、言葉で表現するのに苦労しています。誰かが私にこれの理由の簡潔な説明を教えてもらえますか？
2822 次
9 に答える
14
バックトラッキングによってアルゴリズムが非決定論的になることはそれほど多くありません。
むしろ、（非決定論的の定義により）処理の特定の時間にどのパスを取るべきかわからないため、通常、非決定論的アルゴリズムを処理するためにバックトラックが必要ですが、代わりにいくつかを試す必要があります。
于 2009-02-01T06:03:50.300 に答える
9
ウィキペディアを引用します：
非決定論的プログラミング言語は、プログラムの特定のポイント（「選択ポイント」と呼ばれる）で、プログラムフローのさまざまな代替手段を指定できる言語です。if-thenステートメントとは異なり、これらの選択肢から選択する方法は、プログラマーによって直接指定されません。プログラムは、実行時に、すべての選択ポイントに適用される一般的な方法を使用して、選択肢を決定する必要があります。プログラマーは限られた数の選択肢を指定しますが、プログラムは後でそれらの中から選択する必要があります。（「Choose」は、実際には、非決定論的演算子の一般的な名前です。）選択ポイントの階層が形成され、上位レベルの選択肢が、下位レベルの選択肢を含むブランチにつながる場合があります。
選択の1つの方法は、バックトラッキングシステムで具体化されます。このシステムでは、一部の代替手段が「失敗」し、プログラムがバックトラックして他の代替手段を試行する可能性があります。すべての選択肢が特定の選択ポイントで失敗した場合、ブランチ全体が失敗し、プログラムはさらに古い選択ポイントに戻ります。複雑な点の1つは、選択は暫定的であり、再作成される可能性があるため、システムは、最終的に失敗したブランチを部分的に実行することによって引き起こされる副作用を元に戻すことによって、古いプログラム状態を復元できなければならないことです。
非決定論的プログラミングの記事から。
于 2009-02-01T05:54:16.497 に答える
6
世界地図を着色するためのアルゴリズムを考えてみましょう。隣接する国では色を使用できません。アルゴリズムは国から任意に開始し、任意の色に色付けします。それで、それは動き、国を着色し、「ええと」、2つの隣接する国が同じ色になるまで、各ステップで色を変更します。さて、今、私たちはバックトラックして、新しい色の選択をしなければなりません。現在、非決定性アルゴリズムのように選択を行っていません。これは、決定性コンピューターでは不可能です。代わりに、バックトラッキングを使用して非決定論的アルゴリズムをシミュレートしています。非決定論的アルゴリズムは、すべての国にとって正しい選択をしたでしょう。
于 2009-02-01T06:05:16.023 に答える
4
決定論的コンピュータでのバックトラックの実行時間は階乗です。つまり、O(n!) です。
非決定論的コンピューターが各ステップで即座に正しく推測できたのに対し、決定論的コンピューターは可能な選択肢のすべての組み合わせを試す必要があります。
非決定論的なコンピューターを構築することは不可能であるため、教授の意図はおそらく次のとおりです。
複雑性クラス NP で証明されている困難な問題 (非決定論的コンピューターが常に正しく推測することによって効率的に解決できるすべての問題) は、バックトラックよりも実際のコンピューターでより効率的に解決することはできません。
上記のステートメントは、複雑度クラス P (決定論的コンピューターが効率的に解決できるすべての問題) と NP が同じでない場合に当てはまります。これは有名な P 対 NP 問題です。Clay Mathematics Institute は、その解決策に対して 100 万ドルの賞金を提供しましたが、この問題は何年もの間証明されませんでした。ただし、ほとんどの研究者は、P は NP と等しくないと考えています。
簡単にまとめると次のようになります: 非決定論的コンピュータが常に正しく推測することで効率的に解決できる最も興味深い問題は、非常に難しいため、決定論的コンピュータは可能な選択肢のすべての組み合わせを試す必要があります。つまり、バックトラッキングを使用します。
于 2009-02-02T19:53:46.067 に答える
1
思考実験:
1) 視界から隠されている電荷の分布があり、そこから力を感じ、それらが作り出すポテンシャル場を測定します。すべての電荷の位置を正確に教えてください。
2) いくつかの料金を取り、それらを手配します。彼らが作り出す可能性のあるフィールドを正確に教えてください。
2 番目の質問だけが固有の回答を持っています。これは、ベクトル フィールドの非一意性です。この状況は、検討しているいくつかの非決定論的アルゴリズムと類似している可能性があります。不連続点に近づく方向によって答えが異なるため、存在しない数学の制限をさらに検討してください。
于 2009-02-01T06:53:40.807 に答える
0
バックトラッキングを許可すると、プログラムで無限ループが許可され、実際のパスには常にもう 1 つのループが含まれる可能性があるため、非決定的になります。
于 2009-02-01T07:44:49.627 に答える
0
迷路のアナロジーが好きです。簡単にするために、迷路を 1 つのパスしかないバイナリ ツリーと考えてみましょう。
ここで、深さ優先検索を試して、迷路から抜け出す正しい方法を見つけたいと考えています。
非決定論的コンピューターは、すべての分岐点で自分自身を複製/複製し、さらにそれぞれの計算を並行して実行します。あたかも迷路の中の人が各分岐点で (映画プレステージのように) 自分自身を複製/クローンし、自分自身の 1 つのコピーをツリーの左側のサブブランチに送信し、自分自身の別のコピーをツリーの右側のサブブランチに送信するようなものです。木。
行き止まりにたどり着いたコンピューター/人は死ぬ (応答なしに終了する)。
生き残るのは、迷路を抜けたコンピュータ 1 台だけです (回答で終了します)。
バックトラッキングと非決定論の違いは次のとおりです。
バックトラックの場合、任意の時点で生きているコンピュータは 1 つだけです。彼は伝統的な迷路を解くトリックを実行し、チョークでパスをマークするだけで、行き止まりに到達すると、サブブランチを持つ分岐点にバックトラックするだけです。深さ優先探索のように、彼はまだ完全に探索していませんでした。
対照的に ：
非決定論的コンピューターは、すべての分岐点で自分自身を複製し、サブブランチで並列検索を実行して出口をチェックできます。
したがって、バックトラッキング アルゴリズムは、シーケンシャル/非並列/決定論的コンピューター上で非決定論的コンピューターの複製能力をシミュレート/エミュレートします。
于 2014-10-31T18:59:37.473 に答える
0
非決定論的チューリング マシン (NDTM) は、1 つのステップで複数の分岐を取ることができます。一方、DTM は試行錯誤のプロセスに従います。
DTM は通常のコンピューターと考えることができます。対照的に、量子コンピューターは NDTM に似ており、非決定論的な問題をはるかに簡単に解決できます (たとえば、暗号の解読におけるそれらのアプリケーションを参照してください)。したがって、後戻りは実際には直線的なプロセスになります。
于 2009-02-01T10:04:07.553 に答える