Can you Modify this code To do a IDA* Search The output should be the same as this code. import psutil import time from collections import deque from heapq import heappush, heappop from typing import List, Tuple classSearch: defgoal_test(self, cur_tiles): return cur_tiles == ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '0'] defmanhattan_distance(self, tiles: List[str]) -> int: # Calculate the manhattan distance heuristic for a given state h = 0 i = 0 while i < 16: if tiles[i] != '0': x, y = divmod(i, 4) j = int(tiles[i])-1 u, v = divmod(j, 4) h += abs(x - u) + abs(y - v) i += 1 return h defmisplaced_tiles(self, tiles: List[str]) -> int: # Calculate the misplaced tiles heuristic for a given state h = 0 i = 0 while i < 16: if tiles[i] != '0' and tiles[i] != str(i+1): h += 1 i += 1 return h defget_successors(self, tiles: List[str]) -> List[Tuple[List[str], str]]: # Generate all possible successor states and corresponding actions successors = [] i = tiles.index('0') while i % 4 > 0: # Move the blank tile left new_tiles = tiles[:] new_tiles[i], new_tiles[i-1] = new_tiles[i-1], new_tiles[i] successors.append((new_tiles, 'L')) i -= 1 i = tiles.index('0') while i % 4 < 3: # Move the blank tile right new_tiles = tiles[:] new_tiles[i], new_tiles[i+1] = new_tiles[i+1], new_tiles[i] successors.append((new_tiles, 'R')) i += 1 i = tiles.index('0') while i // 4 > 0: # Move the blank tile up new_tiles = tiles[:] new_tiles[i], new_tiles[i-4] = new_tiles[i-4], new_tiles[i] successors.append((new_tiles, 'U')) i -= 4 i = tiles.index('0') while i // 4 < 3: # Move the blank tile down new_tiles = tiles[:] new_tiles[i], new_tiles[i+4] = new_tiles[i+4], new_tiles[i] successors.append((new_tiles, 'D')) i += 4 return successors defrun_iddfs_manhattan_distance(self, initial_state: List[str], max_depth: int) -> Tuple[List[str], int]: # Run IDDFS algorithm with manhattan distance heuristic function for depth in range(max_depth + 1): result = self.dls_manhattan_distance(initial_state, depth) if result is not None: return result defdls_manhattan_distance(self, state: List[str], depth: int): # Recursive function for depth-limited search with manhattan distance heuristic if depth == 0 and self.goal_test(state): return ([], 0) elif depth > 0: for successor, action in self.get_successors(state): h = self.manhattan_distance(successor) result = self.dls_manhattan_distance(successor, depth - 1) if result is not None: path, num_expanded = result return ([action] + path, num_expanded + 1) returnNone defrun_iddfs_misplaced_tiles(self, initial_state: List[str], max_depth: int) -> Tuple[List[str], int]: # Run IDDFS algorithm with misplaced tiles heuristic function for depth in range(max_depth + 1): result = self.dls_misplaced_tiles(initial_state, depth) if result is not None: return result defdls_misplaced_tiles(self, state: List[str], depth: int): # Recursive function for depth-limited search with misplaced tiles heuristic if depth == 0 and self.goal_test(state): return ([], 0) elif depth > 0: for successor, action in self.get_successors(state): h = self.misplaced_tiles(successor) result = self.dls_misplaced_tiles(successor, depth - 1) if result is not None: path, num_expanded = result return ([action] + path, num_expanded + 1) returnNone defsolve(self, initial_state, heuristic="manhattan", max_depth=50): initial_list = initial_state.split(" ") start_time = time.perf_counter() if heuristic == "manhattan": path, num_expanded = self.run_iddfs_manhattan_distance(initial_list, max_depth) elif heuristic == "misplaced tiles": path, num_expanded = self.run_iddfs_misplaced_tiles(initial_list, max_depth) end_time = time.perf_counter() elapsed_time = end_time - start_time memory_usage = psutil.Process().memory_info().rss print("Moves: " + " ".join(path)) print("Number of expanded Nodes: " + str(num_expanded)) print("Time Taken: " + str(elapsed_time)) print("Max Memory (Bytes): " + str(memory_usage)) return "".join(path) # USE THE README CODE TO RUN THE PROGRAM. # if __name__ == '__main__': # agent = Search() # agent.solve("1 0 2 4 5 7 3 8 9 6 11 12 13 10 14 15")

