获取图形中唯一状态的数量

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))

2条回答

网友

1楼 · 编辑于 2024-06-16 12:47:56

由问题中的代码构建的图形连接了每个可能的状态，因此计算了状态机可能的状态总数，但不计算僧侣在执行“永恒之殿”机器时可以访问的唯一状态的最大数量

通过以类似BFS的方式计算节点，我假设可以通过任何其他状态到达每个状态。事实并非如此。交换操作创建新状态后，不可能通过交换（显然）返回到其“父”状态，因此一旦在锣圈做出选择，就不会有任何返回

因此，我们真正需要做的是构建图，从起始节点开始执行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

网友

2楼 · 编辑于 2024-06-16 12:47:56

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

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

僧侣可以走的任何一条路径中访问状态的最大数量
僧侣能达到的状态总数

请注意，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）、（3）、（4）、（1），（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

相关问题更多 >

编程相关推荐

热门问题

热门文章