5

我正在尝试在 Python 中进行深度优先搜索，但它不起作用。

基本上我们有一个钉子纸牌板：

[1,1,1,1,1,0,1,1,1,1]

1 代表挂钩，0 代表空位。您必须一次将一个钉子向后或向前移动两个槽位到一个空位。如果您在此过程中跳过另一个挂钩，它将成为一个空槽。你这样做直到剩下一个钉子。所以基本上，一个游戏是这样的：

[1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1] #etc until only 1 peg left

这是我所拥有的：

class MiniPeg():
    def start(self):
        ''' returns the starting board '''
        board = [1,1,1,1,1,0,1,1,1,1]
        return board

    def goal(self, node):
        pegs = 0

        for pos in node:
            if pos == 1:
                pegs += 1

        return (pegs == 1) # returns True if there is only 1 peg

    def succ(self, node):
        pos = 0
        for peg in node:
            if peg == 1:                
                if pos < (len(node) - 2):  # try to go forward
                    if node[pos+2] == 0 and node[pos+1] == 1:
                        return create_new_node(node, pos, pos+2)

                if pos > 2: # try to go backwards 
                    if node[pos-2] == 0 and node[pos-1] == 1:
                        return create_new_node(node, pos, pos-2)
        pos += 1

def create_new_node(node, fr, to):
    node[fr] = 0
    node[to] = 1
    if fr > to:
        node[fr-1] = 0
    else:
        node[fr+1] = 0
    return node

if __name__ == "__main__":
    s = MiniPeg()
    b = s.start()

    while not s.goal(b):
        print b
        b = s.succ(b)

所以，现在我的问题：

  1. 这是进行深度优先搜索的正确方法吗？
  2. 我的算法不行！！！它卡住了。在问这里之前，我已经为此苦苦挣扎了几天，所以请帮忙。
  3. 看起来我没有关注 DRY，有什么建议吗？
  4. 天哪，帮帮我？
4

4 回答 4

10

在每个步骤都是从“棋盘位置”到某个可能的下一个“移动”直到达到目标的情况下，实现 DFS 的正常方法如下（伪代码）

seenpositions = set()
currentpositions = set([startingposition])
while currentpositions:
  nextpositions = set()
  for p in currentpositions:
    seenpositions.add(p)
    succ = possiblesuccessors(p)
    for np in succ:
      if np in seenpositions: continue
      if isending(np): raise FoundSolution(np)
      nextpositions.add(np)
  currentpositions = nextpositions
raise NoSolutionExists()

您可能还希望保留反向链接，以便能够在最后发出一系列导致找到的解决方案（如果有的话）的移动，但这是一个辅助问题。

我在您的代码中没有识别出这种一般结构（或其合理变体）的痕迹。为什么不尝试以这种方式记录呢？您只需要编写代码possiblesuccessors并且isending（如果您坚持将位置保留为列表，则必须将其转换为元组以检查集合中的成员资格并添加到集合中，但是，这非常小；-)。

于 2010-01-26T06:17:07.337 回答
1

您似乎没有创建新节点，只是重新使用现有节点。DFS 需要某种堆栈（调用堆栈或您自己的堆栈）。哪里是？

于 2010-01-26T06:05:33.703 回答
0

好吧，首先深度优先搜索假设一棵树。现在，这是有道理的，因为在大多数情况下你有几个可能的动作。深度优先搜索将简单地尝试第一个可能的移动，然后尝试在新情况下的第一个可能的移动，以及在该新情况下的第一个可能的移动，直到成功或没有更多可能的移动，在这种情况下它将备份直到它找到了一个它没有尝试过的动作，然后再次下降。

这样做的“正确”方法是递归。据我所知，您的系统中没有递归。

像这样的东西会起作用（pythonic psuedo codeish english）：

def try_next_move(self, board):
    for each of the pegs in the board:
        if the peg can be moved:
            new_board = board with the peg moved
            if new_board is solved:
                return True
            if self.try_next_move(new_board):
                return True
            # That move didn't lead to a solution. Try the next.
    # No move  worked.
    return False
于 2010-01-26T06:11:42.497 回答
0

基本的算法问题是该succ函数对于给定的棋盘状态总是只产生一个可能的移动。即使有多个可能的移动，该succ函数也只会返回它可以找到的第一个。深度优先搜索需要处理每个状态下所有可能的移动。

进一步的问题可能来自这样一个事实create_new_node，尽管它的名字，并没有真正创建一个新节点，而是修改了现有的节点。对于深度优先搜索，如果此函数实际上创建了它作为参数获取的列表的副本，那么您希望将前一个节点保留在其周围会更好。

此外，在检查是否有可能倒退时succ，您仅在 时才尝试这样做pos > 2。太严格了，pos > 1也可以。

于 2010-01-26T06:19:56.823 回答