获取图中唯一状态的数量
Getting the number of unique states in a graph
我一直在尝试解决麻省理工学院的计算机科学数学问题集，这是其中一个问题：
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:
- Exchange: If he has 3 red beads in his bowl, then he may exchange 3 red beads for 2 green beads.
- 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.
这里有子问题：
- 证明没有人离开过圣殿。我用数学归纳法证明了这一点。
- 证明这个问题只能达到有限的状态。这个证明也是通过使用数学归纳法来完成的，并证明了红色珠子和绿色珠子的数量之和只能减少或保持不变。
- （这就是我卡住的地方）在永恒神殿机器的任何执行中，僧侣可以访问的唯一状态的真实最大数量是多少？
在花了相当多的时间试图思考子问题 #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).
我的程序哪里出错了？我对问题陈述的理解是否不正确（根据我编写的程序）？另外，我真的不明白他们给出的解决方案。有没有更好的方法来解释它？例如，我不明白的 issues/things 之一是，解决方案指出每次交换操作珠子的总和减少 1。因此我们可以通过交换操作获得 25 个新状态。但是图中每个级别的每个总和都可以用多种方式表示，是吗？那么一定有更多的状态是由交换操作创建的吗？这是 link to the full problem set and it's solution.
编辑： 根据 OP 自己的回答和我们在评论中的讨论，这是关键问题：
我们必须区分两个不同的数字：
- 和尚可以走的任何一条路的最大访问状态数n;
- 和尚可以达到的状态总数N。
请注意，N 是在任何一条路径中访问的状态集的并集（采用所有可能的路径）的基数。这意味着 n <= N，很容易看出这些数字不相等。麻省理工学院的问题询问 n，而 OP 的原始代码旨在查找 N.
引用的证明是正确的，所以"an upper bound on [n] is 25 + 26 + 1 = 52"。
我尝试了一种Monte Carlo方法来近似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
更新： 这是完整状态的图 space。 N = 140
这是一条访问 52 个州的路径。绿色的 X 是起点，每个蓝色圆圈标记一个访问状态。由于我们从引用的证明中知道 n <= 52，这证明了 n = 52.
问题中的代码构建的图表连接了每个可能的状态，因此计算了状态机可能的状态总数，但不是僧侣在任何执行圣殿时可以访问的唯一状态的最大数量永远的机器。
通过以类似 BFS 的方式对节点进行计数，我假设可以通过任何其他状态到达每个状态。事实并非如此。在交换操作创建新状态后，不可能通过交换返回到它的 "parent" 状态（显然），因此一旦在锣声中做出选择，就没有了任何回去。
因此，我们真正需要做的是构建图形并从起始节点执行 DFS，并跟踪我们在 DFS 遍历期间达到的最大深度。这个最大深度就是我们想要的解。
代码如下：
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
## Swaps with 0 allowed (only by commenting
## out the code above I get 52)
return Node(self.g, self.r)
def exchange(self):
if self.r >= 3:
return Node(self.r - 3, self.g + 2)
return None
def neighbours(self):
s = self.swap()
e = self.exchange()
n = []
for el in [s, e]:
if el is not None:
n.append(el)
return n
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)
dfs_visited = set()
max_len = [0] ## need a mutable data structure
def dfs(s, curr_len):
for n in s.neighbours():
if curr_len > max_len[0]:
max_len[0] = curr_len
if n not in dfs_visited:
dfs_visited.add(n)
dfs(n, curr_len+1)
return max_len[0]
print(dfs(start, 0))
52
我一直在尝试解决麻省理工学院的计算机科学数学问题集，这是其中一个问题：
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:
- Exchange: If he has 3 red beads in his bowl, then he may exchange 3 red beads for 2 green beads.
- 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.
这里有子问题：
- 证明没有人离开过圣殿。我用数学归纳法证明了这一点。
- 证明这个问题只能达到有限的状态。这个证明也是通过使用数学归纳法来完成的，并证明了红色珠子和绿色珠子的数量之和只能减少或保持不变。
- （这就是我卡住的地方）在永恒神殿机器的任何执行中，僧侣可以访问的唯一状态的真实最大数量是多少？
在花了相当多的时间试图思考子问题 #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).
我的程序哪里出错了？我对问题陈述的理解是否不正确（根据我编写的程序）？另外，我真的不明白他们给出的解决方案。有没有更好的方法来解释它？例如，我不明白的 issues/things 之一是，解决方案指出每次交换操作珠子的总和减少 1。因此我们可以通过交换操作获得 25 个新状态。但是图中每个级别的每个总和都可以用多种方式表示，是吗？那么一定有更多的状态是由交换操作创建的吗？这是 link to the full problem set and it's solution.
编辑： 根据 OP 自己的回答和我们在评论中的讨论，这是关键问题：
我们必须区分两个不同的数字：
- 和尚可以走的任何一条路的最大访问状态数n;
- 和尚可以达到的状态总数N。
请注意，N 是在任何一条路径中访问的状态集的并集（采用所有可能的路径）的基数。这意味着 n <= N，很容易看出这些数字不相等。麻省理工学院的问题询问 n，而 OP 的原始代码旨在查找 N.
引用的证明是正确的，所以"an upper bound on [n] is 25 + 26 + 1 = 52"。
我尝试了一种Monte Carlo方法来近似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
更新： 这是完整状态的图 space。 N = 140
这是一条访问 52 个州的路径。绿色的 X 是起点，每个蓝色圆圈标记一个访问状态。由于我们从引用的证明中知道 n <= 52，这证明了 n = 52.
问题中的代码构建的图表连接了每个可能的状态，因此计算了状态机可能的状态总数，但不是僧侣在任何执行圣殿时可以访问的唯一状态的最大数量永远的机器。
通过以类似 BFS 的方式对节点进行计数，我假设可以通过任何其他状态到达每个状态。事实并非如此。在交换操作创建新状态后，不可能通过交换返回到它的 "parent" 状态（显然），因此一旦在锣声中做出选择，就没有了任何回去。
因此，我们真正需要做的是构建图形并从起始节点执行 DFS，并跟踪我们在 DFS 遍历期间达到的最大深度。这个最大深度就是我们想要的解。
代码如下：
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
## Swaps with 0 allowed (only by commenting
## out the code above I get 52)
return Node(self.g, self.r)
def exchange(self):
if self.r >= 3:
return Node(self.r - 3, self.g + 2)
return None
def neighbours(self):
s = self.swap()
e = self.exchange()
n = []
for el in [s, e]:
if el is not None:
n.append(el)
return n
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)
dfs_visited = set()
max_len = [0] ## need a mutable data structure
def dfs(s, curr_len):
for n in s.neighbours():
if curr_len > max_len[0]:
max_len[0] = curr_len
if n not in dfs_visited:
dfs_visited.add(n)
dfs(n, curr_len+1)
return max_len[0]
print(dfs(start, 0))
52