python Python中的深度优先搜索
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2137731/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Depth-First search in Python
提问by y2k
I'm trying to do a Depth-First search in Python but it's not working.
我正在尝试在 Python 中进行深度优先搜索，但它不起作用。
Basically we have a peg-solitaire board:
基本上我们有一个挂钩纸牌：
[1,1,1,1,1,0,1,1,1,1]
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 代表挂钩，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
Here's what I have:
这是我所拥有的：
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:
所以，现在我的问题：
- Is this the right way to do a Depth-First search for this?
- My algorithm doesn't work!!! It gets stuck. I've been struggling on this for days before asking here so please help.
- Looks like I'm not following DRY, any suggestions?
- omg help me?
- 这是进行深度优先搜索的正确方法吗？
- 我的算法不行！！！它卡住了。在问这里之前，我已经为此苦苦挣扎了好几天，所以请帮忙。
- 看起来我没有关注 DRY，有什么建议吗？
- 天哪帮帮我？
回答by Alex Martelli
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)
在每一步都是从“棋盘位置”“移动”到下一个可能的位置，直到达到目标的情况下，实现 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()
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.
您可能还希望保留向后链接，以便最终能够发出导致找到的解决方案（如果有）的一系列移动，但这是一个辅助问题。
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 possiblesuccessorsand 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;-).
我在您的代码中没有识别出这种一般结构（或其合理的变体）的痕迹。为什么不尝试以这种方式记录呢？你只需要编码possiblesuccessors和isending（如果你坚持将一个位置作为一个列表，你必须把它变成一个元组来检查集合中的成员资格并添加到集合中，但是，这很次要；-）。
回答by Justin W
It doesn't appear that you're creating new nodes, just re-using existing ones. DFS requires some kind of stack (either the call stack, or your own stack). Where is that?
您似乎没有在创建新节点，只是重新使用现有节点。DFS 需要某种堆栈（调用堆栈或您自己的堆栈）。哪里是？
回答by Lennart Regebro
Well, first of all a depth-first search assumes a tree. Now, that makes sense here as you have several possible moves in most cases. A depth first-search would simply try the first possible move, and then the first possible move in the new situation, and the first possible move in that new situation, until success or no more possible moves, in which case it would back up until it finds a move it hasn't tried, and go down again.
好吧，首先深度优先搜索假设一棵树。现在，这是有道理的，因为在大多数情况下您有几种可能的移动。深度优先搜索将简单地尝试第一个可能的移动，然后是新情况下的第一个可能的移动，以及该新情况下的第一个可能的移动，直到成功或没有更多可能的移动，在这种情况下它会返回直到它找到一个它没有尝试过的移动，然后再次下降。
The "correct" way of doing that is with recursion. You have no recursion in your system as far as I can see.
这样做的“正确”方法是递归。据我所知，您的系统中没有递归。
Something like this would work (pythonic psuedo codeish english):
像这样的东西会起作用（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
回答by sth
The basic algorithmic problem is that the succfunction always only produces just one possible move for a given board state. Even if there would be more than one possible moves, the succfunction just returns the first one it can find. A depth first search needs to process all possible moves in each state.
基本的算法问题是succ对于给定的棋盘状态，函数总是只产生一个可能的移动。即使有多个可能的移动，该succ函数也只返回它可以找到的第一个移动。深度优先搜索需要处理每个状态下所有可能的移动。
Further problems might then come from the fact that create_new_node, despite it's name, doesn't really create a new node, but modifies the existing one. For depth first search where you want to keep the previous node around it would be better if this function actually created a copy of the list it get's as a parameter.
进一步的问题可能来自这样一个事实，即create_new_node尽管它的名字，并没有真正创建一个新节点，而是修改现有节点。对于想要保留前一个节点的深度优先搜索，如果此函数实际上创建了它作为参数获取的列表的副本，则会更好。
Also, when checking for the possibility to go backwards in succ, you only try to do so if pos > 2. That's too restrictive, pos > 1would also be ok.
此外，在检查向后倒退的可能性时succ，您仅在时才尝试这样做pos > 2。太严格了，pos > 1也可以。
