python - 获取图中唯一状态的数量

Question

我一直在尝试解决麻省理工学院的计算机科学数学问题集，这是其中一个问题:

Each monk entering the Temple of Forever is given a bowl with 15 red beads and 12 green beads. Each time the Gong of Time rings, a monk must do one of two things:

1. Exchange: If he has 3 red beads in his bowl, then he may exchange 3 red beads for 2 green beads.
2. Swap: He may replace each green bead in his bowl with a red bead and replace each red bead in his bowl with a green bead. That is, if he starts with i red beads and j green beads, then after he performs this operation, he will have j red beads and i green beads.

A monk may leave the Temple of Forever only when he has exactly 5 red beads and 5 green beads in his bowl.

这有一些子问题:

1. 证明没有人离开过圣殿。我用数学归纳法证明了这一点。
2. 证明该问题只能达到有限数量的状态。这个证明也是通过数学归纳法来完成的，并证明红色珠子和绿色珠子的数量之和只能减少或保持不变。
3. (这就是我陷入困境的地方)僧侣在永恒神殿机器的任何执行中可以访问的唯一状态的真正最大数量是多少？

在花了相当多的时间尝试思考子问题 #3 后，我放弃了并决定编写一个程序来计算唯一状态的数量。

class Node:
    def __init__(self, r, g):
        self.r = r
        self.g = g

    def swap(self):
        if self.g <= 0 or self.r <= 0:
            return None
        return Node(self.g, self.r)

    def exchange(self):
        if self.r >= 3:
            return Node(self.r - 3, self.g + 2)
        return None

    def __hash__(self):
        return hash((self.r, self.g))

    def __eq__(self, other):
        if self is None and other is None:
            return True
        if self is None or other is None:
            return False
        return self.r == other.r and self.g == other.g

    def __repr__(self):
        return "({}, {})".format(self.r, self.g)

start = Node(15, 12)
queue = []
graph = []
visited = set()
queue.append(start)

while (queue):
    curr = queue.pop(0)
    visited.add(curr)
    graph.append(curr)
    s = curr.swap()
    e = curr.exchange()

    for el in [s, e]:
        if el != None:
            if el not in visited:
                queue.append(el)

print(visited, len(visited))

我从程序中得到的答案是

{(6, 9), (16, 9), (0, 7), (2, 5), (8, 5), (5, 8), (10, 8), (10, 7), (16, 3), (5, 18), (0, 17), (14, 1), (8, 15), (10, 13), (4, 16), (9, 16), (7, 5), (14, 2), (13, 10), (3, 1), (6, 13), (20, 3), (3, 11), (4, 12), (10, 3), (6, 14), (7, 15), (18, 5), (3, 6), (8, 6), (4, 1), (9, 7), (6, 4), (11, 4), (16, 4), (5, 17), (11, 9), (0, 18), (14, 6), (13, 6), (19, 2), (18, 6), (1, 19), (15, 7), (0, 8), (4, 11), (3, 5), (4, 6), (9, 2), (5, 7), (4, 17), (11, 3), (7, 4), (14, 12), (12, 4), (19, 1), (3, 15), (1, 3), (5, 13), (3, 21), (11, 14), (12, 9), (18, 1), (15, 12), (2, 19), (3, 10), (1, 14), (8, 10), (9, 11), (3, 16), (8, 16), (11, 13), (0, 22), (17, 5), (6, 18), (7, 14), (12, 14), (19, 6), (15, 3), (2, 20), (1, 4), (0, 12), (1, 9), (4, 2), (2, 14), (9, 6), (5, 3), (6, 8), (11, 8), (16, 8), (14, 7), (13, 5), (1, 18), (2, 4), (9, 12), (4, 7), (9, 1), (12, 5), (15, 8), (0, 3), (2, 9), (8, 1), (5, 12), (3, 20), (10, 12), (6, 3), (9, 17), (7, 10), (12, 10), (13, 11), (1, 13), (8, 11), (2, 10), (0, 23), (17, 4), (6, 19), (14, 11), (12, 15), (7, 9), (13, 1), (17, 9), (15, 2), (20, 2), (0, 13), (21, 3), (1, 8), (2, 15), (5, 2), (10, 2)} 129

