温馨提示:本文翻译自stackoverflow.com,查看原文请点击:complexity theory - How I can show the correctness of brute-force TSP algorithm?
complexity-theory graph-theory traveling-salesman brute-force

complexity theory - 如何显示蛮力TSP算法的正确性?

发布于 2020-07-06 00:02:04

我正在研究TSP。因此,我必须证明图上蛮力算法的正确性(从存在的所有置换中(从〜O(n!)中找出良好的置换)。因此,我正在学习很多书籍和网站,但是找不到如何证明正确性的方法。该证明是否存在于书籍和科学家的作品中?如果以前有人遇到过相同的问题或知道如何解决该问题,请给我建议吗?

查看更多

提问者
aristari
被浏览
21
Ido 2020-04-17 05:41

所有蛮力算法的证明基本相同:设BF为蛮力,X为所有可能解的集合。让我们假设我们的算法BF在X中返回了x,而不是让我们矛盾地假设X中存在y,因此y是比x更好的解决方案。但是BF是一种蛮力算法,因此他将x和y进行了比较,得出x更好。矛盾。所以x比y好。