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

我正在学校的数学课上做一个项目，我选择做旅行商问题，这是我一直想进行更多研究的问题。 但是，我的暴力求解算法遇到了问题。

*请前往底部更新查看最新版本代码

如果您知道旅行推销员问题是什么，请跳过本段：尽可能概括地说，TSP 是这样的：您是一名推销员，想要访问某个地区的每个城市（城市本质上是地图上的一个点）。在有界的 x 和 y 区域中有“n”个城市，每个城市都与每个城市相连（假设有一条直路）。你需要找到允许你访问每个城市的城市中最短的路线。我想使用的算法之一（并且我需要测试其他算法）是Brute Force，它会检查每条可能的路线并返回最短的路线路线。之所以不总是使用它，是因为它要求我们检查 (n-1)！可能的路线，并且随着“n”的增加，这个数字变得越来越大 - 事实上，只有 50 个城市，这将是 608281864034267560872252163321295376887552831379210240000000000 条路线要检查。

假设对于本文中讨论的所有示例，我们将使用包含 4 个城市的任意区域（即使该算法可以处理 n 个城市。而且我们也不关心距离 - 我们希望用暴力破解每条可能的路线）。

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

带有城市的地图图片 http://www.emeraldinsight.com/content_images/fig/0050300707002.png

这是暴力算法（假设所有其他调用的方法都正常工作，因为它们确实如此）：

（查看下面的更多解释）

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

    }

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

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

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

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

• 标记最后一个城市

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

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

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

递归树结构的有用图片 http://i264.photobucket.com/albums/ii191/om3n07/46049b90.jpg

该问题与在循环中调用递归或在递归调用中引用路由“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似乎失去了它的意义，并且循环不再继续。有想法吗？

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

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

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

请注意，您正在编写Java，并且在Java中，完成了对象的赋值引用。意思就是r and newRoute are 同一个物体. newRoute不是独立的副本r正如你所期望的那样。所以任何修改newRoute会改变r以及。您可能想将您的路线明确复制到那里。 Java 术语是clone http://docs.oracle.com/javase/7/docs/api/java/lang/Cloneable.html。确保您的克隆足够深，即克隆所有相关的数据结构，而不是在原始数据结构与其克隆数据结构之间共享它们。

Note:在很多地方，您都可以使代码更加高效，但无论如何，暴力都远非高效，而且您只谈论少数城市，也许您不必关心。不过，如果您想研究替代方案，请考虑维护所有未访问过的城市的单个链接列表。每次调用都会循环该列表，删除一个元素，递归并将该元素放回原处。无需在每次调用中从头开始构建此列表。的想法跳舞链接 http://arxiv.org/abs/cs/0011047可以巧妙地应用于此任务，作为预制链表实现的替代方案。

EDIT:

您的代码的以下变体对我有用：

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