Hands-On Artificial Intelligence for Search

Building intelligent applications and perform enterprise searches

Devangini Patel

• Publisher: Packt Publishing
• Year: 2018
• ISBN:
  9781789612479
• Edition: 1
• Topic: Ciencia de la computación
• Subtopic: Ciencias computacionales general

Make your searches more responsive and smarter by applying Artificial Intelligence to it

Key Features

• Enter the world of Artificial Intelligence with solid concepts and real-world use cases
• Make your applications intelligent using AI in your day-to-day apps and become a smart developer
• Design and implement artificial intelligence in searches

Book Description

With the emergence of big data and modern technologies, AI has acquired a lot of relevance in many domains. The increase in demand for automation has generated many applications for AI in fields such as robotics, predictive analytics, finance, and more.

In this book, you will understand what artificial intelligence is. It explains in detail basic search methods: Depth-First Search (DFS), Breadth-First Search (BFS), and A* Search, which can be used to make intelligent decisions when the initial state, end state, and possible actions are known. Random solutions or greedy solutions can be found for such problems. But these are not optimal in either space or time and efficient approaches in time and space will be explored. We will also understand how to formulate a problem, which involves looking at it and identifying its initial state, goal state, and the actions that are possible in each state. We also need to understand the data structures involved while implementing these search algorithms as they form the basis of search exploration. Finally, we will look into what a heuristic is as this decides the quality of one sub-solution over another and helps you decide which step to take.

What you will learn

• Understand the instances where searches can be used
• Understand the algorithms that can be used to make decisions more intelligent
• Formulate a problem by specifying its initial state, goal state, and actions
• Translate the concepts of the selected search algorithm into code
• Compare how basic search algorithms will perform for the application
• Implement algorithmic programming using code examples

Who this book is for

This book is for developers who are keen to get started with Artificial Intelligence and develop practical AI-based applications. Those developers who want to upgrade their normal applications to smart and intelligent versions will find this book useful. A basic knowledge and understanding of Python are assumed.

Understanding the Heuristic Search Algorithm

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 this chapter, we will cover the following topics:

• Revisiting the navigation application
• The priority queue data structure
• Visualizing search trees
• Greedy Best-First Search (BFS)
• The A* Search
• Features of a good heuristic

Revisiting the navigation application

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

The priority queue data structure

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...