Допустим, у нас есть простой связный и ненаправленный граф G (V, E).В игру играют два игрока.В каждой игре игрок A начинает игру в узле t, а игрок B - в узле v. Также существует узел d, который одинаков для каждой игры.
В игре игрок A всегда играет первым.Его цель - добраться до узла d до того, как игрок B достигнет его (игрок B не может перейти к узлу d).Цель игрока B, с другой стороны, состоит в том, чтобы достичь узла, где находится A.Если игроки A, B были в узлах x, y, соответственно, в предыдущем раунде, и эти позиции повторяются снова, матч заканчивается в ничьей.В каждом раунде игрок, имеющий приоритет, должен двигаться к соседнему узлу.
Мне нужно создать алгоритм, который выдает на выходе результат этой игры для каждой возможной стартовой комбинации t, v∈V (гдеt ≠ v).
То, что я до сих пор делал, это решение динамического программирования O (| V | 3).Мы можем записать все возможные состояния этой игры как (положение игрока A, положение игрока B, следующий игрок для перемещения) и найти все возможные результирующие состояния для каждого состояния.
Можно ли сделать это лучше