修剪：何時停止？

修剪在深度優先搜索中何時有效？我一直在研究一種有效的方法來解決N皇后問題，我正在第一次考慮修剪。我已經爲前兩行實現了它，但是它何時會停止高效？我應該修剪多遠？修剪：何時停止？

2010-04-23 cam

確定我想你應該更詳細地描述你的算法。我不確定修剪是什麼意思。它永遠不會停止高效率地拒絕你認爲肯定會導致死路一條的路徑。 – IVlad 2010-04-23 20:30:27

N皇后問題通常是遞歸的。在一個深度實施修剪應該意味着在任何深度實施修剪。

答案取決於你在做什麼樣的修剪。如果您修剪對稱移動，那麼當檢查的成本高於評估整個分支的成本乘以分支對稱的可能性時，它不值得修剪。對於N皇后問題，在前兩行之後對稱可能不是一個非常有效的修剪方法。

2010-04-23 20:36:42 Geoff

我曾經看到過這樣的一句話：「早熟的西梅;經常的西梅。」另一種說法是：「不要做任何愚蠢的事情，不要做任何事情。」

我認爲，修剪的，你做的量應該由你的目標的問題，或者您的邊界上N.

2010-04-23 23:51:55 hehewaffles

回答