我怎样才能加快 8 拼图问题的错位磁贴启发式算法？

Question

我的列表的长度始终为 8（7 个索引），并且始终包含数字 0-8

我目前这样做是为了找到错放的瓷砖的总和：

def misplacedTilesHeuristic(stateObj, goal):
    sum = 0

    for elem in range(len(goal)):
        if goal[elem] != stateObj[elem]:
            sum+=1

    return sum

我怎样才能让它更快？

编辑：

misplacedTilesHeuristic((4, 5, 3, 1, 0, 6, 7, 2, 8), (0, 1, 2, 3, 4, 5, 6, 7, 8))

Answer 1

如前所述，one-liner 是个好主意，例如：

def comp(stObj,goal):
    sum = 0
    for elem in range(len(goal)):
        if goal[elem] != stObj[elem]:sum +=1
    return sum

def prop1(stObj,goal):
    sum = 0
    for i,j in zip(stObj,goal):
        if i !=j:sum +=1
    return sum

def prop2(stObj,goal):
    return sum([i!=j for i, j in zip(stObj,goal)])

def prop3(stObj,goal):
    return sum([i is not j for i, j in zip(stObj,goal)])

def prop4(stObj,goal):
    return sum(map(lambda x, y: x != y, stObj, goal))

t = (4, 5, 3, 1, 0, 6, 7, 2, 8), (0, 1, 2, 3, 4, 5, 6, 7, 8)

基准：

%timeit comp(*t)
1.64 µs ± 46.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit prop1(*t)
1.22 µs ± 27.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
%timeit prop2(*t)
1.67 µs ± 86.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit prop3(*t)
1.6 µs ± 48.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit prop4(*t)
1.79 µs ± 32.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

prop1() 显示了目前最好的时间，性能提高了近 34.4%，但我认为它可能会更好:)

我怎样才能加快 8 拼图问题的错位磁贴启发式算法？

How can I speed up my misplaced tiles heuristic for the 8 puzzle problem?

python

heuristics

sliding-tile-puzzle