Tag: 旅行推销员

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(); […]