import random
import math
# Helper function to find the position of the blank tile (0)
def find_blank(state):
for i in range(3):
for j in range(3):
if state[i][j] == 0:
return i, j
# Function to generate neighbors by moving the blank tile
def get_neighbors(state):
neighbors = []
x, y = find_blank(state)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Up, Down, Left, Right
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < 3 and 0 <= ny < 3: # Check bounds
new_state = [row[:] for row in state]
new_state[x][y], new_state[nx][ny] = new_state[nx][ny], new_state[x][y]
neighbors.append(new_state)
return neighbors
# Function to calculate heuristics
def calculate_heuristic(state, goal, h_type):
if h_type == "h1": # Number of misplaced tiles
return sum(1 for i in range(3) for j in range(3) if state[i][j] != 0 and state[i][j] != goal[i][j])
elif h_type == "h2": # Total Manhattan distance
distance = 0
for i in range(3):
for j in range(3):
if state[i][j] != 0:
goal_x, goal_y = divmod(state[i][j] - 1, 3)
distance += abs(i - goal_x) + abs(j - goal_y)
return distance
return float('inf')
# Simulated Annealing Algorithm
def simulated_annealing(initial, goal, heuristic="h1", initial_temp=1000, cooling_rate=0.95, max_steps=1000):
current = initial
current_cost = calculate_heuristic(current, goal, heuristic)
temperature = initial_temp
for step in range(max_steps):
if current == goal:
return current, step # Solution found
neighbors = get_neighbors(current)
next_state = random.choice(neighbors)
next_cost = calculate_heuristic(next_state, goal, heuristic)
delta_e = next_cost - current_cost
# Accept the new state with a probability based on temperature
if delta_e < 0 or random.uniform(0, 1) < math.exp(-delta_e / temperature):
current = next_state
current_cost = next_cost
# Cool down the temperature
temperature *= cooling_rate
if temperature <= 0.001:
break # Stop if temperature is too low
return None, step # No solution found
# Example usage
if __name__ == "__main__":
initial_state = [
[1, 2, 3],
[4, 0, 5],
[7, 8, 6]
]
goal_state = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 0]
]
heuristic_type = input("Choose heuristic (h1 or h2): ")
solution, steps = simulated_annealing(initial_state, goal_state, heuristic_type)
if solution:
print(f"Solution found in {steps} steps:")
for row in solution:
print(row)
else:
print("No solution found.")
Comments
Post a Comment