Python Implementations of Search Algorithms
■ Program 1: Hill Climbing Algorithm (Local Search)
import random
# Generate a random initial solution
def randomwalk(dp):
cities = list(range(len(dp)))
solution = []
for i in range(len(dp)):
randomcity = cities[[Link](0, len(cities) - 1)]
[Link](randomcity)
[Link](randomcity)
return solution
# Calculate total distance of a solution/path
def distance(dp, solution):
total = 0
for i in range(len(solution) - 1):
total += dp[solution[i]][solution[i + 1]]
return total
# Generate neighboring solutions by swapping two cities
def getNeighbours(solution):
neighbours = []
for i in range(len(solution)):
for j in range(i + 1, len(solution)):
neighbour = [Link]()
neighbour[i], neighbour[j] = neighbour[j], neighbour[i]
[Link](neighbour)
return neighbours
# Find the best neighbour with the least cost
def getBestNeighbour(dp, neighbours):
bestNeighbour = neighbours[0]
bestNeighbourDistance = distance(dp, bestNeighbour)
for neighbour in neighbours:
currentDistance = distance(dp, neighbour)
if currentDistance < bestNeighbourDistance:
bestNeighbour = neighbour
bestNeighbourDistance = currentDistance
return bestNeighbour, bestNeighbourDistance
# Hill Climbing Algorithm
def hillclimbing(dp):
current_solution = randomwalk(dp)
current_distance = distance(dp, current_solution)
while True:
neighbours = getNeighbours(current_solution)
bestNeighbour, bestNeighbourDistance = getBestNeighbour(dp, neighbours)
if bestNeighbourDistance < current_distance:
current_solution = bestNeighbour
current_distance = bestNeighbourDistance
else:
break # No better neighbour found
return current_solution, current_distance
# Main program
def main():
dp = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
best_path, best_cost = hillclimbing(dp)
print("Best path found:", best_path)
print("Cost of path:", best_cost)
if __name__ == "__main__":
main()
■ Program 2: A* Search Algorithm (Informed Search)
# Heuristic function (Estimated distance from node to goal)
def heuristic(n):
H_dist = {
'a': 11,
'b': 6,
'c': 99,
'd': 1,
'e': 7,
'f': 1,
'g': 0
}
return H_dist.get(n, float('inf'))
# Graph structure: node -> list of (neighbor, weight)
Graph_nodes = {
'a': [('b', 2), ('e', 3)],
'b': [('c', 1), ('g', 9)],
'c': [],
'd': [('f', 2), ('g', 2)],
'e': [('d', 6)],
'f': [],
'g': []
}
def astarAlgo(start_node, stop_node):
open_set = set([start_node])
closed_set = set([])
g = {} # Actual cost from start node
parents = {} # Track path
g[start_node] = 0
parents[start_node] = None
while len(open_set) > 0:
n = None
# Find node with lowest f(n) = g(n) + h(n)
for v in open_set:
if n is None or g[v] + heuristic(v) < g[n] + heuristic(n):
n = v
if n is None:
print('Path does not exist!')
return None
if n == stop_node:
path = []
while n is not None:
[Link](n)
n = parents[n]
[Link]()
print('Path found:', path)
return path
for (m, weight) in Graph_nodes.get(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
# Run the A* search
astarAlgo('a', 'g')
