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() explored.add(node.state) 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) # goal state not found 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:
- Pathfinding: Best First Search is commonly used to find the shortest path between two points in a graph.
- Game AI: Best First Search can be used to create intelligent game AI that can make decisions based on a heuristic function.
- Robotics: Best First Search can be used in robotics to find the best path for a robot to take to reach a destination.
- 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.