Python中的深度优先搜索 [英] Depth-First search in Python

问题描述

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

I'm trying to do a Depth-First search in Python but it's not working.

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

Basically we have a peg-solitaire board:

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

1表示一个钉子，0是一个空位。您必须一次将钉子向后移动两个插槽，或仅向前移动到一个空白位置。如果您在此过程中越过另一个挂钩，它将变成一个空插槽。您执行此操作，直到剩下一个钉子为止。所以基本上，游戏就像：

1's represent a peg, and 0 is an open spot. You must move a peg one at a time TWO SLOTS backwards or forward ONLY to an empty spot. If you jump over another peg in the process it becomes an empty slot. You do this until one peg remains. So basically, a game goes like:

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

所以，现在我的问题是：

So, now my questions:

1. 这是进行深度优先搜索的正确方法吗？


2. 我的算法不起作用！！！卡住了。几天来，我一直在苦苦挣扎，然后再问这里，请帮忙。


3. 好像我没有关注DRY，有什么建议吗？


4. omg帮帮我吗？

1. Is this the right way to do a Depth-First search for this?
2. My algorithm doesn't work!!! It gets stuck. I've been struggling on this for days before asking here so please help.
3. Looks like I'm not following DRY, any suggestions?
4. omg help me?

推荐答案

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

The normal way to implement DFS in a situation where each step is a "move" from a "board position" to some possible next one, until a goal is reached, is as follows (pseudocode)

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

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

You probably also want to keep backward links to be able to emit, at the end, the series of moves leading to the found solution (if any), but that's an ancillary problem.

我不认识这种总体结构的痕迹（或其合理的变体） ）。为什么不尝试以这种方式记录它？您只需要编写可能继任者和 isending 的代码（如果您坚持要保持列表的位置，则必须将它变成一个元组，以检查set中的成员资格并添加到set中，但这是相当小的；-）。

I don't recognize a trace of this general structure (or reasonable variant thereof) in your code. Why not try to record it this way? You only need to code possiblesuccessors and isending (if you insist on keeping a position as a list you'll have to turn it into a tuple to check membership in set and add to set, but, that's pretty minor;-).

这篇关于Python中的深度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！