如何表示汉诺塔的不同可能运动（状态）？

Question

我正在尝试编写代码通过使用 UCS 和 A* 算法来解决 ToH 问题，然后比较结果。所以，我应该做的第一件事就是将可能的运动表示为一棵树，然后 UCS 和 A* 算法可以轻松地通过树。

假设我们有 3 个堆栈和 5 个磁盘，那么初始状态将是：

# The Num of stacks is the number of elements in the list.
# The Num of disks is the length of each element in the list.
key = ["12345","00000","00000"]
#         A       B        C

我需要的是建立一个函数来预测接下来可能的走势，所以下一步可能是：

["12340","00005","00000"] or ["12340","00000","00005"]
# so these states will saved as:
dic ={}
x= repr(key)
dic[x] = ["12340","00005","00000"]
# the result:
# ["12345","00000","00000"] : ["12340","00005","00000"]

我试过这个天真的代码：

# there are bugs but I am still working on it 
for indx, block in enumerate(key):
    for i, char in enumerate(reversed(block)):
        if char != "0":
            for indx2, block2 in enumerate(key):
                if indx2 == indx: pass
                for ii, char2 in enumerate(reversed(block2)):
                    if char2 == "0":
                        temp=block[i]
                        block[i]= block2[ii]
                        block2[ii]=temp
                        print(key)

是否有任何伪代码或想法可以提供帮助？

Answer 1

为了解决汉诺塔问题，无需构建状态图，因为有一个数学公式可以确定下一步要采取的行动。

不过，如果您要制作图表，那么我建议将密钥缩短为这种格式：12345||。管道将桩分开。所以如果你将 5 移动到中间堆栈，它的键将是 1234|5|。如果然后将 4 移动到最后一叠：123|5|4，...等

在创建图表的过程中，您可以切换到列表的列表，如[["1","2","3"], [], []]，这样更容易操作。您使用字典的想法很好，但是，一个状态可能有多个有效移动，因此您需要一个状态列表。

图中的节点通常用 Node class 实现，因此我建议使用以下代码：

class Node:
    def __init__(self, key):
        self.key = key
        self.children = []

def create_tree(stacks, tree=None):
    if not tree:
        tree = {}
    key = "|".join(["".join(discs) for discs in stacks])
    if key in tree:  # this node was already created
        return tree[key]
    tree[key] = node = Node(key)
    for source in stacks:
        if source:
            disc = source[-1]
            for target in stacks:
                if not target or disc > target[-1]:
                    # perform the move:
                    target.append(source.pop())
                    # recursion
                    node.children.append(create_tree(stacks, tree))
                    # undo the move
                    source.append(target.pop())
    return node


root = create_tree([["1","2","3","4","5"], [], []])

在运行之后，root 将是一个 Node 实例，其 children 属性中有两个节点。每个 children 都会有三个 children，包括对根的反向引用，代表反向移动。

我在实现中隐藏了字典（称为 tree）。如果您觉得需要访问它，那么您当然可以将其设为 non-local 变量，或将其作为参数传递。

如何表示汉诺塔的不同可能运动（状态）？

How to represent different possible movement (state) of Tower of Hanoi?

python

tree

recursion

artificial-intelligence