When does pruning stop being efficient in a depth-first search? I've been working on an efficient method to solve the N-Queens problem and I'm looking at pruning for the first time. I've implemented it for the first two rows, but when does it stop being efficient? How far should I prune to?
2 に答える
4
N-Queensの問題は、通常、再帰的です。ある深さで剪定を実装することは、任意の深さでそれを実装することを意味するはずです。
答えは、実行している剪定の種類によって異なります。対称移動を剪定する場合、チェックのコストがブランチ全体の評価のコストにブランチが対称である確率を掛けたものよりも大きい場合は、剪定する価値がありません。N-Queensの問題の場合、対称性は、最初の2行以降の剪定方法としてはあまり効果的ではない可能性があります。
于 2010-04-23T20:36:42.933 に答える
1
私はかつてこれに関する引用を見ました、「早く剪定しなさい;頻繁に剪定しなさい」。そしてもう1つは、「愚かなことは何もしないでください。2回は何もしないでください」。
あなたが行う剪定の量は、問題の目標、またはNの境界によって決定されるべきだと思います。
于 2010-04-23T23:51:55.187 に答える