6/recent/ticker-posts

Best First Search (BFS) Algorithm

Best-First Search (BFS) is an informed graph traversal algorithm that explores a graph by selecting the most promising node based on a heuristic function. It combines the advantages of both breadth-first search (BFS) and depth-first search (DFS) algorithms. BFS uses a priority queue to prioritize nodes according to their heuristic values.

The heuristic function provides an estimate of the cost from the current node to the goal node. The algorithm maintains a priority queue of nodes and, at each step, selects the node with the lowest heuristic value as the next node to explore. This makes Best-First Search more efficient in terms of reaching the goal quickly by prioritizing nodes that are likely closer to the goal.

Best-First Search is commonly used in pathfinding problems, such as finding the shortest path in a graph or solving maze puzzles. However, it does not guarantee finding the optimal solution, as it is a greedy algorithm and may get stuck in local optima.

Complexity Analysis:



1. Time complexity : O(b^d) to O(V + E) 
  • b is the branching factor,
  • Time complexity : O(b^d) to O(V + E) 
  • d is the depth of the optimal solution,
  • V is the number of vertices,
  • E is the number of edges in the graph.


2. Space complexity : O(V) 
  • V is the number of vertices in the graph.

Explanation:

  1. Best-First Search (BFS) is an informed graph traversal algorithm that selects the most promising node based on a heuristic function.
  2. The algorithm maintains a priority queue to prioritize nodes according to their heuristic values. This allows it to focus on the nodes that are likely closer to the goal.
  3. BFS starts with an initial node and enqueues it into the priority queue with its heuristic value.
  4. At each step, the algorithm dequeues the node with the lowest heuristic value from the priority queue and checks if it is the goal node. If it is, the search is complete and the algorithm terminates.
  5. If the dequeued node is not the goal node, it is marked as visited, and its child nodes are generated.
  6. The heuristic values of the child nodes are calculated, and they are enqueued into the priority queue based on their heuristic values.
  7. The algorithm continues this process of dequeuing, marking as visited, generating child nodes, and enqueuing until the goal node is reached or the priority queue becomes empty.
  8. If the priority queue becomes empty and the goal node is not reached, it means that there is no solution.

Best-First Search Algorithm:

Input: Graph, start node, goal node, heuristic function

  1. Initialize an empty priority queue.
  2. Enqueue the start node into the priority queue with its heuristic value.
  3. Initialize an empty set to keep track of visited nodes.
  4. While the priority queue is not empty: a. Dequeue the node with the lowest priority from the priority queue. b. If the dequeued node is the goal node, return true (goal reached). c. Mark the dequeued node as visited. d. Generate the child nodes of the dequeued node. e. For each child node: i. If the child node has not been visited: — Calculate its heuristic value. — Enqueue the child node into the priority queue with its heuristic value.
  5. If the priority queue becomes empty and the goal node has not been reached, return false (no solution found).

Example:

Consider a mathematical graph with nodes A, B, C, D, E, F, and G, along with their corresponding heuristic values:

The goal is to find the shortest path from node ‘A’ to node ‘G’ using Best-First Search.

Step-by-Step Explanation:

Step 1: Start with node A (heuristic value: 10).

Graph:

Step 2: Expand node A and check its neighbors.

Graph:

Step 3: Choose the node with the lowest heuristic value, which is B (heuristic value: 5).

Graph:

Step 4: Expand node B and check its neighbors.

Graph:

Step 5: Choose the node with the lowest heuristic value, which is D (heuristic value: 4).

Graph:

Step 6: Expand node D and check its neighbors. Since D has no neighbors, move to the next step.

Step 7: Choose the node with the lowest heuristic value from the remaining unvisited nodes, which is C (heuristic value: 8).

Graph:

Step 8: Expand node C and check its neighbors.

Step 9: Choose the node with the lowest heuristic value, which is E (heuristic value: 3).

Graph:

Step 10: Expand node E and check its neighbors.

Step 11: Choose the node with the lowest heuristic value, which is G (heuristic value: 6).

Graph:

Step 12: Since the goal node G is reached, the search is complete.

Shortest Path: A -> B -> E -> G

Graph Traversal Order:

This corresponds to the shortest path from ‘A’ to ‘G’: A -> B -> E -> G.

Code:

from queue import PriorityQueue
def best_first_search(graph, start, goal, heuristic):
queue = PriorityQueue()
queue.put((heuristic[start], start)) # Enqueue the start node with its heuristic value
visited = set() # Set to keep track of visited nodes

while not queue.empty():
_, current = queue.get() # Dequeue the node with the lowest priority

if current == goal:
return True # Solution found

visited.add(current) # Mark the current node as visited

for neighbor in graph[current]:
if neighbor not in visited:
priority = heuristic[neighbor] # Calculate the priority (heuristic value)
queue.put((priority, neighbor)) # Enqueue the neighbor with its priority

return False # No solution found
# Example graph represented as an adjacency list
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['G'],
'F': [],
'G': []
}
# Heuristic values for each node
heuristic = {
'A': 10,
'B': 5,
'C': 8,
'D': 4,
'E': 3,
'F': 2,
'G': 6
}
start_node = 'A'
goal_node = 'G'
# Perform Best-First Search
result = best_first_search(graph, start_node, goal_node, heuristic)
# Print the result
if result:
print("Goal reached!")
else:
print("No solution found.")

Output:

Goal reached!

The provided code implements Best-First Search using a priority queue. Ituses a graph represented as an adjacency list and a heuristic dictionary that assigns heuristic values to each node. The best_first_search function performs the search and returns True if the goal node is reached or False if no solution is found. In this example, the goal node G is reached, resulting in the output "Goal reached!"

follow my Instagram account :

Usage and Conclusion

Best-First Search is commonly used in pathfinding problems, where the goal is to find the most promising path based on a heuristic function. It is applicable in various domains such as route planning, puzzle-solving, and optimization.

Although Best-First Search does not guarantee finding the optimal solution, it can be effective when the heuristic provides a good estimation of the remaining cost. It explores the most promising nodes first, reducing the search space and potentially leading to efficient solutions.

In conclusion, Best-First Search is a powerful algorithm that combines aspects of breadth-first and depth-first search, using heuristics to prioritize node exploration. It offers flexibility and efficiency in pathfinding scenarios and is a valuable tool in solving complex problems.

Post a Comment

0 Comments