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

Question

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

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

Answer 1

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

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

1. 随机选择一个路段，将其添加到集合中并进行标记
2. 从此部分分支出来，即。沿着未标记的两个方向连接的路段(如果标记了，我们已经到过这里)
3. 如果找到的路段不在集合中，添加它并标记它
4. 继续从新的片段开始，直到找不到更多未标记的片段与当前集合中的片段相关
5. 如果还有未标记的片段，则它们是新集合的一部分，随机选择一个片段，然后从 1 开始返回另一组

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

请注意，在上面和后面的步骤中，只考虑当前玩家分割。您可以忽略那些其他路段，就好像它们甚至不在 map 上一样。

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

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

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

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

每当需要回溯的时候，因为没有更多的分支，记下当前的长度，如果比“之前的最大值”长，就将新的长度作为最大值存入。

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