java - 从起点开始的深度优先算法

Question

好吧，我在网上查了很多资料，但都不太合我的胃口。

我有一个ArrayList towns = new ArrayList<Town>以及我将对其执行 DFS 的城镇。

我用 ~8 个城镇填充这个数组

我有一个整数int i (ArrayList 中的城镇索引，必须位于路径中的第一个位置)

我有一个初始距离double dist = 0

我有一个函数distBetween(Town a, Town b)它的作用就是它所说的。

我有一个数组列表 route = new ArrayList<Town>()其中包含城镇的顺序，具体取决于我所走的路径。

现在我有了执行深度优先搜索的主要函数(根据在线研究，递归)。

public static void dfs(){

    // what goes here

}

我需要将城镇添加到路线数组中，并根据深度优先搜索算法删除它们。我需要编辑 dist变量也是如此。

我怎么会想到这个。有人可以向我提供一些伪代码或注释来解释要做什么。我似乎无法应用我在网上找到的其他算法。如果我能得到针对我的情况的具体解释，那就太好了。

我可以删除索引i来自town如果它可以更轻松地执行搜索。

Answer 1

我假设您有 State具有以下属性的类(如果您喜欢图表，请使用 Node 而不是 State ):

Set<Town> unused;        // towns not yet visited
ArrayList<Town> path;    // current path
double dist;             // total distance in path

然后使用类似这样的代码，使用 DFS 递归地尝试每一条可能的路径。第一次通话时，使用 dfs(emptyState, startTown, null) :

public static void dfs(State s, Town last, State best) {
    s.path.add(last);
    s.unused.remove(last);
    if (unused.empty()) {
        // all towns visited - distance and path are now complete
        if (best == null || s.dist < best.dist) best = s;
        return;
    }
    for (Town t : s.unused) {
        State next = s.copy(); // a copy of State s
        next.dist += distBetween(last, t);
        dfs(next, t);
    }
}

调用此函数后，所有路径都将被访问一次(按 DFS 顺序)，并且 best将包含最短的一个。请注意，对于许多城市来说，这会变得非常慢 - O(n!)。