0

私は、 8パズル問題の解決策を見つけるために、反復深化深さ優先探索の実装に取り​​組んでいます。私は実際の検索パス自体を見つけることに興味はありませんが、プログラムの実行にかかる時間を計るだけです。（私はまだタイミング機能を実装していません）。

ただし、実際の検索機能を実装しようとすると問題が発生します（下にスクロールして表示）。これまでに持っているすべてのコードを貼り付けたので、これをコピーして貼り付けると、実行することもできます。これは、私が抱えている問題を説明するための最良の方法かもしれません...たとえば、最初の展開が必要なパズル2（p2）のテストで、再帰中に無限ループが発生する理由がわかりません。解を生成します。コード行の1行の前に「Return」を追加しないことと関係があるのではないかと思いました（以下にコメントがあります）。リターンを追加すると、パズル2のテストに合格できますが、パズル3のようなより複雑なものは失敗します。これは、コードが左端のブランチのみを展開しているように見えるためです...

何時間もこれにいて、希望をあきらめました。私はこれについて別の目で見ていただければ幸いです。私の誤りを指摘していただければ幸いです。ありがとうございました！

#Classic 8 puzzle game
#Data Structure: [0,1,2,3,4,5,6,7,8], which is the goal state. 0 represents the blank
#We also want to ignore "backward" moves (reversing the previous action)

p1 = [0,1,2,3,4,5,6,7,8]
p2 = [3,1,2,0,4,5,6,7,8]
p3 = [3,1,2,4,5,8,6,0,7]

def z(p):   #returns the location of the blank cell, which is represented by 0
    return p.index(0)

def left(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc-1]
    p[zeroLoc-1] = 0
    return p

def up(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc-3]
    p[zeroLoc-3] = 0
    return p

def right(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc+1]
    p[zeroLoc+1] = 0
    return p

def down(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc+3]
    p[zeroLoc+3] = 0
    return p

def expand1(p):   #version 1, which generates all successors at once by copying parent
    x = z(p)
    #p[:] will make a copy of parent puzzle
    s = []  #set s of successors

    if x == 0:
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 1:
        s.append(left(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 2:
        s.append(left(p[:]))
        s.append(down(p[:]))
    elif x == 3:
        s.append(up(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 4:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 5:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(down(p[:]))   
    elif x == 6:
        s.append(up(p[:]))
        s.append(right(p[:]))
    elif x == 7:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(right(p[:]))
    else:   #x == 8
        s.append(left(p[:]))
        s.append(up(p[:]))

    #returns set of all possible successors
    return s

goal = [0,1,2,3,4,5,6,7,8]

def DFS(root, goal):    #iterative deepening DFS
    limit = 0
    while True:
        result = DLS(root, goal, limit)
        if result == goal:
            return result
        limit = limit + 1

visited = []

def DLS(node, goal, limit):    #limited DFS
    if limit == 0 and node == goal:
        print "hi"
        return node
    elif limit > 0:
        visited.append(node)
        children = [x for x in expand1(node) if x not in visited]
        print "\n limit =", limit, "---",children   #for testing purposes only
        for child in children:
            DLS(child, goal, limit - 1)     #if I add "return" in front of this line, p2 passes the test below, but p3 will fail (only the leftmost branch of the tree is getting expanded...)
    else:
        return "No Solution"

#Below are tests

print "\ninput: ",p1
print "output: ",DFS(p1, goal)

print "\ninput: ",p2
print "output: ",DLS(p2, goal, 1)
#print "output: ",DFS(p2, goal)

print "\ninput: ",p3
print "output: ",DLS(p3, goal, 2)
#print "output: ",DFS(p2, goal)
4

2 に答える 2

1

再帰で発生している当面の問題は、再帰ステップに到達したときに何も返さないことです。ただし、最初の子が解決策を見つけることが保証されていないため、最初の再帰呼び出しから無条件に値を返すことも機能しません。代わりに、子の状態で実行している再帰検索のどれが成功するかをテストする必要があります。DLS関数の終わりを変更する方法は次のとおりです。

    for child in children:
        child_result = DLS(child, goal, limit - 1)
        if child_result != "No Solution":
            return child_result

# note, "else" removed here, so you can fall through to the return from above
return "No Solution"

これを行うためのもう少し「pythonic」（およびより高速な）方法はNone、「No Solution」文字列ではなく、番兵値として使用することです。次に、テストは単純になりif child_result: return child_result、オプションで、失敗した検索のreturnステートメントを省略できます（None関数のデフォルトの戻り値であるため）。

この再帰の問題が修正されると、コードで発生する他の問題がいくつかあります。たとえば、visited別の再帰検索を再開するたびにグローバル変数をリセットしない限り、グローバル変数の使用には問題があります。しかし、私はそれらをあなたに任せます！

于 2012-10-27T22:25:17.670 に答える
0

あなたの州のクラスを使用してください！これにより、作業がはるかに簡単になります。始めるために。今すぐソリューション全体を投稿したくありませんが、これにより作業がはるかに簡単になります。

#example usage
cur = initialPuzzle
for k in range(0,5): # for 5 iterations. this will cycle through, so there is some coding to do
    allsucc = cur.succ() # get all successors as puzzle instances
    cur = allsucc[0] # expand first                                                                                           
    print 'expand ',cur 

import copy


class puzzle:

    '''
    orientation
    [0, 1, 2
     3, 4, 5
     6, 7, 8]
    '''

    def __init__(self,p):
        self.p = p

    def z(self):  
        ''' returns the location of the blank cell, which is represented by 0 '''
        return self.p.index(0)

    def swap(self,a,b):
        self.p[a] = self.p[b]
        self.p[b] = 0

    def left(self):
        self.swap(self.z(),self.z()+1) #FIXME: raise exception if not allowed

    def up(self):
        self.swap(self.z(),self.z()+3)

    def right(self):
        self.swap(self.z(),self.z()-1)

    def down(self):
        self.swap(self.z(),self.z()-3)

    def __str__(self):
        return str(self.p)

    def copyApply(self,func):
        cpy = self.copy()
        func(cpy)
        return cpy

    def makeCopies(self,s):
        ''' some bookkeeping '''
        flist = list()
        if 'U' in s:
            flist.append(self.copyApply(puzzle.up))
        if 'L' in s:
            flist.append(self.copyApply(puzzle.left))
        if 'R' in s:
            flist.append(self.copyApply(puzzle.right))
        if 'D' in s:
            flist.append(self.copyApply(puzzle.down))

        return flist

    def succ(self):
        # return all successor states for this puzzle state
        # short hand of allowed success states
        m = ['UL','ULR','UR','UDR','ULRD','UDL','DL','LRD','DR']
        ss= self.makeCopies(m[self.z()]) # map them to copies of puzzles
        return ss


    def copy(self):
        return copy.deepcopy(self)



# some initial state
p1 = [0,1,2,3,4,5,6,7,8]

print '*'*20
pz = puzzle(p1)
print pz

a,b = pz.succ()
print a,b
于 2012-10-27T22:40:58.240 に答える