所以，129。但是当我查看问题集的解决方案(对于子问题#3)时，它是这样的

Each move in the sequence must be either an exchange or swap, since these are the only legal moves. Now, whenever the monk performs an exchange operation, the sum r + g decreases by one.

(r - 3) + (g + 2) = (r + g) - 1

In contrast, swaps do not have any effect on the sum. Furthermore, we know that the sum r + g must be at least 3 to perform an exchange operation. Therefore, there can be at most 25 exchange operations in the sequence.

Now consider swap operations: between each pair of exchanges in the sequence, there may be an unlimited number of swaps. However, only a single swap can take the monk to a new state: if at step k the monk is in state (r, g), then at step k + 2, he will return to the same state. Therefore, an upper bound on the number of unique states in any execution of the machine is 25 + 26 + 1 = 52 (if swaps are inserted at both the beginning and end of the sequence).

我的程序哪里出了问题？我对问题陈述的理解是否不正确(关于我编写的程序)？另外，我不太明白他们给出的解决方案。有没有更好的方法来解释它？例如，我不明白的问题/事情之一是，解决方案指出每次交换操作珠子的总和都会减少 1。因此我们可以获得 25 个具有交换操作的新状态。但是图表每个级别的每个总和都可以用多种方式表示，是吗？那么，一定有更多的国家是通过交易所业务创建的吗？这是 link完整的问题集是 solution .

Answer 1

编辑:根据 OP 自己的回答和我们在评论中的讨论，这是关键问题:

我们必须区分两个不同的数字:

1. 僧侣可以采取的任何一条路径中访问状态的最大数量n；
2. 僧侣可以达到的状态总数N。

请注意，N 是在任何一条路径中访问的状态集的并集(采用所有可能的路径)的基数。这意味着n <= N，并且很容易看出这些数字不相等。麻省理工学院的问题询问n，而OP的原始代码旨在找到N。

---

引用的证明是正确的，因此“[n] 的上限是 25 + 26 + 1 = 52”。

我尝试了蒙特卡罗方法来近似N:只要有选择，就随机决定是交换还是交换，重复直到过程在 (2, 0) 和 (0, 2) 之间振荡，并多次重复所有这些，同时跟踪所有唯一访问过的状态。

但是，这似乎并不实用，因为可能的路径数量太大，因此在任何可行的迭代次数下，我们得到的数量都不会接近N。下面的代码在我的机器上已经花费了大约 15 分钟。

import random

def swap(i, j):
    i, j = j, i
    return i, j

def exchange(i, j):
    i, j = i - 3, j + 2
    return i, j

x, y = 15, 12
visited = {(x, y)}

for run in range(1_000_000_000):
    while x + y > 2:
        if x < 3:
            x, y = swap(x, y)
        else:
            coinflip = random.randint(0, 1)
            if coinflip == 0:
                x, y = swap(x, y)
            else:
                x, y = exchange(x, y)
        visited = visited.union({(x, y)})

    x, y = swap(x, y)    
    visited = visited.union({(x, y)})

print('Visited states:', visited)
print('Number of visited states:', len(visited))

访问过的州:{(18, 0), (4, 7), (1, 3), (3, 0), (0, 2), (4, 12), (11, 14), ( 2, 5), (0, 3), (8, 5), (5, 8), (15, 12), (8, 1), (16, 3), (5, 18), (1, 14), (14, 1), (3, 16), (8, 16), (4, 1), (12, 14), (2, 20), (0, 18), (2, 10) , (1, 4), (1, 19), (4, 2), (17, 4), (5, 3), (14, 11), (4, 6), (15, 2), ( 20, 2), (16, 8), (4, 17), (11, 3), (3, 1), (7, 4), (14, 12), (1, 8), (12, 4), (2, 0), (19, 1), (5, 2), (2, 4), (10, 2)}

访问过的州数:46

更新:这是完整状态空间的图。 N = 140

这是一条访问 52 个州的路径。绿色的 X 是起点，每个蓝色圆圈标记一个已访问的状态。由于我们从引用的证明中知道 n <= 52，因此证明 n = 52。