Can you Modify this code To do a IDA* Search The output should be the same as this code. import psutil import time from collections import deque from heapq import heappush, heappop from typing import List, Tuple classSearch: defgoal_test(self, cur_tiles): return cur_tiles == ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '0'] defmanhattan_distance(self, tiles: List[str]) -> int: # Calculate the manhattan distance heuristic for a given state h = 0 i = 0 while i < 16: if tiles[i] != '0': x, y = divmod(i, 4) j = int(tiles[i])-1 u, v = divmod(j, 4) h += abs(x - u) + abs(y - v) i += 1 return h defmisplaced_tiles(self, tiles: List[str]) -> int: # Calculate the misplaced tiles heuristic for a given state h = 0 i = 0 while i < 16: if tiles[i] != '0' and tiles[i] != str(i+1): h += 1 i += 1 return h defget_successors(self, tiles: List[str]) -> List[Tuple[List[str], str]]: # Generate all possible successor states and corresponding actions successors = [] i = tiles.index('0') while i % 4 > 0: # Move the blank tile left new_tiles = tiles[:] new_tiles[i], new_tiles[i-1] = new_tiles[i-1], new_tiles[i] successors.append((new_tiles, 'L')) i -= 1 i = tiles.index('0') while i % 4 < 3: # Move the blank tile right new_tiles = tiles[:] new_tiles[i], new_tiles[i+1] = new_tiles[i+1], new_tiles[i] successors.append((new_tiles, 'R')) i += 1 i = tiles.index('0') while i // 4 > 0: # Move the blank tile up new_tiles = tiles[:] new_tiles[i], new_tiles[i-4] = new_tiles[i-4], new_tiles[i] successors.append((new_tiles, 'U')) i -= 4 i = tiles.index('0') while i // 4 < 3: # Move the blank tile down new_tiles = tiles[:] new_tiles[i], new_tiles[i+4] = new_tiles[i+4], new_tiles[i] successors.append((new_tiles, 'D')) i += 4 return successors defrun_iddfs_manhattan_distance(self, initial_state: List[str], max_depth: int) -> Tuple[List[str], int]: # Run IDDFS algorithm with manhattan distance heuristic function for depth in range(max_depth + 1): result = self.dls_manhattan_distance(initial_state, depth) if result is not None: return result defdls_manhattan_distance(self, state: List[str], depth: int): # Recursive function for depth-limited search with manhattan distance heuristic if depth == 0 and self.goal_test(state): return ([], 0) elif depth > 0: for successor, action in self.get_successors(state): h = self.manhattan_distance(successor) result = self.dls_manhattan_distance(successor, depth - 1) if result is not None: path, num_expanded = result return ([action] + path, num_expanded + 1) returnNone defrun_iddfs_misplaced_tiles(self, initial_state: List[str], max_depth: int) -> Tuple[List[str], int]: # Run IDDFS algorithm with misplaced tiles heuristic function for depth in range(max_depth + 1): result = self.dls_misplaced_tiles(initial_state, depth) if result is not None: return result defdls_misplaced_tiles(self, state: List[str], depth: int): # Recursive function for depth-limited search with misplaced tiles heuristic if depth == 0 and self.goal_test(state): return ([], 0) elif depth > 0: for successor, action in self.get_successors(state): h = self.misplaced_tiles(successor) result = self.dls_misplaced_tiles(successor, depth - 1) if result is not None: path, num_expanded = result return ([action] + path, num_expanded + 1) returnNone defsolve(self, initial_state, heuristic="manhattan", max_depth=50): initial_list = initial_state.split(" ") start_time = time.perf_counter() if heuristic == "manhattan": path, num_expanded = self.run_iddfs_manhattan_distance(initial_list, max_depth) elif heuristic == "misplaced tiles": path, num_expanded = self.run_iddfs_misplaced_tiles(initial_list, max_depth) end_time = time.perf_counter() elapsed_time = end_time - start_time memory_usage = psutil.Process().memory_info().rss print("Moves: " + " ".join(path)) print("Number of expanded Nodes: " + str(num_expanded)) print("Time Taken: " + str(elapsed_time)) print("Max Memory (Bytes): " + str(memory_usage)) return "".join(path) # USE THE README CODE TO RUN THE PROGRAM. # if name == 'main': # agent = Search() # agent.solve("1 0 2 4 5 7 3 8 9 6 11 12 13 10 14 15")

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Can you Modify this code To do a IDA* Search The output should be the same as this code.

import psutil

import time

from collections import deque

from heapq import heappush, heappop

from typing import List, Tuple

classSearch:

