a program which performs a-star search to find the solution to any... a program which performs a-star
Question:
a program which performs a-star search to find the solution to any...
a program which performs a-star search to find the solution to any given board position for 15 puzzle using two types of heuristics:
1. Number of misplaced tiles 2. Manhattan Distance
Input
The input should be given in form of sequence of numbered tiles for initial board configuration, '0' indicating the empty space (see example below)
Output
1. Moves
2. Number of Nodes expanded 3. Time Taken
4. Memory Used
Starter code:
# For assignment 5, please specify manhattan distance or misplaced tiles as the heuristic function
class Search:
def goal_test(self, cur_tiles):
return cur_tiles == ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '0']
def solve(self, initial_state, heuristic = "manhattan"): # Format : "1 0 2 4 5 7 3 8 9 6 11 12 13 10 14 15"
initial_list = initial_state.split(" ")
"""
Please use this as a reference to run with gradescope autograder.
if heuristic == "manhattan":
solution_moves = run_bfs_manhattan_distance(initial_list)
if heuristic == "misplaced tiles":
solution_moves = run_bfs_manhattan_distance(initial_list)
"""
print("Moves: " + " ".join(path))
print("Number of expanded Nodes: " + str(""))
print("Time Taken: " + str(""))
print("Max Memory (Bytes): " + str(""))
return "".join(path) # Get the list of moves to solve the puzzle. Format is "RDLDDRR"
if __name__ == '__main__':
agent = Search()
Essentials Of Statistics For Business And Economics
ISBN: 9781305081598
7th Edition
Authors: David Anderson, Thomas Williams, Dennis Sweeney, Jeffrey Cam