0

長方形グリッドのDFSを作成しようとしています。ここでは、特定の（x、y）座標から開始し、目標座標（xg、yg）に到達する必要があります。実際に私がたどった方向のリストであるパスを返す関数が必要です。

action=['Up','Left','Left','Bottom']

これまでの私のコードは次のようになります

def depthFirstSearch():
    visited=[]                # stores the vertices that I have visited  
    action=[]                 # this is what I have to return
    stack=Stack()             # the general stack used in DFS
    forward=Stack()           # stores the forward direction 
    reverse=Stack()           # stores the backward direction, in case we need to backtrack
    stack.push(getStartState())

    while not stack.isEmpty():
        tmp=stack.pop()
        if(GoalState(tmp)):
            return action
        if not tmp in visited:
            visited.append(tmp)
            if not forward.isEmpty():
                dirn=forward.pop()
                action.append(dirn)
                reverse.append(opposite(dirn))

        child1=getSuccessors(tmp)   # returns all the possible childs and direction as a list
        child2=[]

        for st in child1:
            if not st in visited:
                child2.append(st)

        if child2:
            for state in child2:
                stack.push(state[0])
                forward.push(state[1])
                reverse.push(oppposite(state[1])
        elif not child2:
            action.append(reverse.pop())

私はPythonを初めて使用するので、誰かがここで私を助けてくれたら本当にありがたいです。インデントに問題があります。また、パスを格納するためのDFSのロジックについてもよくわかりません。助けてください ！！

4

1 に答える 1

0

これは、深さ優先探索について説明している記事です。あなたがすることは次のとおりです、startあなたの場合、あなたはノードを持っています、(x,y)そしてあなたはあなたが訪問したステップが到達したかどうかをチェックしますgoalこれは(xg,yg)深さ優先探索が行う方法です、それはスタックを維持しそしてスタックに訪問された各ノードをプッシュしますそれらをポップアウトし、それが目標であるかどうかを確認します。プログラムでは、そのチェックステップをリストに書き込む必要があります。チュートリアルリンクがあなたが始めるのに役立つことを願っています。

于 2012-10-14T04:03:29.480 に答える