虽然语言不可知,但本教程很好,并提供了几个可能提供必要直觉的示例.
也就是说,回溯背后的想法根本不难理解.回溯算法基本上就像执行蛮力一样探索所有解空间,除了(这使得它更有效)它一旦意识到它不可行就从部分解回溯.
一个例子
考虑这个众所周知的八皇后问题的部分解决方案.
前四列中的皇后已经定位,但最后一列中的皇后位于无效方格中.一个强力解决方案将继续为其余的列放置皇后,而忽略了这样一个事实:无论这个部分解决方案如何被增强,结果都将是无效的.
回溯算法将"更智能":它将意识到第四个女王被错误地放置并且"回去"考虑其他方块.
- @ScottSchulthess https://web.archive.org/web/20140716033908/http://web.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html (3认同)
- 您链接的示例现在不见了 (2认同)
| 归档时间： |
|
| 查看次数： |
8914 次 |
| 最近记录： |