蛮力算法在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.

* 请去更新在底部查看最新版本的code

跳过这一段，如果你知道旅行商问题是： 总之尽可能的TSP是这样的：你是一个推销员谁想要访问每一个城市在一个地区（城市基本上是在地图上的一个点）。有'N'个城市中的有界x和y区域，并且每个城市连接到每个城市（通过假设直线道路）。你需要找到城市之间最短的路线，它允许您访问我想使用的算法在每次city.One（我将需要测试的其它算法）是蛮力，检查每一个可能的路径，并返回最短路线。究其原因，这是不经常使用，因为它需要我们检查（N-1）！可能的途径，而且这个数字得到巨大的'N'increases-事实上，只有50个城市，这将是608​​281864034267560872252163321295376887552831379210240000000000路线查询。

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).

下面是一个简单的图片demoing什么，我说什么（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)

与城市地图画面

下面是蛮力算法（假设其他所有调用的方法可以正常工作，因为他们做的）：

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");

    }

下面是我的逻辑： （注：一个城市的对象有所谓的参观标志布尔变量）

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

（如果所有的路由不标记，并且如果该路由不包含每个可能的地点）的

• 在开始与1未标记的城市路线。
• 标记的最后的旗标的城市（这个城市是支点）
• 找到每一个城市，是NOT IN ROUTE R，并将其添加到一个新的途径。
• 递归调用暴力破解的方法对这些路线。

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

• 标记的最后一个城市

（否则......这意味着航线都有每个城市的标记，并包含每一个可能的城市）的

• 看看这是最短的为route-如果是，将其存储在全局变量

这个形象将帮我解释一下这个问题？ 所以程序正确地下降的左侧。然而，在它到达底部，人们所期望的递归跳回至步骤4，它确实。然而，而不是让城市R A和标记B市旗标，然后递归调用本身含有AFLAG和B的新干线，R目前拥有4个城市包括在内，所有4个被标记。它失败，因为它再添D市为newRoute，再次递归调用自身，而在另一种方法，我们得到一个数组越界错误，因为不会有5个城市在我的地区，但也有不正确的有5个城市的路径R （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.

如果您有任何想法，我需要做的，我会认真AP preciate一些帮助。

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内部的循环似乎失去它的意思是，当我们跳出递归，循环不会继续。想法？

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中，对象的分配完成的引用的。这意味着研究和 newRoute 是相同的对象的。 newRoute 不是研究的独立副本正如您所料。因此，任何修改 newRoute 将改变研究为好。您可能需要显式地复制你的路线那里。 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.

注意：的有许多地方，你可以让你的code更有效，但蛮力是远远效率在任何情况下，而你只谈论几个城市，也许你不必在意。如果你想调查的替代品，但是，考虑维护所有未访问城市的单链表。每次调用会遍历这个列表，删除元素，递归并把该元素后面。无需在每次调用从头开始构建这个名单。的舞蹈链的可整齐地应用于此任务，作为替代premade的想法链表实现。

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.

编辑：

你的code以下变化对我的作品：

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屋！