Я пытаюсь разработать программу-головоломку из 15 звезд в Python, и она должна отсортировать все в числовом порядке, используя алгоритм поиска по звездам с 0 в конце.
Вот мой звездный алгоритм, который я разработал до сих пор:
"""Search the nodes with the lowest f scores first.
You specify the function f(node) that you want to minimize; for example,
if f is a heuristic estimate to the goal, then we have greedy best
first search; if f is node.depth then we have breadth-first search.
There is a subtlety: the line "f = memoize(f, 'f')" means that the f
values will be cached on the nodes as they are computed. So after doing
a best first search you can examine the f values of the path returned."""
def best_first_graph_search_manhattan(root_node):
start_time = time.time()
f = manhattan(root_node)
node = root_node
frontier = []
# how do we create this association?
heapq.heappush(frontier, node)
explored = set()
z = 0
while len(frontier) > 0:
node = heapq.heappop(frontier)
print(node.state.tiles)
explored.add(node)
if (goal_test(node.state.tiles)):
#print('In if statement')
path = find_path(node)
end_time = time.time()
z = z + f
return path, len(explored), z, (end_time - start_time)
for child in get_children(node):
# calcuate total cost
f_0 = manhattan(child)
z = z + f_0
print(z)
if child not in explored and child not in frontier:
#print('Pushing frontier and child')
heapq.heappush(frontier, child)
print('end of for loop')
return None
"""
Return the heuristic value for a given state using manhattan function
"""
def manhattan(node):
# Manhattan Heuristic Function
# x1, y1 = node.state.get_location()
# x2, y2 = self.goal
zero_location = node.state.tiles.index('0')
x1 = math.floor(zero_location / 4)
y1 = zero_location % 4
x2 = 3
y2 = 3
return abs(x2 - x1) + abs(y2 - y1)
"""
astar_search() is a best-first graph searching algortithim using equation f(n) = g(n) + h(n)
h is specified as...
"""
def astar_search_manhattan(root_node):
"""A* search is best-first graph search with f(n) = g(n)+h(n).
You need to specify the h function when you call astar_search, or
else in your Problem subclass."""
return best_first_graph_search_manhattan(root_node)
Вот и остальная часть моей программы. Предположим, что все работает правильно следующим образом:
import random
import math
import time
import psutil
import heapq
#import utils.py
import os
import sys
from collections import deque
# This class defines the state of the problem in terms of board configuration
class Board:
def __init__(self,tiles):
self.size = int(math.sqrt(len(tiles))) # defining length/width of the board
self.tiles = tiles
#This function returns the resulting state from taking particular action from current state
def execute_action(self,action):
new_tiles = self.tiles[:]
empty_index = new_tiles.index('0')
if action=='l':
if empty_index%self.size>0:
new_tiles[empty_index-1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-1]
if action=='r':
if empty_index%self.size<(self.size-1):
new_tiles[empty_index+1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+1]
if action=='u':
if empty_index-self.size>=0:
new_tiles[empty_index-self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-self.size]
if action=='d':
if empty_index+self.size < self.size*self.size:
new_tiles[empty_index+self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+self.size]
return Board(new_tiles)
# This class defines the node on the search tree, consisting of state, parent and previous action
class Node:
def __init__(self,state,parent,action):
self.state = state
self.parent = parent
self.action = action
#self.initial = initial
#Returns string representation of the state
def __repr__(self):
return str(self.state.tiles)
#Comparing current node with other node. They are equal if states are equal
def __eq__(self,other):
return self.state.tiles == other.state.tiles
def __hash__(self):
return hash(self.state)
def __lt__(self, other):
return manhattan(self) < manhattan(other)
# Utility function to randomly generate 15-puzzle
def generate_puzzle(size):
numbers = list(range(size*size))
random.shuffle(numbers)
return Node(Board(numbers),None,None)
# This function returns the list of children obtained after simulating the actions on current node
def get_children(parent_node):
children = []
actions = ['l','r','u','d'] # left,right, up , down ; actions define direction of movement of empty tile
for action in actions:
child_state = parent_node.state.execute_action(action)
child_node = Node(child_state,parent_node,action)
children.append(child_node)
return children
# This function backtracks from current node to reach initial configuration. The list of actions would constitute a solution path
def find_path(node):
path = []
while(node.parent is not None):
path.append(node.action)
node = node.parent
path.reverse()
return path
# Main function accepting input from console , running iterative_deepening_search and showing output
def main():
global nodes_expanded
global path
global start_time
global cur_time
global end_time
nodes_expanded = 0
process = psutil.Process(os.getpid())
initial_memory = process.memory_info().rss / 1024.0
initial = str(input("initial configuration: "))
initial_list = initial.split(" ")
root = Node(Board(initial_list),None,None)
print(astar_search_manhattan(root))
final_memory = process.memory_info().rss / 1024.0
print('Directions: ', path)
print('Total Time: ', (end_time-start_time), ' seconds')
print('Total Memory: ',str(final_memory-initial_memory)+" KB")
print('Total Nodes Expanded: ', nodes_expanded)
# Utility function checking if current state is goal state or not
def goal_test(cur_tiles):
return cur_tiles == ['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','0']
if __name__=="__main__":main()
Мне удалось сузить его до моего значения для l oop в моей функции best_first_graph_search_manhattan, и кажется, что вызвано бесконечное значение l oop оператор if, где проверяется, находится ли дочерний элемент в исследуемом, а дочерний не в границах. Я не уверен, так ли это, как я вызываю функцию своего ребенка или как я помещаю границу и ребенка в мою очередь приоритетов. Я импортировал heapq в свою программу и провел обширные исследования, в которых импорт этой функции позволяет использовать приоритетную очередь в вашей программе. Пожалуйста, не обращайте внимания на другие переменные, которые не используются в моем поиске по звездам.
Вот тестовый пример: 1 0 3 4 5 2 6 8 9 10 7 11 13 14 15 12 | DRDRD
Большое спасибо всем за помощь!