Answered: Write a program which performs…

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

Question

Can you modify this to do IDA* method

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)

if __name__ == '__main__':

agent = Search()

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

Write a program which performs Iterative Deepening a-star (IDA*) 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
https://en.wikipedia.org/wiki/Iterative deepening A*
Described in section 3.5.5 of the textbook.
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

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.

Similar questions

Recommended textbooks for you

Database System Concepts

Computer Science

ISBN:

9780078022159

Author:

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

Publisher:

McGraw-Hill Education

Starting Out with Python (4th Edition)

Computer Science

ISBN:

9780134444321

Author:

Tony Gaddis

Publisher:

PEARSON

Digital Fundamentals (11th Edition)

Computer Science

ISBN:

9780132737968

Author:

Thomas L. Floyd

Publisher:

PEARSON

Database System Concepts

Computer Science

ISBN:

9780078022159

Author:

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

Publisher:

McGraw-Hill Education

Starting Out with Python (4th Edition)

Computer Science

ISBN:

9780134444321

Author:

Tony Gaddis

Publisher:

PEARSON

Digital Fundamentals (11th Edition)

Computer Science

ISBN:

9780132737968

Author:

Thomas L. Floyd

Publisher:

PEARSON

C How to Program (8th Edition)

Computer Science

ISBN:

9780133976892

Author:

Paul J. Deitel, Harvey Deitel

Publisher:

PEARSON

Database Systems: Design, Implementation, & Manag…

Computer Science

ISBN:

9781337627900

Author:

Carlos Coronel, Steven Morris

Publisher:

Cengage Learning

Programmable Logic Controllers

Computer Science

ISBN:

9780073373843

Author:

Frank D. Petruzella

Publisher:

McGraw-Hill Education

SEE MORE TEXTBOOKS