Write 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
Use python
This is also with the question
# 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.
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()
![Write 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
Pseudocode from the textbook:
Figure 3.7
function BEST-FIRST-SEARCH(problem. f) returns a solution node or failure
node+NODE(STATE=problem.INITIAL)
frontiera priority queue ordered by f, with node as an element
reached a lookup table, with one entry with key problem. INITIAL and value node
while not IS-EMPTY(frontier) do
node POP(frontier)
if problem.IS-GOAL(node.STATE) then return node
for each child in EXPAND(problem, node) do
schild.STATE
if s is not in reached or child.PATH-COST < reached[s].PATH-COST then
reached[s] child
add child to frontier
return failure
function EXPAND(problem, node) yields nodes
s-node.STATE
for each action in problem.ACTIONS (s) do
sproblem.RESULT(s, action)
cost-node.PATH-COST + problem.ACTION-COST(s, action, s')
yield NODE(STATE=s', PARENT=node, ACTION=action, PATH-COST=cost)
The best-first search algorithm, and the function for expanding a node. The data structures used here are
described in Section 3.3.2, See Appendix B for yield.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F672bf286-8abe-4b07-9ca1-0d5b2612956c%2F35c6ac7d-341d-42e4-a0da-c7f947995ea6%2Framigwq_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 4 images
