Heuristic searching is an AI search technique that utilizes a heuristic for its functionality. A heuristic is a general guideline that most likely prompts an answer. Heuristics assume a noteworthy role in searching strategies, in view of the exponential nature of most problems. Heuristics help to decrease a high quantity of options from an exponential number to a polynomial number. In artificial intelligence (AI), heuristic searching is of general significance, and also has specific importance. In a general sense, the term heuristic is utilized for any exercise that is regularly successful, but isn't certain to work in every situation. In heuristic search design, the term heuristic often alludes to the extraordinary instance of a heuristic evaluation function.
In Chapter 2, Understanding the Breadth-First Search Algorithm, we saw the university navigation application, with which we wanted to find our way from the Bus Stop to the AI Lab. In the BFS method, we assume that the distance between connected places is one (that is, the same). However, in reality, that is not the case. Now, let's assume that the university is designed as follows:
Figure 1
The values in green are the actual distances between the connected places. Let's go ahead and create a dictionary, storing the locations of these places:
...
#connections between places
connections = {}
connections["Bus Stop"] = {"Library"}
connections["Library"] = {"Bus Stop", "Car Park", "Student Center"}
connections["Car Park"] = {"Library", "Maths Building", "Store"}
connections["Maths Building"] = {"Car Park", "Canteen"}
connections["Student Center"] = {"Library", "Store" , "Theater"}
connections["Store"] = {"Student Center", "Car Park", "Canteen", "Sports Center"}
connections["Canteen"] = {"Maths Building", "Store", "AI Lab"}
connections["AI Lab"] = {"Canteen"}
connections["Theater"] = {"Student Center", "Sports Center"}
connections["Sports Center"] = {"Theater", "Store"}
...
In the Python NavigationData.py module, we have created a dictionary called connections; this dictionary stores the connections between places. They are similar to the connections between people that we saw in the LinkedIn connection feature application in Chapter 2, Understanding the Breadth-First Search Algorithm:
...
#location of all the places
location = {}
location["Bus Stop"] = [2, 8]
location["Library"] = [4, 8]
location["Car Park"] = [1, 4]
location["Maths Building"] = [4, 1]
location["Student Center"] = [6, 8]
location["Store"] = [6, 4]
location["Canteen"] = [6, 1]
location["AI Lab"] = [6, 0]
location["Theater"] = [7, 7]
location["Sports Center"] = [7, 5]
...
We also have the location dictionary for storing the locations of places. The keys of the location dictionary are the places, and the values are the x and y coordinates of those places.
In DFS, preference was given to the child nodes while exploring the search tree; in BFS, preference was given to the sibling nodes. In heuristic searching, preference is given to nodes with lower heuristic values.
Now, let's look at the term heuristic. A heuristic is a property of the class node. It is a guess, or estimate, of which node will lead to the goal state faster than others. This is a strategy used to reduce the nodes explored and reach the goal state quicker:
Figure 2
For example, suppose that we're at the red node in the preceding diagram, and it has two child nodes—the yellow node and the green node. The green node seems to be much closer to the goal state, so we would select that node for further exploration.
We'll see the following two heuristic search algorithms as we proceed with this chapter:
- The greedy BFS algorithm
- The A* Search algorithm
![]()
A priority queue is a queue in which each element has a priority. For example, when passengers are waiting in a queue to board a flight, families with young children and business class passengers usually take priority and board first; then, the economy class passengers board. Let's look at another example. Suppose that three people are waiting in a queue to be attended to at a service counter, and an old man steps in at the end of the queue. Considering his age, the people in the queue might give him a higher priority and allow him to go first. Through these two examples, we can see that the elements in a priority queue have priorities, and they are processed in order of those priorities.
Just like in queuing, we have operations to insert elements into a priority queue. The insert operation inserts an element with a specific priority. Consider the following diagram, illustrating the insert operation:
Figure 3
In the preceding diagram, element A is inserted with priority 5; since the priority queue is empty, the element is kept at the front. In Python, elements with low priorities are arranged toward the front of the queue, and elements with high priority values are arranged toward the end of the priority queue. This means that elements with low priority values are processed fi...
