3

私は深さ優先探索を実装するさまざまな方法を試してきました。私はいくつかの実用的な方法を見つけましたが、それらはかなり退屈な辞書の仕事を含んでいました。リストを使用して新しいアイデアを開発しましたが、この実装が返すアクションが目的の結果と一致しません。コードにできるだけ明確にコメントを付けようとします。

start = problem.getStartState()            ## returns an (x, y) tuple
children = problem.getSuccessors(start)    ##returns the children of a parent node in ((start                  
                                           state), action, cost) format. 
stack = Stack()                            ##creates a Stack (LIFO) data structure
visited = []                               ##list of visited nodes
visited.append(start)
for child in children:
    stack.push((child, [], [], 0))         ##push children to fringe in the format of (child,
    while stack:                           ##path taken, actions taken, cost) 
        parent = stack.pop()
        node = parent[0]
        if parent[0] in visited: continue
        visited.append(parent[0])
        path = parent[1] + [node[0]]           ##assigns previous path/actions/cost to new 
        actions = parent[2] + [node[1]]        ##node, creating a cumulative, ordered list of
        print actions                          ##the path/actions and a cumulative cost
        cost = parent[3] + node[2]
        if problem.isGoalState(node[0]):
            print parent[2]
            return parent[2]                    ## returns list of actions 
        children = problem.getSuccessors(node[0])
        if children != []:
            for child in children:
                stack.push((child, path, actions, cost))   ##assigns cumulative lists to child

誰かが私の問題がこの実装のどこにあるのかわかりますか？ところで、私はDFSがほとんどの場合非効率的なアルゴリズムであることを知っています。しかし、この実装を正しく行うと、親ノードの子を格納するデータ構造を変更するだけで、他の検索アルゴリズムにクロスオーバーできるようになります。

4

2 に答える 2

6

CS188 pal :D ここでコードを読むのは本当に難しいです...これらすべてのインデックス %) より多くの変数を使用すると、より明確になります。私の解決策：

def depthFirstSearch(problem):
    fringe = util.Stack()
    expanded = set()
    fringe.push((problem.getStartState(),[],0))
    
    while not fringe.isEmpty():
        curState, curMoves, curCost = fringe.pop()
        
        if(curState in expanded):
            continue
        
        expanded.add(curState)
        
        if problem.isGoalState(curState):
            return curMoves
        
        for state, direction, cost in problem.getSuccessors(curState):
            fringe.push((state, curMoves+[direction], curCost))
    return []

コメントする必要がないことを願っています。読みやすいです:)良い一日を;)

于 2012-10-16T15:03:52.490 に答える
4

名前の衝突があるようです。ご了承ください：

children = problem.getSuccessors(start)    ##returns the children of a parent node in ((start                  
... 
for child in children:
    ...
    while stack:
        ...
        children = problem.getSuccessors(node[0])
        ...

最初の反復の後、元の子は内側のループの子によって上書きされるため失われます。

一般に、DFS は再帰関数を使用して実装するのが最適です。大まかに次のようになります (未テスト)。

def dfs(problem, state, visited):
    visited.append(state)

    # have we reached the goal?
    if problem.isGoalState(state):
        return [state]

    for child in problem.getSuccessors(state):
        # if child is already visited, don't bother with it
        if child in visited: continue

        # otherwise, visit the child
        ret = dfs(problem, child, visited)

        if ret is not None:
            # goal state has been reached, accumulate the states
            ret.append(state)
            return ret

    return None # failed to find solution here
    # note that Python return None by default when reaching the end of a function
于 2012-10-16T14:55:27.743 に答える