defgoal_test(self, cur_tiles):

return cur_tiles == ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '0']

defmanhattan_distance(self, tiles: List[str]) -> int:

# Calculate the manhattan distance heuristic for a given state

h = 0

i = 0

while i < 16:

if tiles[i] != '0':

x, y = divmod(i, 4)

j = int(tiles[i])-1

u, v = divmod(j, 4)

h += abs(x - u) + abs(y - v)

i += 1

return h

defmisplaced_tiles(self, tiles: List[str]) -> int:

# Calculate the misplaced tiles heuristic for a given state

h = 0

i = 0

while i < 16:

if tiles[i] != '0' and tiles[i] != str(i+1):

h += 1

i += 1

return h

defget_successors(self, tiles: List[str]) -> List[Tuple[List[str], str]]:

# Generate all possible successor states and corresponding actions

successors = []

i = tiles.index('0')

while i % 4 > 0:

# Move the blank tile left

new_tiles = tiles[:]

new_tiles[i], new_tiles[i-1] = new_tiles[i-1], new_tiles[i]

successors.append((new_tiles, 'L'))

i -= 1

i = tiles.index('0')

while i % 4 < 3:

# Move the blank tile right

new_tiles = tiles[:]

new_tiles[i], new_tiles[i+1] = new_tiles[i+1], new_tiles[i]

successors.append((new_tiles, 'R'))

i += 1

i = tiles.index('0')

while i // 4 > 0:

# Move the blank tile up

new_tiles = tiles[:]

new_tiles[i], new_tiles[i-4] = new_tiles[i-4], new_tiles[i]

successors.append((new_tiles, 'U'))

i -= 4

i = tiles.index('0')

while i // 4 < 3:

# Move the blank tile down

new_tiles = tiles[:]

new_tiles[i], new_tiles[i+4] = new_tiles[i+4], new_tiles[i]

successors.append((new_tiles, 'D'))

i += 4

return successors

defrun_iddfs_manhattan_distance(self, initial_state: List[str], max_depth: int) -> Tuple[List[str], int]:

# Run IDDFS algorithm with manhattan distance heuristic function

for depth in range(max_depth + 1):

result = self.dls_manhattan_distance(initial_state, depth)

if result is not None:

return result

defdls_manhattan_distance(self, state: List[str], depth: int):

# Recursive function for depth-limited search with manhattan distance heuristic

if depth == 0 and self.goal_test(state):

return ([], 0)

elif depth > 0:

for successor, action in self.get_successors(state):

h = self.manhattan_distance(successor)

result = self.dls_manhattan_distance(successor, depth - 1)

if result is not None:

path, num_expanded = result

return ([action] + path, num_expanded + 1)

returnNone

defrun_iddfs_misplaced_tiles(self, initial_state: List[str], max_depth: int) -> Tuple[List[str], int]:

# Run IDDFS algorithm with misplaced tiles heuristic function

for depth in range(max_depth + 1):

result = self.dls_misplaced_tiles(initial_state, depth)

if result is not None:

return result

defdls_misplaced_tiles(self, state: List[str], depth: int):

# Recursive function for depth-limited search with misplaced tiles heuristic

if depth == 0 and self.goal_test(state):

return ([], 0)

elif depth > 0:

for successor, action in self.get_successors(state):

h = self.misplaced_tiles(successor)

result = self.dls_misplaced_tiles(successor, depth - 1)

if result is not None:

path, num_expanded = result

return ([action] + path, num_expanded + 1)

returnNone

defsolve(self, initial_state, heuristic="manhattan", max_depth=50):

initial_list = initial_state.split(" ")

start_time = time.perf_counter()

if heuristic == "manhattan":

path, num_expanded = self.run_iddfs_manhattan_distance(initial_list, max_depth)

elif heuristic == "misplaced tiles":

path, num_expanded = self.run_iddfs_misplaced_tiles(initial_list, max_depth)

end_time = time.perf_counter()

elapsed_time = end_time - start_time

memory_usage = psutil.Process().memory_info().rss

print("Moves: " + " ".join(path))

print("Number of expanded Nodes: " + str(num_expanded))

print("Time Taken: " + str(elapsed_time))

print("Max Memory (Bytes): " + str(memory_usage))

return "".join(path)

# USE THE README CODE TO RUN THE PROGRAM.

# if __name__ == '__main__':

# agent = Search()

# agent.solve("1 0 2 4 5 7 3 8 9 6 11 12 13 10 14 15")

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 4 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.