Алгоритм поиска победителей в игре прохождения - PullRequest
Новая
       13

Алгоритм поиска победителей в игре прохождения

0 голосов
/ 14 февраля 2019

Будем работать с графиками и двумя игроками.На этом связанном графике условие победы состоит в том, что у второго игрока нет других путей.Загвоздка в том, что как только игрок выбрал путь, он не может быть взят снова.

Предположим, что исходным входом является список смежности (x, y) означает, что x имеет путь к y

Цель состоит в том, чтобы вернуть набор вершин, которые игрок 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

1 Ответ

0 голосов
/ 14 февраля 2019

Вот простое рекурсивное решение.Это неэффективно, это поиск методом грубой силы без какого-либо кэширования промежуточных состояний, поэтому его, безусловно, можно сделать быстрее, хотя я не знаю, существует ли эффективное (то есть не экспоненциальное) решение этой проблемы. 

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]
...