一律コスト検索アルゴリズム

Question

私は本とウィキペディアでそれについて読んでいましたが、まだそれを100％理解していません。

誰かが例を挙げて説明できるのであれば、本当に感謝します。私はあなたがthis Wikipedia page見ていたと仮定し

おかげ

Answer 1

。つまり、2つの数値を加算したり、2つの数値を比較したり、メモリからデータを取得したりするなど、所与の演算に必要な時間は、関係する変数のサイズとは無関係です。換言すれば、8ビット比較は32ビット比較と同じ時間量を要する。この前提を実現することで、効率の分析を簡素化し、実装の詳細に陥ることなくアルゴリズムを比較することができます。

Answer 2

私は街のブロックの近くのピザの場所を探して地図を見ています。私が使用できるいくつかの戦略：

• Breadth first search（BFS）：ピザの場所が見つかるまで、ブロックの周りのブロックの同心円を外側から見てください。これは、カラスが飛ぶように私のブロックに最も近いピザの場所の一つを私に与えるでしょう。
• 奥行き最初の検索（DFS）：行き止まりになるまで道をたどり、その後逆戻りします。最終的にすべての可能なブランチが検索されるので、どこかにピザの場所があれば、それを見つけることができますが、おそらく私のブロックの近くにはありません。
• ユニフォーム・コスト・サーチ（UCS）：一部の通りで交通が悪いと言われています。私はその街をよく知っています。任意の所在地について、私はブロックからそこに着くまでどれくらいの時間がかかると言えるでしょう。だから地図を見て、最初に私は1分以内に行くにはすべてのブロックを検索します。私はまだピザの場所を見つけていない場合、私は1〜2分の間に私を連れて行くすべてのブロックを検索します。ピザの場所が見つかるまで、このプロセスを繰り返します。これは、私のブロックから最も近いドライブであるピザの場所の一つを私に与えます。 BFSが同心円のように見えるのと同様に、UFSはa contour mapのようになります。

通常、優先順位キューを使用してUCSを実装し、コストを最小限に抑えてノードを検索します。