0

状態になっているかどうかを確認するO（1）メソッドが必要です。問題は、状態がマップ上のいくつかのズームビニスの位置によって定義されることです。Zoombini = {（1,1）：0、（2,2）：1、（3,3）：3} {位置：Zoombini ID}幅優先探索を使用しており、この位置の辞書をキューにプッシュしています。

dirs = [goNorth, goSouth, goWest, goEast] ## List of functions
zoom = {}
boulders = {}
visited = {} ## {(zoom{}): [{0,1,2},{int}]}
             ## {Map: [color, distance] 0 = white, 1 = gray, 2 = black
n = len(abyss)
for i in xrange(n):
    for j in xrange(n):
        if (abyss[i][j] == 'X'):
            boulders[(i,j)] = True
        elif (isInt(abyss[i][j])):
            zoom[(i,j)] = int(abyss[i][j])      ## invariant only 1 zomb can have this position
        elif (abyss[i][j] == '*'):
              exit = (i, j)
sQueue = Queue.Queue()
zombnum = 0
done = False
distance = 0
sQueue.put(zoom)
while not(sQueue.empty()):
    currZomMap = sQueue.get()
    for zom in currZomMap.iterkeys(): ## zoom {(i,j): 0}
        if not(zom == exit):
            z = currZomMap[zom]
            for fx in dirs: ## list of functions that returns resulting coordinate of going in some direction
                newPos = fx(zom)
                newZomMap = currZomMap.copy()
                del(newZomMap[zom]) ## Delete the old position
                newZomMap[newPos] = z ## Insert new Position
                if not(visited.has_key(newZomMap)):
                    sQueue.put(newZomMap)

私の実装は完了していませんが、すでに州を訪問したかどうかを確認するためのより良い方法が必要です。辞書から整数ハッシュを作成する関数を作成することはできますが、効率的に作成できるとは思いません。時間も問題です。どうすればこれを最適に行うことができますか？

4

2 に答える 2

1

壊れやすいカスタムハッシュ関数を作成するのではなく、おそらく：を使用しますfrozenset。

>>> Z = {(1,1): 0, (2,2):1, (3,3):3}
>>> hash(Z)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> frozenset(Z.items())
frozenset([((2, 2), 1), ((1, 1), 0), ((3, 3), 3)])
>>> hash(frozenset(Z.items()))
-4860320417062922210

フリーズセットは、問題なくセットとディクテーションに保存できます。から構築されたタプルを使用することもできますが、Z.items()常に正規の形式で保存されていることを確認する必要があります（たとえば、最初にソートすることによって）。

于 2012-11-06T04:16:58.117 に答える
0

Pythonでは可変キーが許可されていないため、辞書をハッシュする関数を作成することになりました。

編集 - 

def hashthatshit(dictionary):
result = 0
i =0
for key in dictionary.iterkeys():
    x = key[0]
    y = key[1]
    result+=x*10**i+y*10**(i+1)+\
             10**(i+2)*dictionary[key]
    i+=3
return result

私はこれを自分の実装に固有のものとして使用しました。そのため、元々はそれを含めませんでした。

于 2012-11-06T02:59:15.797 に答える