algorithm - バックトラッキングアルゴリズム

Question

バックトラッキングアルゴリズムの計算コストに重みの順序はどのように影響しますか? ノード数と探索木の数は同じだけど、無秩序だともっと時間がかかるので何とかしている。

ありがとう！

Answer 1

バックトラッキング アルゴリズムでは、特定のブランチが答えではないことがわかっている場合、それをトリムすることができます。これは、ゲームのエージェントでは非常に一般的であり、アルファ ベータ プランニングと呼ばれます。

したがって、訪問したノードを並べ替えると、プルーニング率を上げて、回答の正確さに影響を与えることなく、実際に訪問するノードの数を減らすことができます。

もう 1 つの可能性 - プルーニングがない場合は、キャッシュのパフォーマンスです。ツリーが配列として格納される場合があります [特に完全なツリー]。配列は、「ランダムにジャンプ」するのではなく、反復するときに最も効率的です。並べ替えによってこの動作が変更される可能性があり、その結果、キャッシュの動作が良くなったり悪くなったりします。