Python heapq heappush 多元素数组真值不明确使用 a.any() 或 a.all()

Question

我遇到了 heapq 库的错误——尤其是 heappush 函数。错误代码(下方)对我没有任何帮助。

(Pdb) heapq.heappush(priority_queue, (f, depth, child_node_puzzle_state))
*** ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

这是导致问题的代码片段...

h = compute_heuristic(child_node_puzzle_state, solved_puzzle)
depth = current_node[1] + 1
f = h + depth
heapq.heappush(priority_queue, [f, depth, child_node_puzzle_state])

我应该注意到 h 和 depth 是 int 而 child_node_puzzle_state 是一个 numpy 数组。查看一些调试代码...

(Pdb) child_node_puzzle_state
array([[  5.,   4.,  18.,  15.,   0.,   0.,   0.,   0.,   0.,   0.,   0.,
         99.],
       [ 99.,  10.,   6.,  14.,  12.,  20.,   0.,   0.,   0.,   0.,  99.,
         99.],
       [ 99.,  99.,  11.,  19.,  17.,  16.,   8.,   0.,   0.,  99.,  99.,
         99.],
       [ 99.,  99.,  99.,   2.,   3.,   0.,   0.,   0.,  99.,  99.,  99.,
         99.],
       [ 99.,  99.,  99.,  99.,   1.,  21.,   0.,  99.,  99.,  99.,  99.,
         99.],
       [ 99.,  99.,  99.,  99.,  99.,   9.,  13.,   7.,   0.,   0.,   0.,
          0.]])
(Pdb) child_node_puzzle_state.dtype
dtype('float64')
(Pdb) p h
3
(Pdb) depth
2
(Pdb) f
5
(Pdb) priority_queue
[(5, 2, array([[  9.,  15.,   0.,   0.,   0.,   0.,   0.,   0.,   0.,   0.,   0.,
         99.],
       [ 99.,  10.,   6.,  14.,   5.,   4.,  18.,   0.,   0.,   0.,  99.,
         99.],
       [ 99.,  99.,  11.,  19.,  17.,  12.,  20.,   8.,   0.,  99.,  99.,
         99.],
       [ 99.,  99.,  99.,  16.,   3.,   0.,   0.,   0.,  99.,  99.,  99.,
         99.],
       [ 99.,  99.,  99.,  99.,   2.,   0.,   0.,  99.,  99.,  99.,  99.,
         99.],
       [ 99.,  99.,  99.,  99.,  99.,   1.,  21.,  13.,   7.,   0.,   0.,


...

(Pdb) len(priority_queue)
9

这是我想不通的……如果我改变一点点它就可以工作——但它在语义上是错误的。这是变化......

h = compute_heuristic(child_node_puzzle_state, solved_puzzle)
depth = current_node[1] + 1
heapq.heappush(priority_queue, (h, depth, child_node_puzzle_state))

你看出区别了吗？我没有计算 f = h + depth，而是使用 h。它神奇地起作用了吗？

这不可能是大小，因为正如我在调试中展示的...

(Pdb) len(priority_queue)
9

---

这对我来说真的没有意义，所以我将包含更多代码。首先，这是计算 h 所需的一切，没有任何奇怪的事情发生，所以我真的怀疑这就是问题所在。所有函数都返回整数(尽管它们使用 numpy 数组)...

def tubes_aligned(puzzle_state):

    current_index = 3 #test for index 3
    blue_tube = puzzle_state[3,:]
    len_of_top_tube = len(blue_tube[blue_tube < 99]) - 3
    correct_index = 6 - len_of_top_tube

    found = False
    distance = 3
    for i in range(3):
        if i == correct_index:
            distance = current_index - i
            found = True

    if not found:
        for i in range(5,2,-1):
            if i == correct_index:
                distance = i - current_index

    return distance

def balls_in_top_half(puzzle_state):

    for i in range(6):
        full_tube = puzzle_state[i,:]
        num_balls = full_tube[full_tube < 99]
        num_balls = len(num_balls[num_balls > 0])
        if (6 - i - num_balls) != 0:
            return 1

    return 0

def balls_in_correct_place(puzzle_state, solved_puzzle):
    if is_solved(puzzle_state, solved_puzzle):
        return 0
    else:
        return 1

def compute_heuristic(puzzle_state, solved_puzzle):
    # print "computing heuristic"
    # heuristic (sum all three):
    #     1. how many tubes is the puzzle state from tubes being aligned -- max is 3
    #     2. is there balls in the top portion? 1 -- yes || 0 -- no
    #     3. are there balls in the wrong place in the bottom half? 1 -- yes || 0 -- no
    part_1 = tubes_aligned(puzzle_state)
    part_2 = balls_in_top_half(puzzle_state)
    part_3 = balls_in_correct_place(puzzle_state, solved_puzzle)
    return part_1 + part_2 + part_3

Answer 1

heapq.heappush将比较一个数组与堆中的其他数组，如果您推送的元组中的前面元素在其他方面是相等的。

这是 heappush() 的纯 Python 实现:

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

实际的实现将在 C 中，这就是为什么您在没有更深入的回溯的情况下得到错误的原因。

注意 newitem < parent比较;是 那个比较 抛出异常，如 numpy array对象将逐个元素进行比较，并生成一个具有 true 和 false 结果的 bool 数组。如果您的堆中有一个状态 f和 depth相等，该比较必须比较数组:

>>> import numpy
>>> t1 = (5, 2, numpy.array([9.,  15.]))
>>> t2 = (5, 2, numpy.array([10.,  15.]))
>>> t1 < t2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

对于您来说，当您更改元组第一个位置的值时，问题“消失”了，与堆中已有的值相比，前两个值再次变得唯一。但它实际上并没有解决根本问题。

您可以通过在数组前插入一个唯一计数(使用 itertools.count() )来避免此问题:

from itertools import count

# a global
tiebreaker = count()

# each time you push
heapq.heappush(priority_queue, (f, depth, next(tiebreaker), child_node_puzzle_state))

计数器确保元组的前三个元素始终是唯一的。这也意味着任何后来添加到堆中的与启发式分数和深度上的已经存在的状态相匹配的内容都会排在较旧的之前。您可以使用 count(step=-1)如果你想反转这种关系。