# Best First Search Program in Python

Best First Search is an algorithm that is used to search the best path between two points. The algorithm uses heuristics to determine the most promising node to expand next, which makes it an efficient algorithm for finding solutions in a search space. In this article, we will discuss the implementation of Best First Search in Python, and we will also discuss some of the applications of this algorithm.

## What is Best First Search?

Best First Search is a type of graph traversal algorithm that uses a heuristic function to determine the next node to be explored. The algorithm works by exploring the node with the lowest heuristic value first. The heuristic function estimates the distance between the current node and the goal node. The goal of the algorithm is to find the path with the lowest cost to the goal node.

## Implementation of Best First Search in Python

The implementation of Best First Search in Python is simple. We will use the A* algorithm, which is a type of Best First Search algorithm. The A* algorithm uses both the cost of the path so far and the heuristic estimate of the remaining cost to the goal to determine the next node to be expanded.

We will implement the algorithm using the Python programming language. Here is the implementation:

Example:

```from queue import PriorityQueue
class Node:
def __init__(self, state, parent=None):
self.state = tuple(state)
self.parent = parent
self.cost = 0
def __lt__(self, other):
returnself.cost<other.cost
def heuristic(state):
# Manhattan distance heuristic
goal_state = (1, 2, 3, 4, 5, 6, 7, 8, 0)
distance = 0
fori in range(9):
if state[i] != 0:
distance += abs(i // 3 - goal_state.index(state[i]) // 3) + abs(i % 3 - goal_state.index(state[i]) % 3)
return distance
defget_successors(state):
successors = []
blank_index = state.index(0)
ifblank_index != 0 and blank_index != 3 and blank_index != 6:
# move left
new_state = list(state)
new_state[blank_index], new_state[blank_index - 1] = new_state[blank_index - 1], new_state[blank_index]
successors.append(tuple(new_state))
ifblank_index != 2 and blank_index != 5 and blank_index != 8:
# move right
new_state = list(state)
new_state[blank_index], new_state[blank_index + 1] = new_state[blank_index + 1], new_state[blank_index]
successors.append(tuple(new_state))
ifblank_index> 2:
# move up
new_state = list(state)
new_state[blank_index], new_state[blank_index - 3] = new_state[blank_index - 3], new_state[blank_index]
successors.append(tuple(new_state))
ifblank_index< 6:
# move down
new_state = list(state)
new_state[blank_index], new_state[blank_index + 3] = new_state[blank_index + 3], new_state[blank_index]
successors.append(tuple(new_state))
return successors
defbest_first_search(start_state):
number_of_inversions = sum(1 for i in range(8) for j in range(i+1, 9) if start_state[i] >start_state[j] and start_state[i] != 0 and start_state[j] != 0)
ifnumber_of_inversions % 2 != 0:
return None
start_node = Node(start_state)
ifstart_node.state == (1, 2, 3, 4, 5, 6, 7, 8, 0):
return [start_node.state]
frontier = PriorityQueue()
frontier.put(start_node)
explored = set()
while not frontier.empty():
node = frontier.get()
forsuccessor_state in get_successors(node.state):
ifsuccessor_state not in explored:
successor_node = Node(successor_state, parent=node)
successor_node.cost = heuristic(successor_state)
ifsuccessor_state == (1, 2, 3, 4, 5, 6, 7, 8, 0):
# goal state found
path = [successor_state]
whilesuccessor_node.parent is not None:
successor_node = successor_node.parent
path.append(successor_node.state)
return path[::-1]
frontier.put(successor_node)
return None
# example usage
start_state = (1,2,3,4,5,6,7,0,8)
path = best_first_search(start_state)
print(path)```

Output:

`[(1, 2, 3, 4, 5, 6, 7, 0, 8), (1, 2, 3, 4, 5, 6, 7, 8, 0)]`

Let's break down the implementation into smaller parts and understand what each part does:

### 1. Node Class

The Node class represents a node in the search space. Each node has a state, a parent, a cost, and a heuristic. The state represents the state of the node, the parent represents the parent node, the cost represents the cost of the path so far, and the heuristic represents the heuristic estimate of the remaining cost to the goal.

### 2. Best First Search Function

The best_first_search function takes three arguments: start, goal, and heuristic. The start argument represents the starting state, the goal argument represents the goal state, and the heuristic argument represents the heuristic function. The function returns the path from the start state to the goal state.

### 3. Visited List

The visited list keeps track of the states that have already been visited.

### 4. Queue

The queue is a list that contains nodes that are yet to be explored. The nodes in the queue are sorted based on their heuristic value, and the node with the lowest heuristic value is expanded next.

### 5. While Loop

The while loop runs as long as there are nodes in the queue. The nodes in the queue are sorted based on their heuristic value, and the node with the lowest heuristic value is expanded next.

### 6. Node Selection

The node with the lowest heuristic value is selected for expansion. This is done by sorting the nodes in the queue based on their heuristic value, and then selecting the first node in the queue.

### 7. Goal State Check

The selected node's state is checked to see if it is the goal state. If it is the goal state, the path is traced back from the goal node to the start node, and the path is returned in reverse order.

### 8. Adding Node to Visited List

If the selected node is not the goal node, its state is added to the visited list.

### 9. Generating Children

The children of the selected node are generated by swapping the values of two elements in the state of the node. Each child node is created by creating a new state and adding it to a new node object.

### 10. Child Node Cost and Heuristic Calculation

The cost of the child node is calculated by adding 1 to the cost of the parent node. The heuristic of the child node is calculated by calling the heuristic function with the child node's state and the goal state.

### 11. Adding Child Node to Queue

If the state of the child node has not been visited before, the child node is added to the queue.

### 12. Return Value

If a path from the start state to the goal state is not found, the function returns None.

## Applications of Best First Search

Best First Search has many applications. Some of them are as follows:

1. Pathfinding: Best First Search is commonly used to find the shortest path between two points in a graph.
2. Game AI: Best First Search can be used to create intelligent game AI that can make decisions based on a heuristic function.
3. Robotics: Best First Search can be used in robotics to find the best path for a robot to take to reach a destination.
4. Logistics: Best First Search can be used in logistics to optimize delivery routes and reduce transportation costs.

### Conclusion

In this article, we have discussed the implementation of Best First Search in Python. We have also discussed the applications of Best First Search in various fields. Best First Search is a powerful algorithm that can be used to find the shortest path between two points. It is a widely used algorithm and is often used in game AI, robotics, logistics, and many other fields. With its efficient search strategy, Best First Search can find solutions to problems quickly and effectively.