gpt4 book ai didi

python - 寻找谁在遍历游戏中获胜的算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:38:29 24 4
gpt4 key购买 nike

我们将使用图表和两个玩家。在这个连通图中,获胜条件是第二个玩家没有其他路径可走。问题是,一旦玩家选择了一条路径,就无法再次选择。

让我们假设初始输入是邻接表 (x,y) 意味着 x 有到 y 的路径

目标是返回玩家 1 可以选择的一组顶点,以便玩家 1 始终获胜。

例如,如果我有 [(1,2), (2,0), (0, 3), (3,2)] 并且玩家 1 开始,那么我们应该返回[1, 0, 3]。我们不能返回 2:

2 --> 玩家 1 从这里开始

(2,0) --> 玩家 2 走到 0

(0,3) --> 玩家 1 去 3

(3,2) --> 玩家 2 去到 2

(2,0) --> 玩家 1 不能去这里,已经被带走了

already_visited = []

turn = 1

result = []

def findStarting(L):
global already_visited
global turn
global result

for x,y in L:
allowed = can_visit(L, y) # function tell me which I can visit safely

turn = (turn % 2) + 1 # increment the turn

already_visited.append((x,y)) # we visited this edge

res = findStarting([(x, y)]) # recursive call (search on this node for paths)


if (turn == 2): return True

def can_visit(L, y):
res = []
for a,b in L: if (a==y and (a,b) not in already_visited): res.append((a,b))
return res

我在处理递归情况时遇到了问题。我想我想做的是返回 True 如果我们到达转弯为 2 的点并且玩家没有他们可以走的路径,但我不确定如何从这里继续前进

enter image description here

最佳答案

这是一个简单的递归解决方案。它效率不高,它是没有任何中间状态缓存的蛮力搜索,所以它肯定可以变得更快,虽然我不知道是否有解决这个问题的有效(即非指数)解决方案。

def firstPlayerWins(g,v):
for i,e in enumerate(g):
if e[0]==v and not firstPlayerWins(g[:i]+g[i+1:],e[1]):
return True
return False

def winningVertices(g):
return [v for v in set(e[0] for e in g) if firstPlayerWins(g,v)]

winningVertices([(1,2), (2,0), (0, 3), (3,2)])
## [0, 2, 3]

关于python - 寻找谁在遍历游戏中获胜的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54691091/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com