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 所需的一切，没有任何奇怪的事情发生，所以我真的怀疑这是问题所在。所有函数 return 整数（尽管它们使用 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比较；抛出异常的是 that comparison，因为 numpy array 对象将逐个元素进行比较，并生成具有 true 和 false 结果的布尔数组。如果堆中存在 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()

当您更改元组第一个位置的值时，问题 'disappeared' 使前两个值与堆中已有的值相比再次变得唯一。但它并没有真正解决根本问题。

您可以通过在数组前插入一个唯一计数（使用 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)。

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

Python heapq heappush The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

python

heap

numpy