我正在研究TSP。因此,我必须证明图上蛮力算法的正确性(从存在的所有置换中(从〜O(n!)中找出良好的置换)。因此,我正在学习很多书籍和网站,但是找不到如何证明正确性的方法。该证明是否存在于书籍和科学家的作品中?如果以前有人遇到过相同的问题或知道如何解决该问题,请给我建议吗?
所有蛮力算法的证明基本相同:设BF为蛮力,X为所有可能解的集合。让我们假设我们的算法BF在X中返回了x,而不是让我们矛盾地假设X中存在y,因此y是比x更好的解决方案。但是BF是一种蛮力算法,因此他将x和y进行了比较,得出x更好。矛盾。所以x比y好。
谢谢!我用类似的方法证明了算法。让我们列出所有城市排列的清单。让函数COST计算每条路径的权重。在计算完每条路径的权重之后,我们得到数组Len,其中对于城市排列列表中的i路径,存在i-weight。MIN函数查找最小路径长度和该路径的i数。由于路径列表和值数组一一对应,因此,最小成本的i位置对应于路径的i位置。因此,i是所需路径,也是最小路径。