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()

Pseudocode: function reconstruct_path(came From, current) total_path = {current} while current in cameFrom.Keys: current = came From [current] total_path.prepend(current) return total_path // A* finds a path from start to goal. // h is the heuristic function. h (n) estimates the cost to reach goal from node n. function A_Star(start, goal, h) // The set of discovered nodes that may need to be (re-) expanded. // Initially, only the start node is known. // This is usually implemented as a min-heap or priority queue rather than a hash-set. openSet {start} // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start // to n currently known. cameFrom= an empty map // For node n, gScore[n] is the cost of the cheapest path from start to n currently known. gScore = map with default value of Infinity gScore[start] := 0 // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to // how cheap a path could be from start to finish if it goes through n. fScore : map with default value of Infinity fScore[start] := h(start) while openSet is not empty // This operation can occur in O(Log (N)) time if openSet is a min-heap or a priority queue current = the node in openSet having the lowest fScore[] value if current = goal return reconstruct_path(came From, current) openSet. Remove (current) for each neighbor of current // d(current, neighbor) is the weight of the edge from current to neighbor // tentative_gScore is the distance from start to the neighbor through current tentative_gScore := gScore[current] + d(current, neighbor) if tentative_gScore < gScore[neighbor] // This path to neighbor is better than any previous one. Record it! came From [neighbor] = current gScore [neighbor] = tentative_gScore fScore [neighbor] = tentative_gScore + h(neighbor) if neighbor not in openSet openSet.add(neighbor) // Open set is empty but goal was never reached return failure