Python: стоимость поиска / эвристика N-Puzzle
Мне нужно решить N-головоломку, используя список различных методов поиска: A*, равномерная стоимость, в ширину, в глубину и в первую очередь с жадным поиском (поиск по дереву и графу для каждого типа). Когда я запускаю код, он дает мне одинаковый ответ (путь решения и стоимость) для каждого типа. Я почти уверен, что он просто вычисляет стоимость как количество ходов от начала до конца g(n), хотя я попытался добавить h(n) к некоторым из затрат.
Я должен ссылаться на два файла.py в моем коде, содержащие потенциально полезные функции и классы - search.py и utils.py. Я импортировал некоторые функции и классы непосредственно из этих файлов, а для других я написал измененные версии внутри своего собственного документа.
Пожалуйста, дайте мне знать, если вы понимаете, почему я получаю одинаковую стоимость каждый раз. Я вставил свой код в блок ниже. Файлы search.py и utils.py превысили ограничение на количество символов, поэтому вместо этого здесь есть ссылки github на необработанный текст:
Мой код:
from search import *
from utils import *
import math
from math import *
########################
### CLASS DEFINITION ###
########################
class nPuzzle(Problem):
def __init__(self, initial, goal):
self.problem = Problem(initial, goal)
super().__init__(initial, goal)
def find_blank_square(self, state):
if type(state[0]) == int:
return state.index(0)
else:
return state.index('0')
def actions(self, state):
possible_actions = ['UP', 'DOWN', 'LEFT', 'RIGHT']
index_blank_square = self.find_blank_square(state)
n = len(state)
row_length = int(sqrt(n))
if index_blank_square % row_length == 0:
possible_actions.remove('LEFT')
if index_blank_square <= row_length:
possible_actions.remove('UP')
if index_blank_square % row_length == row_length-1:
possible_actions.remove('RIGHT')
if index_blank_square >= n - row_length:
possible_actions.remove('DOWN')
return possible_actions
def result(self, state, action):
n = len(state)
row_length = int(sqrt(n))
blank = self.find_blank_square(state)
new_state = list(state)
delta = {'UP': -row_length, 'DOWN': row_length, '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):
return state == self.goal
def check_solvability(self, state):
inversion = 0
for i in range(len(state)):
for j in range(i + 1, len(state)):
if (state[i] > state[j]) and state[i] != 0 and 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))
########################
### SEARCH FUNCTIONS ###
########################
def uniform_cost_tree_search(problem, display=False):
return best_first_tree_search(problem, lambda node: node.path_cost, display)
def uniform_cost_graph_search(problem, display=False):
return best_first_graph_search(problem, lambda node: node.path_cost, display)
def best_first_graph_search(problem, f, display=False):
f = memoize(f, 'f')
node = Node(problem.initial)
frontier = PriorityQueue('min', f)
frontier.append(node)
explored = set()
while frontier:
node = frontier.pop()
if problem.goal_test(node.state):
return node
explored.add(node.state)
for child in node.expand(problem):
if child.state not in explored and child not in frontier:
frontier.append(child)
elif child in frontier:
if f(child) < frontier[child]:
del frontier[child]
frontier.append(child)
return None
def best_first_tree_search(problem, f, display=False):
f = memoize(f, 'f')
node = Node(problem.initial)
frontier = PriorityQueue('min', f)
frontier.append(node)
explored = set()
while frontier:
node = frontier.pop()
if problem.goal_test(node.state):
return node
frontier.extend(node.expand(problem))
return None
def astar_tree_search(problem, h = None, display=False):
h = memoize(h or problem.h, 'h')
return best_first_tree_search(problem, lambda n: n.path_cost + h(n), display = False)
def astar_graph_search(problem, h=None, display=False):
h = memoize(h or problem.h, 'h')
return best_first_graph_search(problem, lambda n: n.path_cost + h(n), display = False)
def greedy_best_first_tree_search(problem, h = None, display = False):
h = memoize(h or problem.h, 'h')
return best_first_tree_search(problem, lambda n: h(n), display = False)
def greedy_best_first_graph_search(problem, h = None, display = False):
h = memoize(h or problem.h, 'h')
return best_first_graph_search(problem, lambda n: h(n), display = False)
def depth_first_tree_search(problem):
frontier = [Node(problem.initial)]
while frontier:
node = frontier.pop()
if problem.goal_test(node.state):
return node
frontier.extend(node.expand(problem))
return None
def depth_first_graph_search(problem):
frontier = [(Node(problem.initial))]
explored = set()
while frontier:
node = frontier.pop()
if problem.goal_test(node.state):
return node
explored.add(node.state)
frontier.extend(child for child in node.expand(problem)
if child.state not in explored and child not in frontier)
return None
######################
### IMPLEMENTATION ###
######################
if __name__ == '__main__':
method_dict = {'UCTS': uniform_cost_tree_search, 'UCGS': uniform_cost_graph_search,
'BFGS': breadth_first_graph_search, 'BFTS': breadth_first_tree_search,
'ASTS': astar_tree_search, 'ASGS': astar_graph_search,
'DFTS': depth_first_tree_search, 'DFGS': depth_first_graph_search,
'GBFTS': greedy_best_first_tree_search, 'GBFGS': greedy_best_first_graph_search}
# I put 'ASTS' here just as an example:
search_algo_str = 'ASTS'
func = method_dict[search_algo_str]
global state
global solution
# The initial state I give here is just an example. The puzzle could be a different size, but will always be a square."""
state = [1, 5, 2, 3, 8, 4, 6, 7, 0, 9, 10, 11, 12, 13, 14, 15]
# Whatever the dimensions, the solution will always start at 0 and count up.
goal_ = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
puzzle = nPuzzle(initial = tuple(state), goal = tuple(goal_))
goal_node = func(puzzle)
# Do not change the code below
if goal_node is not None:
print("Solution path", goal_node.solution())
print("Solution cost", goal_node.path_cost)
else:
print("No solution was found.")