我正在为一堂课写一本卡特定居者。额外的信用功能之一是自动确定哪个玩家拥有最长的道路。我已经考虑过了，看起来深度优先搜索的一些细微变化可能会起作用，但我无法弄清楚如何处理循环检测，如何处理玩家的两个初始道路网络的加入，和其他一些细枝末节。我怎么能在算法上做到这一点？
对于那些不熟悉游戏的人，我会尝试简洁而抽象地描述问题：我需要在无向循环图中找到最长的路径。
我正在为一堂课写一本卡特定居者。额外的信用功能之一是自动确定哪个玩家拥有最长的道路。我已经考虑过了，看起来深度优先搜索的一些细微变化可能会起作用，但我无法弄清楚如何处理循环检测，如何处理玩家的两个初始道路网络的加入，和其他一些细枝末节。我怎么能在算法上做到这一点？
对于那些不熟悉游戏的人，我会尝试简洁而抽象地描述问题：我需要在无向循环图中找到最长的路径。
这应该是一个相当容易实现的算法。
首先，将道路分成不同的集合，其中每组中的所有道路段都以某种方式连接。有这样做的各种方法，但这里有一个：
注意：按官方说 卡坦规则如果另一个游戏在两个部分之间的联合上建立了解决方案，则可以打破道路。您需要检测到这一点，而不是通过结算。
注意，在上面和后面的步骤中，只考虑当前的玩家细分。您可以忽略其他段，就好像它们甚至不在地图上一样。
这会为您提供一个或多个集合，每个集合包含一个或多个路段。
好的，对于每一组，请执行以下操作：
现在，从您选择的细分市场，进行递归分支深度优先搜索，跟踪您到目前为止找到的当前道路的长度。始终标记路段，不要分支到已标记的段。这将允许算法在“吃掉自己的尾巴”时停止。
每当您需要回溯时，因为没有更多分支，请记下当前长度，如果长度超过“之前的最大值”，则将新长度存储为最大长度。
为所有套装做这件事，你应该有最长的路。
我会建议广度优先搜索。
对于每个球员：
选择一个起始节点。如果它具有零个或多个连接的邻居，则跳过，并以广度优先的方式找到从其开始的所有玩家路径。捕获：一旦一个节点被遍历，对于该回合中剩下的所有搜索，它被“停用”。也就是说，它可能不再被遍历。
如何实施？这是一种可以使用的广度优先算法：
执行此操作一次后，转到下一个激活的节点并重新开始该过程。停用所有节点时停止。
对于给定的玩家，你现在拥有的最大值是你最长的道路长度。
请注意，这效率稍低，但如果性能无关紧要，那么这将有效:)
重要提示，感谢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
不太晚，但仍然相关。我在java中实现它，请参阅 这里。算法如下：
此实现支持Catan的大多数变体。边缘可以自己决定是否要连接到另一个，请参阅
SidePiece.canConnect(point, to.getSidePiece());
道路，船舶，桥梁都实施了SidePiece接口。道路有实施
public boolean canConnect(GraphPoint graphPoint, SidePiece otherPiece)
{
return (player.equals(graphPoint.getPlayer()) || graphPoint.getPlayer() == null)
&& otherPiece.connectsWithRoad();
}
简单的多项式时间深度优先搜索不太可行，因为问题是NP难的。您将需要一些需要指数时间来获得最佳解决方案的东西。由于问题很小，但在实践中应该没问题。
可能最简单的解决方案是动态编程：保留一个表T [v，l]存储每个节点v和每个长度l一组路径长度为l并以v结尾。显然T [v，1] = { [v]}你可以通过收集来自T [w，l-1]的所有路径为l> 1填写T [v，l]，其中w是v的邻居，但是还没有包含v，然后附加v这与Justin L.的解决方案类似，但避免了一些重复的工作。
我要做的是：
对不起prolog-ish术语:)
这是我用来确定Catan Excel VBA模拟器中给定玩家（“用户”）最长路的代码片段。
我刚才意识到它没有考虑到有关定居点的规则，但这不应该很难融入。
Private Frays As Dictionary
Private RoadPths As Collection
Public Function GetLongestRoad(g As Board, oUser As User) As Long
Dim oRoad As Road
Dim v, w
Dim fNum As Long
Dim rCount As Long
Set Frays = New Dictionary
Set RoadPths = New Collection
' get list of roads that happen to be linked to other roads ("Frays")
For fNum = 55 To 126
If g.Roads(fNum).Owner = oUser.Name Then
For Each v In RoadLinks(g, fNum)
If g.Roads(v).Owner = oUser.Name Then Frays(fNum) = v
Next v
End If
Next fNum
' begin recursion
For Each v In Frays
RecurSegmts g, v & ";" & Frays(v)
Next v
rCount = 0
For Each v In RoadPths
w = Split(v, ";")
If rCount < UBound(w) Then rCount = UBound(w)
Next v
GetLongestRoad = rCount + 1
End Function
Private Sub RecurSegmts(g As Board, Segmts As Variant)
Dim SegmtArr, NextRoad
Dim LoopsBack As Boolean
Dim i As Long
RoadPths.Add Segmts
SegmtArr = Split(Segmts, ";")
For Each NextRoad In RoadLinks(g, CLng(SegmtArr(UBound(SegmtArr))))
LoopsBack = False
For i = 0 To UBound(SegmtArr)
If CLng(NextRoad) = CLng(SegmtArr(i)) Then LoopsBack = True
Next i
If LoopsBack = False Then Call RecurSegmts(g, Segmts & ";" & NextRoad)
Next NextRoad
End Sub
如果有人需要，这是我的版本。写在 Typescript。
longestRoadLengthForPlayer（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
}
您可以使用Dijkstra，只需更改条件即可选择最长的路径。
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
这是有效的，但并不总能找到实际上最短/最长的路径，尽管它在大多数时间都可以工作。