Ex No Implementation of Informed Search Algorithms (A*)
CLICK HERE PROGRAM LINK
-------------------------------------------------
A* - Informed Search (Heuristic Search)
Informed search algorithms use additional knowledge (heuristics) to guide the search more intelligently, helping to focus the exploration of the search space towards more promising paths. This approach often leads to faster solutions because it reduces the number of paths explored.
Characteristics:
- Domain-specific knowledge: These algorithms use heuristics to estimate the cost or value of reaching the goal.
- Smarter exploration: They prioritize paths that seem more likely to lead to a solution.
Types of Informed Search:
- Greedy Best-First Search: Chooses the node that appears to be closest to the goal based on a heuristic.
- A Search*: Combines the cost to reach a node and the estimated cost to reach the goal (using both path cost and heuristic), ensuring an optimal solution if the heuristic is admissible (doesn’t overestimate costs).
Pros:
- Efficiency: Heuristic guidance helps cut down on unnecessary exploration.
- Faster solutions in many cases.
- Can be optimal (e.g., A* Search with admissible heuristics).
-------------------------------------------------
Aim
To implement the informed search algorithm and execute the code for A* search algoritm.
Algorithm
1.Define the problem determine the problem you want to solve including the start and goal nodes.
2.Add the start node to the open list and set its G score.
3.Calculate the F score for each node on the open list by adding the G score and a heuristic estimate of the
distance to the goal node.The heuristic estimate can be calculated using a variety of method.
4.Choose the node with the lowest F score from the open list and move it to the closed list.
5.Generate the successors of the node selected in step4.
6.If the goal node is on the closed list,the search is complete.Otherwise,repeat steps 4,5 untill the goal
node is found.
7.Set a bound for the minimum acceptable F score for the goal node,this allows the algorithm to terminate
early if it is a solution that is close enough to optimal.
8.If the algorithm terminate early,backtrack to the node with the lowest F score that was removed from the
open list and generate its successors.
9.When backtracking nodes that were previously removed from the open list may need to be reinserted if
their now F score is lower than the bound.
PROGRAM:
def astaralgo(start_node, stop_node):
open_set = set([start_node]) # Open set to keep track of nodes to explore
closed_set = set() # Closed set to keep track of already explored nodes
g = {} # g values (costs from start node)
parents = {} # To track the path
g[start_node] = 0 # Starting node has a g value of 0
parents[start_node] = start_node # The parent of the start node is itself
while len(open_set) > 0:
n = None
# Find the node in the open set with the lowest f = g + heuristic
for v in open_set:
if n is None or g[v] + heuristic(v) < g[n] + heuristic(n):
n = v
# If the destination is reached
if n == stop_node:
path = []
while parents[n] != n:
path.append(n)
n = parents[n]
path.append(start_node)
path.reverse()
print("Path found: {}".format(path))
return path
# If the node is not valid or no more valid nodes are left
if Graph_nodes.get(n) is None:
pass
else:
# Explore neighbors
for m, weight in get_neighbors(n):
if m not in open_set and m not in closed_set:
open_set.add(m)
parents[m] = n
g[m] = g[n] + weight
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
open_set.remove(n)
closed_set.add(n)
print("Path does not exist!")
return None
def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return [] # Return an empty list if there are no neighbors
def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 99,
'D': 1,
'E': 7,
'G': 0,
}
return H_dist.get(n, 0) # Default to 0 if heuristic is not defined for a node
Graph_nodes = {
'A': [('B', 2), ('E', 3)],
'B': [('C', 1), ('G', 9)],
'C': [],
'E': [('D', 6)],
'D': [('G', 1)],
}
# Running the A* algorithm from node 'A' to node 'G'
astaralgo('A', 'G')
Path found: ['A', 'E', 'D', 'G']
['A', 'E', 'D', 'G']
No comments:
Post a Comment