Java中旅行商问题的强力算法

Question

我正在学校开设一个数学课的项目,我选择在旅行商问题上做我的,我一直想调查一下.但是,我的蛮力求解算法存在问题.

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

---

---

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

将承担谈到这篇文章的所有例子,我们将要使用的一个任意区域有4个城市(即使该算法可以处理n个城市.我们也不在乎distances-我们想打畜生一切可能的途径力).

这是一个简单的图片演示我正在谈论的内容(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<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");

    }

这是我的逻辑:(注意:一个城市对象有一个名为"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<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;
        }

    }

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

Answer 1

您应该在递归调用返回后从路径中删除城市.你做这个:

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

但从来没有newRoute.removeFromRoute或类似的.

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

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

编辑:

以下代码变体适合我:

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