Description

Lab2 15-Puzzle Problem (IDA*)

17341015 Hongzheng Chen
Contents
1 IDA* Algorithm 2
1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Tasks 3
3 Codes 3
4 Results 6
1 IDA* Algorithm
1.1 Description
Iterative deepening A* (IDA*) was first described by Richard Korf in 1985, which is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph.
It is a variant of iterative deepening depth-first search that borrows the idea to use a heuristic function to evaluate the remaining cost to get to the goal from the A* search algorithm.
Since it is a depth-first search algorithm, its memory usage is lower than in A*, but unlike ordinary iterative deepening search, it concentrates on exploring the most promising nodes and thus does not go to the same depth everywhere in the search tree.
Iterative-deepening-A* works as follows: at each iteration, perform a depth-first search, cutting off a branch when its total cost f(n) = g(n)+h(n) exceeds a given threshold. This threshold starts at the estimate of the cost at the initial state, and increases for each iteration of the algorithm. At each iteration, the threshold used for the next iteration is the minimum cost of all values that exceeded the current threshold.
1.2 Pseudocode

2 Tasks
• Please solve 15-Puzzle problem by using IDA* (Python or C++). You can use one of the two commonly used heuristic functions: h1 = the number of misplaced tiles. h2 = the sum of the distances of the tiles from their goal positions.
• Here are 4 test cases for you to verify your algorithm correctness. You can also play this game (15puzzle.zip) for more information.

• Please send E02 YourNumber.pdf to ai 201901@foxmail.com, you can certainly use E02 15puzzle.tex as the LATEXtemplate.
3 Codes
In this lab, I implement the IDA? algorithm in Python.
import sys
from copy import deepcopy from queue import PriorityQueue MAX_INT = 0x3f3f3f3f
def print_arr(arr):
“””
Print arr (4*4)
“”” if arr == None: print(arr)
else:
for i in range(4):
print(*(arr[i])) print() def get_target_pos(num):
“””
Get target position of num
“””
return ((num-1) // 4, (num-1) % 4) if num != 0 else (3,3)
def heuristics(a):
“””
Heuristic function for IDA*
“””
res = 0 for i in range(4):
for j in range(4):
(ti, tj) = get_target_pos(a[i][j]) res += abs(i – ti) + abs(j – tj)
return res
def find_space(a):
“””
Find the space of the matrix a
“”” for i in range(4):
try:
j = a[i].index(0) return (i,j) except:
pass
def move(a,i,j,d):
“””
An action on matrix ’a’ that moves (i,j) in the direction of ’d’
“”” res = deepcopy(a) # be careful! if d == ’U’:
if i+1 < 4:
res[i][j], res[i+1][j] = res[i+1][j], res[i][j] return res
else: return None
elif d == ’L’:
if j+1 < 4:
res[i][j], res[i][j+1] = res[i][j+1], res[i][j] return res
else: return None
elif d == ’D’: if i-1 >= 0:
res[i][j], res[i-1][j] = res[i-1][j], res[i][j] return res
else: return None
elif d == ’R’:
if j-1 >= 0:
res[i][j], res[i][j-1] = res[i][j-1], res[i][j] return res else:
return None
else: raise RuntimeError
def search(path,cost,bound):
“””
Path: The previous states
Cost: The current cost (f)
Bound: Maximum limitation of IDA*
“”” arr = path[-1] f = cost + heuristics(arr) if f > bound:
return f, False
if arr == [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,0]]: return f, True # h = 0
(si,sj) = find_space(arr)
# find the successors # based on the f+g priority q = PriorityQueue() for d in [’U’,’L’,’D’,’R’]: new_state = move(arr,si,sj,d) # not share if new_state in path: continue
if new_state != None:
priority = cost + 1 + heuristics(new_state) q.put((priority,new_state))
# DFS minF = MAX_INT while not q.empty(): _, state = q.get() path = path + [state] f, found = search(path,cost+1,bound) if found == True: return f, True
else:
minF = min(f,minF)
del path[-1]
return minF, False
def ida_star(src):
“””
Main function of IDA*
“”” bound = heuristics(arr) path = [src] while True:
bound, found = search(path,0,bound) if found == True: break
if bound == MAX_INT: print(“NOT FOUND!”) return
print(bound)
# Read in data arr = [] for i in range(4): arr.append(list(map(int,input().split())))
# Initialization ida_star(arr)
4 Results