通过算法寻找卡坦岛游戏中最长的道路

Question

我正在为课程编写一个《卡坦岛定居者》克隆版。额外的积分功能之一是自动确定哪个玩家拥有最长的道路。我考虑过，深度优先搜索的一些细微变化似乎可以起作用，但我无法弄清楚如何处理循环检测，如何处理玩家的两个初始道路网络的连接，以及其他一些细节。我怎样才能通过算法做到这一点？

对于那些不熟悉游戏的人，我将尝试简洁抽象地描述问题：我需要在无向循环图中找到最长的可能路径。

Answer 1

这应该是一个相当容易实现的算法。

首先，将道路分成不同的组，每个组中的所有路段都以某种方式连接。有多种方法可以做到这一点，但这里有一个：

1. 选择一个随机路段，将其添加到一个集合中，并将其标记
2. 为从该路段分支出来，即。沿着未标记的两个方向连接的路段（如果已标记，则我们已经到过这里）
3. 如果找到的路段尚未在集合中，则将其添加并标记它
4. 继续从新路段继续，直到无法找到为止查找与当前组中的当前段相关的任何更多未标记段
5. 如果还存在未标记段，则它们是新组的一部分，随机选择一个段并从 1 开始使用另一组

注意：根据官方的卡坦岛规则，如果另一场比赛建立，一条路可能会被破坏两个部分之间的连接处的解决方案。你需要检测到这一点，而不是越过定居点。

请注意，在上面和下面的步骤中，仅考虑当前玩家分段。您可以忽略其他部分，就好像它们根本不在地图上一样。

这将为您提供一组或多组，每组包含一个或多个路段。

好的，对于每一组，执行以下操作：

1. 在该组中选择一个随机路段，该组中只有一个连接的路段（即您选择一个端点）
2. 如果您不能这样做，则整个组正在循环（一个或多个），因此在这种情况下选择一个随机路段

现在，从您选择的路段中，进行递归分支深度优先搜索，跟踪到目前为止您找到的当前道路的长度。始终标记路段，并且不要分支到已标记的路段。这将使算法在“吃掉自己的尾巴”时停止。

每当您需要回溯时，因为没有更多分支，请记下当前长度，如果它比“先前的最大值”长，则将新长度存储为最大值。

对所有组都这样做，你就会得到最长的路。

Answer 2

简单的多项式时间深度优先搜索不太可能起作用，因为该问题是 NP 困难的。您将需要花费指数时间才能获得最佳解决方案的东西。由于问题很小，所以在实践中应该没有问题。

最简单的解决方案可能是动态编程：保留一个表 T[v, l]，为每个节点 v 和每个长度 l 存储长度为 l 且以 v 结尾的路径集。显然 T[v, 1] = { [v]} 则可以填写 T[v, l]，其中 l > 1 通过收集来自 T[w, l-1] 的所有路径（其中 w 是 v 的邻居，但尚未包含 v），然后附加 v。这与 Justin L. 的解决方案类似，但避免了一些重复工作。

Answer 3

我建议进行广度优先搜索。

对于每个玩家：

• 设置默认的已知最大值 0

• 选择一个起始节点。如果它有零个或多个连接的邻居，则跳过并以广度优先的方式找到从它开始的所有玩家路径。问题是：一旦遍历到一个节点，该节点就将“停用”该轮中剩余的所有搜索。也就是说，它可能不再被遍历。

  如何实现这一点？这是可以使用的一种可能的广度优先算法：

  1. 如果没有从此初始节点开始的路径，或者有多个路径，请将其标记为停用并跳过它。
  2. 保留路径队列。
  3. 将仅包含初始死端节点的路径添加到队列中。停用该节点。
  4. 从队列中弹出第一条路径并“分解”它——也就是说，找到所有有效路径，这些路径是该路径+在有效方向上多一步的路径。对于“有效”，下一个节点必须通过道路连接到最后一个节点，并且还必须被激活。
  5. 停用上一步中所访问的所有节点。
  6. 如果前一条路径没有有效的“爆炸”，则将该路径的长度与已知的最大值进行比较。如果大于它，则为新的最大值。
  7. 将所有分解路径（如果有）添加回队列中。
  8. 重复4-7，直到队列为空。

• 执行此操作一次后，移动到下一个激活的节点并重新开始该过程。当所有节点都停用时停止。

• 您现在拥有的最大值是给定玩家的最长道路长度。

请注意，这效率稍低，但如果性能不重要，那么这会起作用:)

重要说明，感谢 Cameron MacFarland

• 假设所有不属于当前玩家的城市的节点都会自动停用总是。

---

Ruby 伪代码（假设每个节点都有一个 get_neighbors 函数）

def explode n
  exploded = n.get_neighbors             # get all neighbors
  exploded.select! { |i| i.activated? }  # we only want activated ones
  exploded.select! { |i| i.is_connected_to(n) } # we only want road-connected ones
  return exploded
end

max = 0

