As pointed out by #919 and #941, A* search is behaving incorrectly. This is partly due to the way the A* implementation interfaces with the PriorityQueue (in utils.py). Due to how __contains__ is implemented in PriorityQueue, if the heuristic function passed to A* produces non-unique values for the same state (As in the case of #919), A* would re-visit the same state multiple times.
#829 also raises some concerns about the implementation of __getitem__ and __contains__ in PriorityQueue. While these methods seem similar, they are quite distinct. Using __getitem__ instead of __contains__ should fix A*. However, since both these functions are confused many times (#828), we should include at least some documentation and test cases to illustrate this use. Another solution to this confusion would be altering the roles of __getitem__ and __contains__ such that for a priority queue A and element x:
-
x in A returns whether a copy is present regardless of its function value
-
A[x] returns the function value of a copy if it is present in the queue, else throws a KeyError like other dicts in python.
As pointed out by #919 and #941, A* search is behaving incorrectly. This is partly due to the way the A* implementation interfaces with the PriorityQueue (in utils.py). Due to how
__contains__is implemented in PriorityQueue, if the heuristic function passed to A* produces non-unique values for the same state (As in the case of #919), A* would re-visit the same state multiple times.#829 also raises some concerns about the implementation of
__getitem__and__contains__in PriorityQueue. While these methods seem similar, they are quite distinct. Using__getitem__instead of__contains__should fix A*. However, since both these functions are confused many times (#828), we should include at least some documentation and test cases to illustrate this use. Another solution to this confusion would be altering the roles of__getitem__and__contains__such that for a priority queue A and element x:x in Areturns whether a copy is present regardless of its function valueA[x]returns the function value of a copy if it is present in the queue, else throws aKeyErrorlike other dicts in python.