Pe baza problemei puzzle-ului 8, construiți o reprezentare model a problemei puzzle-ului 15 și creați două funcții euristice pentru a rezolva problema prin aplicarea strategiei de căutare A*.
Să se rezolve in Python.
More Questions From This User See All
Răspuns:
from search import *
class NPuzzle(Problem):
def __init__(self, initial, goal, n):
""" Define goal state and initialize a problem """
self.goal = goal
self.n = n
Problem.__init__(self, initial, goal)
def find_blank_square(self, state):
"""Return the index of the blank square in a given state"""
return state.index(0)
def actions(self, state):
""" Return the actions that can be executed in the given state.
The result would be a list, since there are only four possible actions
in any given state of the environment """
possible_actions = ['UP', 'DOWN', 'LEFT', 'RIGHT']
index_blank_square = self.find_blank_square(state)
nr = int(math.sqrt(self.n + 1))
if index_blank_square % nr == 0:
possible_actions.remove('LEFT')
if index_blank_square < nr:
possible_actions.remove('UP')
if index_blank_square % nr == nr - 1:
possible_actions.remove('RIGHT')
if index_blank_square > self.n - nr:
possible_actions.remove('DOWN')
return possible_actions
def result(self, state, action):
""" Given state and action, return a new state that is the result of the action.
Action is assumed to be a valid action in the state """
# blank is the index of the blank square
blank = self.find_blank_square(state)
new_state = list(state)
nr = int(math.sqrt(self.n + 1))
delta = {'UP':-nr, 'DOWN':nr, 'LEFT':-1, 'RIGHT':1}
neighbor = blank + delta[action]
new_state[blank], new_state[neighbor] = new_state[neighbor], new_state[blank]
return tuple(new_state)
def goal_test(self, state):
""" Given a state, return True if state is a goal state or False, otherwise """
return state == self.goal
def check_solvability(self, state):
inversion = 0
for i in range(len(state)):
for j in range(i, len(state)):
if state[i] > state[j] != 0:
inversion += 1
return inversion % 2 == 0
def h(self, node):
""" Return the heuristic value for a given state. Default heuristic function used is
h(n) = number of misplaced tiles """
return sum(s != g for (s, g) in zip(node.state, self.goal))
................
from problem import NPuzzle
from math import *
class NPuzzleMiss(NPuzzle):
def h(self, node):
""" Return the heuristic value for a given state. Default heuristic function used is
h(n) = number of misplaced tiles """
return sum(s != g for (s, g) in zip(node.state, self.goal))
class NPuzzleMht(NPuzzle):
def h(self, node):
""" implement Manhattan distance. Hint! Look at
Missplaced Tiles heuristic function above """
return sum(abs(e - s) for (s, e) in zip(node.state, self.goal))
class NPuzzleEuc(NPuzzle):
""" implement Euclidean distance. """
def h(self, node):
return sqrt(sum(pow((x - s), 2) for (s, x) in zip(node.state, self.goal)))
class NPuzzleRC(NPuzzle):
def h(self, node):
size = ceil(sqrt(len(self.goal)))
sr = sc = 0
for i in range(0, size):
sr = sr + sum(s != g for (s, g) in zip(node.state[i * size:(i + 1) * size], self.goal[i * size:(i + 1) * size]))
for i in range(0, size):
sc = sc + sum(s != g for (s, g) in zip(node.state[i:len(node.state):size], self.goal[i:len(self.goal):size]))
return sr + sc