12

我正在为一个班级写一个 Settlers of Catan 克隆。额外的信用功能之一是自动确定哪个玩家拥有最长的道路。我已经考虑过了，似乎深度优先搜索的一些细微变化可能会起作用，但我无法弄清楚如何处理循环检测，如何处理玩家的两个初始道路网络的加入，和其他一些细节。我怎么能在算法上做到这一点？

对于不熟悉这个游戏的人，我会尽量简洁抽象地描述这个问题：我需要在一个无向循环图中找到最长的可能路径。

4

7 回答 7

7

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

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

  1. 选择一个随机路段，将其添加到一个集合中，并标记它
  2. 从这个部分分支出来，即。在未标记的两个方向上跟随连接的路段（如果它们被标记，我们已经到过这里）
  3. 如果找到的路段不在集合中，添加它并标记它
  4. 继续从新段开始，直到您找不到与当前集合中的段相关联的任何未标记段
  5. 如果还有未标记的片段，它们是新集合的一部分，请随机选择一个，然后从 1 开始与另一集合

注意：根据官方卡坦规则，如果另一场比赛在两个路段之间的连接处建立定居点，则可能会破坏道路。您需要检测到这一点，而不是越过结算。

请注意，在上述和以下步骤中，仅考虑当前玩家细分。您可以忽略这些其他部分，就好像它们甚至不在地图上一样。

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

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

  1. 在集合中选择一个随机路段，其中只有一个连接的路段（即您选择一个端点）
  2. 如果你不能这样做，那么整个集合都在循环（一个或多个），所以在这种情况下选择一个随机片段

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

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

对所有组都这样做，你应该有最长的路。

于 2010-07-07T07:33:30.817 回答
2

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

对于每个玩家：

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

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

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

    1. 如果从这个初始节点没有路径，或者有多个路径，则将其标记为停用并跳过它。
    2. 保留路径队列。
    3. 将仅包含初始死端节点的路径添加到队列中。停用此节点。
    4. 将第一条路径从队列中弹出并“分解”它——也就是说，找到所有有效路径，即路径 + 1 在有效方向上的更多步骤。通过“有效”，下一个节点必须通过道路连接到最后一个节点，并且它也必须被激活。
    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
于 2010-07-07T07:06:36.060 回答
2

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

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

于 2010-07-07T08:52:53.207 回答
2

有点晚了，但仍然有意义。我在 java 中实现了它，请参见此处。算法如下：

  • 使用玩家的所有边从主图派生一个图，添加连接到边的主图的顶点
  • 列出末端（度数==1的顶点）和分裂（度数==3的顶点）
  • 添加一条路线以检查 (possibleRoute) 的每一端，并在每次拆分时为每两条边 + 一个顶点组合找到 (3，因为度数为 3)
  • 走好每一条路。可能会遇到三件事：结束、中间或分裂。
  • End : 终止可能的Route，将其添加到找到的列表中
  • 中级：检查是否可以连接到其他边缘。如果是这样，请添加边缘。如果没有，则终止路由并将其添加到找到的路由列表中
  • 拆分：对于两个边缘，做中间。当两条路线连接时，复制第二条路线并将其添加到列表中。
  • 使用两种方法检查连接：查看新边是否已存在于 possibleRoute（无连接）中，并通过将顶点和原始顶点作为参数来询问新边是否可以连接。一条道路可以连接到一条道路，但前提是该顶点不包含来自其他玩家的城市/定居点。一条道路可以连接到一艘船，但前提是顶点包含正在检查路线的玩家的城市或道路。
  • 可能存在循环。如果每个遇到的边缘尚未在列表中，则将其添加到列表中。当检查了所有可能的Routes，但该列表中的边数少于玩家的总边数时，存在一个或多个循环。在这种情况下，任何未检查的边都将成为新的 possibleRoute ，并再次检查该路线。
  • 最长路线的长度是通过简单地遍历所有路线来确定的。返回遇到的具有等于或多于 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();
}
于 2011-02-12T19:29:33.253 回答
0

我会做什么：

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

对不起序言式的术语:)

于 2010-07-07T02:25:54.723 回答
0

如果有人需要，这是我的版本。写在Typescript.

longRoadLengthForPlayer(player: PlayerColors): number { 让longestRoad = 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
}
于 2017-11-30T12:25:16.547 回答
-1

您可以使用 Dijkstra 并更改条件以选择最长的路径。

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

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

于 2010-07-07T07:37:07.297 回答