在算法上找到Settlers of Catan游戏中最长的道路

Question

我正在为一堂课写一本卡坦定居者.其中一项额外功能是自动确定哪个玩家的道路最长.我已经考虑过了,看起来深度优先搜索的一些细微变化可能会起作用,但我无法弄清楚如何处理循环检测,如何处理玩家的两个初始道路网络的加入,和其他一些细枝末节.我怎么能在算法上做到这一点？

对于那些不熟悉游戏的人,我会尝试简洁而抽象地描述问题:我需要在无向循环图中找到最长的路径.

Answer 1

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

首先,将道路分成不同的集合,其中每个集合中的所有道路段都以某种方式连接.有这样做的各种方法,但这里有一个:

1. 选择一个随机路段,将其添加到一个集合中并标记它
2. 分支出这个部分,即.按照未标记的两个方向关联连接的部分(如果已标记,我们已经在这里)
3. 如果找到的路段尚未在集合中,请添加并标记
4. 继续从新细分开始,直到找不到与该集合中当前的细分相关联的任何其他未标记的细分
5. 如果剩下未标记的片段,则它们是新集合的一部分,选择一个随机片段并从另一个集合开始返回1

注意:根据官方的Catan规则,如果另一个游戏在两个部分之间的联合上建立定居点,则可以打破道路.你需要检测到这一点,而不是通过和解.

注意,在上面和后面的步骤中,只考虑当前的玩家细分.您可以忽略其他段,就好像它们甚至不在地图上一样.

这会为您提供一个或多个集合,每个集合包含一个或多个路段.

好的,对于每一组,请执行以下操作:

1. 在集合中选择一个随机路段,该路段仅有一个连接的路段(即,您选择一个端点)
2. 如果你不能这样做,那么整个集合就是循环(一个或多个),所以在这种情况下选择一个随机段

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

每当您需要回溯时,因为没有更多分支,请记下当前长度,如果长度超过"之前的最大值",则将新长度存储为最大长度.

为所有套装做这件事,你应该有最长的路.