Java中旅行商问题的powershell算法

我正在为学校的数学课做一个项目，我选择了我的旅行推销员问题，我一直想调查更多。 但是，我的蛮力解算算法存在问题。

* 请转到底部的更新以查看最新版本的代码

---

---

如果您知道旅行销售员问题是什么，请跳过此段：尽可能总结一下，TSP是这样的：您是一个想要访问某个地区的每个城市的推销员（一个城市基本上是地图上的一个点） 。 在有界x和y区域中有’n’个城市，每个城市都与每个城市相连（通过直线道路）。 您需要在城市中找到允许您访问每个城市的最短路径。我想要使用的其中一种算法（我需要测试其他算法）是Brute Force，它检查每条可能的路线并返回最短的路线路线。 这并不总是使用的原因是因为它需要我们检查（n-1）！ 可能的路线，随着’n’的增加，这个数字会变得很大 – 事实上，只有50个城市，那将是608281864034267560872252163321295376887552831379210240000000000路线要检查。

假设我们将使用4个城市的任意区域 （尽管该算法可以处理n个城市。我们也不关心距离 – 我们希望以粗暴的方式击中每条可能的路线）力）。

这是一个简单的图片演示我正在谈论的内容（4个城市是我开始检查过程是否正常工作）

与城市的地图的图片

这是Brute Force算法（假设所有其他被调用的方法都正常工作，因为他们这样做）：

（请查看下面的更多解释）

[码]

public void BruteForceFindBestRoute(Route r) //Must start r having 1 unflagged city to begin with { if(!r.allFlagged() && r.route.size() != m.cities.size()) { /*STEP 1 Begin with last unflagged city*/ City pivot = r.lastCityAdded(); /*STEP 2: Flag city*/ pivot.visited = true; /*STEP 3: Find cities "NOT IN ROUTE"*/ ArrayList citiesNotInRoute = new ArrayList(); for(int i = 0; i<m.cities.size(); i++) { if(!r.isCityInRoute(m.cities.get(i).name)) { citiesNotInRoute.add(m.cities.get(i)); } } /*STEP 4: Recursively call BruteForceFindBestRoute() using these cities added to the end of our original route*/ for(int i = 0; i<citiesNotInRoute.size(); i++) { Route newRoute = r; newRoute.addToRoute(citiesNotInRoute.get(i)); BruteForceFindBestRoute(newRoute); } } /*STEP 5: If the route is full but the last city isn't flagged, then flag it call BruteForceFindBestRoute() again, with the last city flagged*/ else if(!r.allFlagged() && r.route.size() == m.cities.size()) { if(r.allFlaggedButLast()) { Route x = r; x.flagLastCity(); BruteForceFindBestRoute(x); } } /*STEP 6: If all cities are flagged, the route is full. Check to see if it's the best route.*/ else if(r.allFlagged()) { if(IsBestRoute(r)) bestRoute = r; } else System.err.println("Error: somehow all cities got flagged, but the route isn't full"); } 

这是我的逻辑:(注意：一个城市对象有一个名为“visited”的“flag”布尔变量）

（如果所有路线都没有标记，并且路线不包含每个可能的城市）

• 以1个未标记城市的路线开始。
• 标志着“最后一个没有标志”的城市（这个城市是“枢纽”）
• 找到“NOT IN ROUTE R”的每个城市，并将其添加到新路线。
• 在每个路由上递归调用BruteForce方法。

（如果所有路线都没有标记，但路线包含每个城市）

• 标记最后一个城市

（否则……这意味着路线标记每个城市并包含每个可能的城市）

• 看看这是否是最短路径 – 如果是，则将其存储在全局变量中

这个图像将帮助我解释问题…所以程序正确地向左侧。 然而，在它到达底部之后，人们会期望递归跳回到步骤4，它会这样做。 但是，不是R标记城市A而城市B未标记，然后在包含Aflag和B的“新路线”上递归调用自身，R现在包含所有4个城市，并且所有4个都被标记。 它失败了，因为它再次将城市D添加到“newRoute”，递归地再次调用自身，而在另一种方法中，我们得到一个数组越界错误，因为我的区域中没有5个城市，但错误地是路线r中的5个城市（A，B，C，d，d）。

递归树结构的有用图片

该问题与在循环中调用递归或在递归调用中引用’r’的路由有关。

如果你知道我需要做什么，我会非常感激一些帮助。

感谢任何能帮助我的人。 我会将整个项目发送给任何愿意提供帮助的人。

---

UPDATE

好吧，所以我试图缩短和简化我的原始方法，这就是我所拥有的：

 public void BruteForceFindBestRoute(Route r, ArrayList citiesNotInRoute) { if(!citiesNotInRoute.isEmpty()) { for(int i = 0; i<citiesNotInRoute.size(); i++) { City justRemoved = (City) citiesNotInRoute.remove(0).clone(); Route newRoute = (Route) r.clone(); newRoute.addToRoute(justRemoved); BruteForceFindBestRoute(newRoute, citiesNotInRoute); citiesNotInRoute.add(justRemoved); } } else //if(citiesNotInRoute.isEmpty()) { if(IsBestRoute(r)) bestRoute = r; } } 

问题是，当我们突破递归时，for循环中的变量i似乎失去了它的意义，并且循环不会继续。 想法？

Answer 1

在递归调用返回后，您应该从路由中删除城市。 你做这个：

  Route newRoute = r; newRoute.addToRoute(citiesNotInRoute.get(i)); BruteForceFindBestRoute(newRoute); 

但从来没有一个新的newRoute.removeFromRoute 。 newRoute.removeFromRoute或类似的东西。

请注意，您正在编写Java，而在Java中，对象的赋值是通过引用完成的 。 这意味着r和newRoute是同一个对象 。 newRoute不是您所期望的r的独立副本。 所以对newRoute任何修改也会改变r 。 您可能希望明确地复制您的路线。 Java的术语是克隆 。 确保您的克隆足够深，即克隆所有相关数据结构，而不是在原始克隆和克隆之间共享它们。

注意：在很多地方你可以使你的代码更有效率，但是在任何情况下蛮力都远没有效率，而你只是谈论几个城市，也许你不必关心。 但是，如果您想调查替代方案，请考虑维护所有未访问城市的单个链接列表。 每个调用都会循环遍历该列表，删除一个元素，递归并将元素放回。 无需在每次调用时从头开始构建此列表。 跳舞链接的想法可以巧妙地应用于此任务，作为预制链表实现的替代方案。

编辑：

您的代码的以下变体适合我：

 import java.util.*; class SO11703827 { private static ArrayList bestRoute; public static void bruteForceFindBestRoute (ArrayList r, ArrayList citiesNotInRoute) { if(!citiesNotInRoute.isEmpty()) { for(int i = 0; i newRoute = (ArrayList) r.clone(); newRoute.add(justRemoved); bruteForceFindBestRoute(newRoute, citiesNotInRoute); citiesNotInRoute.add(justRemoved); } } else //if(citiesNotInRoute.isEmpty()) { if(isBestRoute(r)) bestRoute = r; } } private static boolean isBestRoute(ArrayList r) { System.out.println(r.toString()); return false; } public static void main(String[] args) { ArrayList lst = new ArrayList(); for (int i = 0; i < 6; ++i) lst.add(i); ArrayList route = new ArrayList(); bruteForceFindBestRoute(route, lst); } }