Best First Search priority queue presents a weird behavior

[kecol]

Looks like this modification to PriorityQueue.contains() method makes the Best First Search original implementation fails with the frontier management. The queue will not work as expected by BFS algorithm and the frontier will grow in size every time a repeated situation/state is found.

In class PriotityQueue

aima-python/utils.py

Lines 726 to 728 in 5889656

	def __contains__(self, item):
	"""Return True if item in PriorityQueue."""
	return (self.f(item), item) in self.heap

Inside best_first_graph_search method (lines 276 and 278).

aima-python/search.py

Lines 275 to 282 in 5889656

	for child in node.expand(problem):
	if child.state not in explored and child not in frontier:
	frontier.append(child)
	elif child in frontier:
	incumbent = frontier[child]
	if f(child) < f(incumbent):
	del frontier[incumbent]
	frontier.append(child)

[rajatjain1997]

You are correct, frontier size will increase not only in the case of BFS but also in the instances of A* algorithm where the heuristic function has different values for the same node depending on the path taken. Thanks for pointing this out. I will try to resolve this issue ASAP :-).

[dmeoli]

Resolved by #1196 (commit b57c2e5). The weird behavior was caused by PriorityQueue.__contains__ comparing the whole (f, item) tuple, so a same-state node with a different f-value failed the membership test and got appended as a duplicate (unbounded frontier growth) instead of replacing the costlier entry. __contains__/__getitem__/__delitem__ now match on the item only (via Node.__eq__, state-based), so best_first_graph_search's replacement works correctly. Verified on current master. Closing as resolved.