Java中旅行商问题的强力算法 [英] Brute force algorithm for the Traveling Salesman Problem in Java

问题描述

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

I'm working on a project for a math class at school, and I chose to do mine on the Traveling Salesman Problem, something I've always wanted to investigate more. However, I'm having problems with my brute force solving algorithm.

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

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

SKIP THIS PARAGRAPH IF YOU KNOW WHAT THE TRAVELING SALESMAN PROBLEM IS: To summarize as much as possible, the TSP goes like this: You are a salesman who wants to visit each city in a region (a city is essentially a point on a map). There are 'n' cities in the bounded x and y region, and each city is connected to each city (by assume a straight road). You need to find the shortest possible route among the cities that allows you to visit each city.One of the algorithms I want to use (and I will need to test other algorithms) is Brute Force, which checks every possible route and returns the shortest route. The reason this is not always used is because it requires us to check (n-1)! possible routes, and that number gets huge as 'n' increases- in fact, with just 50 cities, that would be 608281864034267560872252163321295376887552831379210240000000000 routes to check.

将承担所有关于我们将要使用4个城市的任意区域的事件的例子（即使算法可以处理n个城市。我们也不关心距离 - 我们想要达到每个可能的路线蛮力）。

ASSUME FOR ALL EXAMPLES TALKED ABOUT IN THIS POST THAT WE ARE GOING TO BE USING AN ARBITRARY REGION WITH 4 CITIES (even though the algorithm can handle n cities. also we don't care about distances- we want to hit every possible route in brute force).

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

Here is a simple picture demoing what I'm talking about (4 cities is what I'm starting with to check if the process is working properly)

城市地图图片

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

Here is the Brute Force algorithm (assume all other called methods work correctly, because they do):

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

(check below for a bit more explanation)

[code]

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<City> citiesNotInRoute = new ArrayList<City>();
            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");

    }

这是我的逻辑：
（注意： city对象有一个名为visited的flag布尔变量。

Here is my logic: (Note: a city object has a "flag" boolean variable called "visited")

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

• 从1个未标记城市的路线开始。


• 标记最后一个未标记的城市（这个城市是枢纽）


• 查找每个城市不在路上R，以及将其添加到新路线。


• 以递归方式在每条路线上调用BruteForce方法。

• begin with route with 1 unflagged city.
• flag the "last unflagged" city (this city is "pivot")
• Find each city that is "NOT IN ROUTE R", and add it to a new route.
• recursively call the BruteForce method on each of these routes.

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

• 标记最后一个城市

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

• 看看这是否是最短的路线 - 如果是，将其存储在全局变量中

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

This image will help me explain the problem... So the program correctly goes down the left side. However, after it gets to the bottom, one would expect the recursion to jump back up to step4, which it does. However, instead of R having city A flagged and city B unflagged and then recursively calling itself on the "new route" containing Aflag and B, R now has all 4 cities included, and all 4 are flagged. It fails because it adds city D again to "newRoute", recursively calls itself again, and in another method we get an array out of bounds error because there aren't 5 cities in my region, but there incorrectly are 5 cities in route r (A,B,C,D,D).

有用的递归图片树结构

问题与在循环中调用递归或在递归调用中引用'r'有关。

The problem has something to do with calling recursion in the loop, or route 'r' being referenced within a recursive call.

如果您知道我需要做什么，我会非常感谢您的帮助。

If you have any idea what I need to do, I would SERIOUSLY appreciate some help.

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

Thanks to anyone who will help me out. I will send the whole project to anyone who is willing to help as well.

更新

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

Alright, so I have attempted to shorten and simplify my original method, and this is what I have:

public void BruteForceFindBestRoute(Route r, ArrayList<City> 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;
        }

    }

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

The problem is that the variable i inside the for loop seems to lose it's meaning when we break out of the recursion, and the loop is not continued. Ideas?

推荐答案

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

You should remove cities from the route after the recursive call returns. You do this:

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

但绝不是 newRoute.removeFromRoute 或类似。

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

Note that you are writing Java, and in Java, an assignment of an object is done by reference. Which means that r and newRoute are the same object. newRoute is not an independent copy of r as you might expect. So any modification to newRoute will change r as well. You might want to explicitely copy your route there. The Java term for this is clone. Make sure your clone is deep enough, i.e. you clone all relevant data structures, instead of sharing them between the original and its clone.

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

Note: There are many places where you might make your code more efficient, but as brute force is far from efficient in any case, and you're only talking about few cities, perhaps you don't have to care. If you want to investigate alternatives, though, consider maintaining a single linked list of all unvisited cities. Each call would loop over that list, remove an element, recurse and put the element back. No need to build this list from scratch in each invocation. The idea of dancing links could be neatly applied to this task, as an alternative to premade linked list implementations.

编辑：

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

The following variation of your code works for me:

import java.util.*;

class SO11703827 {

    private static ArrayList<Integer> bestRoute;

    public static void bruteForceFindBestRoute
        (ArrayList<Integer> r,
         ArrayList<Integer> citiesNotInRoute)
    {
        if(!citiesNotInRoute.isEmpty())
        {
            for(int i = 0; i<citiesNotInRoute.size(); i++)
            {
                Integer justRemoved =
                    (Integer) citiesNotInRoute.remove(0);
                ArrayList<Integer> newRoute =
                    (ArrayList<Integer>) 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<Integer> r) {
        System.out.println(r.toString());
        return false;
    }

    public static void main(String[] args) {
        ArrayList<Integer> lst = new ArrayList<Integer>();
        for (int i = 0; i < 6; ++i)
            lst.add(i);
        ArrayList<Integer> route = new ArrayList<Integer>();
        bruteForceFindBestRoute(route, lst);
    }
}

这篇关于Java中旅行商问题的强力算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！