1

我讨厌问这样的问题，因为我觉得我真的应该自己找出解决方案，但我真的不知道这段代码到底有什么问题。我希望重新审视它会发现一些我认为理所当然的功能存在的缺陷。

该程序的目标是执行图形搜索以解决经典谜语。它从所有四个布尔值设置为假的父节点开始，目标是让它们都设置为真。这是通过查找节点的所有有效子节点（基于验证函数）并将它们放入节点的“树”列表中来完成的。父节点也被放入“已探索”节点列表中。

在寻找下一个要使用的子节点时，循环会在树列表中查找并找到成本最低的值，同时忽略已探索列表中的任何节点。在找到具有最低成本的下一个节点后，它将其作为新的父节点返回，并且循环再次开始。到达目标节点后，循环退出，构建到目标节点的路径，并以特殊格式打印。

这就是应该发生的一切，但是当我运行程序时，它只是无限地继续下去。基于一些调试，我认为我的循环存在问题，无法找到新的父节点。第一个父节点工作正常，它是有效的父节点，并获得创建的第一批子节点并将其添加到树列表中。一旦选择了第二个（根据我的计算并通过打印测试确认是一个“无效”节点），进度如下：

  1. 没有找到新的子节点（这是无效父节点的预期功能）

  2. 父级未添加到树列表中，因为它已经存在（再次，预期功能）

  3. 父级被添加到探索列表中，因为它还没有在那里找到（预期的功能，到目前为止一切都很好）

  4. 出现选择下一个父级的循环，这是出错的地方

据我所知，选择新父级的循环只是不断地一遍又一遍地选择同一个第二个父级。我已经通过打印测试进行了调试，发现整个 while 循环只会永远选择和拒绝完全相同的节点，即使它不应该多次选择它（因为它被添加到探索列表中）。

我的清单有什么问题我没有看到吗？这是供参考的代码。感谢任何可以帮助我的人！

#for parent is not equal to goal
while not isGoal(parent):
    if validate(parent, explored):  
        getchildren(parent)
        #print parent.farmer

    #add parent to explored nodes
    if parent not in explored:
        explored.append(parent)
    if parent not in tree:
        tree.append(parent)
        #print parent.farmer

    #find next node to explore

    temp = node()
    temp.cost = sys.maxint  #this ensures that the first temp is always replaced by the first unexplored tree node
    for i in range(0, len(tree)):
            if tree[i] not in explored and tree[i].cost <= temp.cost:
                tree[i].copy(temp)
                #print temp.farmer, temp.wolf, temp.sheep, temp.cabbage
    temp.copy(parent)

#now return to the top of the while and do it again

编辑：这是所要求的类定义：

class node:
    def __init__(self):
        self.farmer, self.wolf, self.sheep, self.cabbage = False, False, False, False
        self.parent = None
        self.cost = 0
    def copy(self, child):
        child.farmer = self.farmer
        child.wolf = self.wolf
        child.sheep = self.sheep
        child.cabbage = self.cabbage
        child.parent = self
        child.cost = self.cost

没有eq功能。

编辑：我添加了这个 eq 函数：

def __eq__(self, node):
        if self.farmer == node.farmer and self.wolf == node.wolf and self.sheep == node.sheep and self.cabbage == node.cabbage:
            return True
        return False

并在节点中更改了此代码：

for i in range(0, len(tree)):
        for j in range(0, len(explored)):
            if tree[i].__eq__(explored[j]) is False and tree[i].cost <= temp.cost:
                tree[i].copy(temp)
                #print temp.farmer, temp.wolf, temp.sheep, temp.cabbage
    temp.copy(parent)

但这对我没有任何改变，问题仍然存在。

4

0 回答 0