我正在尝试创建一种本地搜索试探法来解决TSP，并且此过程似乎失败了。我生成了一个随机的汉密尔顿周期并将其存储在outing []中，outgoing [i]表示起源于i的边之一指向的顶点。 distances [a] [b]表示从顶点a到顶点b的距离。但是，每当我运行此代码时，该算法不会优化我传出的哈密顿循环，而是简单地创建新的循环0-> numcities-2-> 1-> numcities-1。如果可以改善顶点到其出顶点的距离，则应该简单地反复切换出顶点。我可能忽略了一些小问题，但是我根本无法弄清楚自己做错了什么。顺便说一下，我将多次运行，这就是布尔值更改的用途。
for(int i = 0; i < numcities; i++)
{
for(int j = i+1; j < numcities; j++)
{
if(distances[i][outgoing[i]] + distances[j][outgoing[j]] > distances[i][outgoing[j]] + distances[j][outgoing[i]] && i != outgoing[j] && j != outgoing[i])
{
changed = true;
int temp = outgoing[j];
outgoing[j] = outgoing[i];
outgoing[i] = temp;
}
}
}
最佳答案
问题在于，当交换outgoing[i]和outgoing[j]时，您正在创建两个子轮廓-两个较小的循环。
例如，假设numcities=6且您的出发旅程是0 1 2 3 45。假设if语句对于i=1，j=3为true。您的代码设置了outgoing[1] = 4和outgoing[3] = 2。因此，代码认为自outgoing[1] = 4以来，游览现在为0 1 4 5。这并不完全是您要参加的旅行，但我认为这是相同的基本想法。
要解决此问题，您需要考虑游览的3个部分-（A）直至并包括城市i的部分，（B）i和j之间的部分（包括j）， （C）j之后的部分。交换边缘时，需要重新配置游览，以便（A）与以前相同，然后颠倒（B）部分，然后保持（C）部分不变。
因此，在我的示例中，零件（A）为0 1，零件（B）为2 3，零件（C）为45。折断1-2和3-4的边并重新连接后，得到的导览为0 1 3 2 4 5。
您在此处实现的被称为2-opt。您会在很多地方找到更多有关它的信息。