我知道 DP 为许多 NP 完全问题(如 TSP)提供了更好的性能。虽然需要的空间很大，但它很好地降低了复杂性。
但我无法理解分支限界和回溯与暴力搜索相比的效率。
在最坏的情况下，蛮力等于 b&b 还是回溯？
最佳答案
通过穷举搜索，您将计算所有 N!节点之间的可能路径。通过回溯，您可能会计算出访问一半节点的路线，注意到它已经比目前找到的最佳路线更昂贵，并在此时停止调查该部分路线。通过这样做，您已经跳过计算通过完成该部分路线而产生的所有路线，从而节省了穷举搜索的时间，后者将继续检查所有路线。
关于performance - 使用回溯和分支定界的优势，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10060379/