nodes.each do |n|                 # for each node n
  next if not n.activated?        # skip if node is deactivated
  if explode(n).empty? or explode(n).size > 1
    n.deactivate                  # deactivate and skip if
    next                          # there are no neighbors or
  end                             # more than one

  paths = [ [n] ]                 # start queue

  until paths.empty?              # do this until the queue is empty

    curr_path = paths.pop         # pop a path from the queue
    exploded = explode(curr_path) # get all of the exploded valid paths

    exploded.each { |i| i.deactivate }  # deactivate all of the exploded valid points

    if exploded.empty?                  # if no exploded paths
      max = [max,curr_path.size].max    # this is the end of the road, so compare its length to
                                        # the max
    else
      exploded.each { |i| paths.unshift(curr_path.clone + i) }  
                                        # otherwise, add the new paths to the queue
    end

  end

end

puts max

Answer 4

有点晚了，但仍然相关。我用java实现了它，请参阅

• 使用玩家的所有边从主图派生出一个图，添加连接到边的主图的顶点
• 制作一个端点列表（度数==1的顶点）和分割（度数=的顶点） =3）
• 添加一条路线来检查每个端点的（possibleRoute），并为每个分割处找到的每两条边+一个顶点组合（3，因为度数为3）
• 步行每条路线。可能会遇到三件事：结束、中间或分裂。
• 结束：终止可能的路由，将其添加到找到的列表
• 中间：检查是否可以连接到其他边缘。如果是这样，请添加边缘。如果没有，则终止该路由并将其添加到找到的路由列表
• 分割：对于两条边，都按中间方式进行。当两条路由连接时，复制第二条路由并将其也添加到列表中。
• 使用两种方法检查连接：查看可能的路由中是否已存在新边（无连接），并通过将顶点和原始顶点作为参数来询问新边是否可以连接。一条道路可以连接到另一条道路，但前提是该顶点不包含其他玩家的城市/定居点。道路可以连接到船只，但前提是顶点包含正在检查路线的玩家的城市或道路。
• 可能存在循环。每个遇到的边都会添加到列表中（如果尚未添加到列表中）。当检查了所有可能的路线，但此列表中的边数小于玩家的边总数时，则存在一个或多个循环。在这种情况下，任何未检查的边都会成为新的可能路由，并再次检查该路由。
• 最长路线的长度是通过简单地迭代所有路线来确定的。返回遇到的具有等于或多于 5 个边的第一条路线。

此实现支持 Catan 的大多数变体。边缘可以自行决定是否要连接到另一个边缘，请参阅

SidePiece.canConnect(point, to.getSidePiece());

已实现 SidePiece 接口的道路、船舶、桥梁。一条路有作为实施

public boolean canConnect(GraphPoint graphPoint, SidePiece otherPiece)
{
    return (player.equals(graphPoint.getPlayer()) || graphPoint.getPlayer() == null)
            && otherPiece.connectsWithRoad();
}

Answer 5

我会做什么：

1. 选择一个带有道路的顶点
2. 选择最多两条要遵循的道路
3. 沿着道路走；如果有分支就回溯到这里，并选择更长的
4. 如果当前顶点在访问列表中，回溯到3
5. 将顶点添加到访问列表中，从3递归
6. 如果3处没有更多的路，则返回长度
7. 当你'最多走了 2 条路，将它们相加，记下长度
8. 如果初始顶点有 3 条路，则回溯到 2 条。

抱歉使用了 prolog 式的术语:)

Answer 6

这是我的版本，如果有人需要的话。用 Typescript 编写。

最长的RoadLengthForPlayer（玩家：PlayerColors）：数字{
让最长的路= 0

    let mainLoop = (currentLongestRoad: number, tileEdge: TileEdge, passedCorners: TileCorner[], passedEdges: TileEdge[]) => {
        if (!(passedEdges.indexOf(tileEdge) > -1) && tileEdge.owner == player) {
            passedEdges.push(tileEdge)
            currentLongestRoad++
            for (let endPoint of tileEdge.hexEdge.endPoints()) {
                let corner = this.getTileCorner(endPoint)!

                if ((corner.owner == player || corner.owner == PlayerColors.None) && !(passedCorners.indexOf(corner) > -1)) {
                    passedCorners.push(corner)
                    for (let hexEdge of corner.hexCorner.touchingEdges()) {
                        let edge = this.getTileEdge(hexEdge)
                        if (edge != undefined && edge != tileEdge) {
                            mainLoop(currentLongestRoad, edge, passedCorners, passedEdges)
                        }
                    }
                } else {
                    checkIfLongestRoad(currentLongestRoad)
                }
            }
        } else {
            checkIfLongestRoad(currentLongestRoad)
        }
    }

    for (let tileEdge of this.tileEdges) {
        mainLoop(0, tileEdge, [], [])
    }

    function checkIfLongestRoad(roadLength: number) {
        if (roadLength > longestRoad) {
            longestRoad = roadLength
        }
    }

    return longestRoad
}

Answer 7

您可以使用 Dijkstra，只需更改条件即可选择最长的路径。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

它很高效，但并不总能找到实际上最短/最长的路径，尽管它在大多数情况下都有效。