У меня есть такой алгоритм поиска A *:
def solve_puzzle(current_state, choosen_heuristic):
open_list = []
closed_list = []
init_node = Node(current_state)
open_list.append(init_node) #putting first node into open_list
while len(open_list) != 0:
node = open_list.pop(0) #thanks to the always sorted open_list, the best node to explore is at the beginning
if node in closed_list: #if this node is in closed_list, pass and take another node from open_list. Do this until you got a node that is not in closed_list
pass
if (node.parent != None): #check if the child node is the goal we want to reach
node.check_if_goal_is_reached()
node.generate_children(choosen_heuristic) #here are child generated, also heuristic cost is calculated
child_list = []
for i in range(4): #store each child in the child_list
if node.child[i] is not None:
set_child_priority(node.child[i])
child_list.insert(0, node.child[i])
temp_list = []
for i in range(len(child_list)): #append each child to open_list
open_list.append(child_list[i])
temp_list = sorted(open_list, key=get_node_priority) #sort the open_list, so the best node is at the beginning
open_list = temp_list
closed_list.append(node) # put the node that we expanded into closed_list
Ниже вы можете увидеть фрагмент функции generate_children () (для перемещения плитки вверх):
def generate_children(self, choosen_heuristic):
global n_size
global m_size
global dimension
global goal_state
current_node_blank_position = self.get_blank_tile_position() # current blank node position (index) - custom function, works perfect
# MOVE UP - I move a tile with number on it, not the blank one
if current_node_blank_position < (dimension - n_size) and self.last_operator != "DOWN": # if I can move up and it wont take me back where I came from
# I'm gonna create child for this node
self.child[0] = Node(self.current_state) #right now I dont have the updated state for this child, I will update it later below in this code
self.child[0].parent = self # the node I am expanding is a parent of this child
# Now I am going to change the childs state = parents state but after I moved DOWN
# So I here I set the index of blank tile
new_blank_position = current_node_blank_position + m_size
# normal swap = swap of the two tiles, this will give me the updated state of child
temp = self.child[0].current_state[current_node_blank_position]
self.child[0].current_state[current_node_blank_position] = self.child[0].current_state[new_blank_position]
self.child[0].current_state[new_blank_position] = temp
self.child[0].last_operator = "UP" # I came by moving UP to this child
self.child[0].depth = self.depth + 1 # childs depth = parents depth increased by one
# check which heuristic function user chose and calculate the heuristic_cost for this child
if choosen_heuristic == "misplaced":
# sum of misplaced tiles ( updated child state -> goal state)
self.child[0].misplaced_tiles_heuristic()
if choosen_heuristic == "manhattan":
# manhattan distance sum ( updated child state -> goal state)
self.child[0].manhattan_distance()
else:
# If I cant move UP
self.child[0] = None
Когда Я пытаюсь решить 8-головоломку, которая расширяет всего 8 000 узлов, я нахожу решение в секунду. Когда я расширяю 60 000 узлов, это занимает 15 минут, а если я расширяю 250 000 узлов, это занимает более часа. Это невероятно неправильно. Расширение 200 000 узлов должно занять всего несколько секунд.
Что я делаю не так? Почему это так долго? Как я могу это исправить? Спасибо за любую помощь.