In Python with A Star

How would you delete an element in a fringe that is similar to the expanded list? In A-Star once you expanded a node you cannot revisit that node in the fringe.

Because simple test cases such as [0, 1, 2, 3, 8, 4, 6, 7, 5] work fine but when it comes to more complex cases such as [6, 4, 0, 1, 5, 3, 7, 8, 2] the program runs and it seems like there are repeated items being expanded.

Here is my code:

from math import sqrt

import time

#fring- to keep the nodes

#expand: the function to expand one node at a time

#heuristic: calculate the cheapest cost

#f()- total cost

#h()- the number index to the goal

#expanded_nodes- have all the visited

startime = time.time_ns()

def astar(puzzle):

#intializing the variables

cost = 0

node = Node(puzzle,cost)

loop = True

#the possible nodes

fringe = []

#After expanding the list

expanded = []

# maybe need it keep it for now

visit = set() #keep track of all the visit

#the goal state

goal = [0,1,2,3,4,5,6,7,8]

#possible combination move

possible_move = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]

#intialization of the first node

fringe = [node]

#print('state:'+str(node.state))

#start the loop

while loop:

print(' the state of this game position is: ' + str(node.state) +" ")

#find the lowest cost in the fringe then expand the lowest cost node

min_cost = fringe[0].cost

min_node = fringe[0]

for node in fringe:

if node.cost < min_cost:

min_cost = node.cost

min_node = node

#append the node that was just expaneded into the expanded list but keep the list not expaneded in fringe

expanded.append(min_node)

print('the min node '+str(min_node.state)+' the cheapest cost: '+ str(min_cost) + ' ')

#removes the min cost node from fringe

for node in fringe[:]:

if node.state == min_node.state:

fringe.remove(node)

#when there is a solution in the expanded

for node in expanded:

if node.state == goal:

loop = False

#checking the node in fringe

for node in fringe:

print(node.state)

# key = tuple(node.state)

# if key in visit:

# continue

# visit.add(key)

#traverse the nodes that was expanded and add the children to the fringe

# for node in expanded[:]:

for node in expanded[:]:

#append all the successor/children and set the children's parent to fringe

blank = node.state.index(8)

print('the index of the blank is '+ str(blank))

print(' ')

possible_pos = possible_move[blank]

print('possible pos '+ str(possible_pos))

for i in possible_pos:

#if node not in visit:

print(' ')

possible_sw = node.state[:]

print('index swap = '+ str(i))

possible_sw[blank] = possible_sw[i]

possible_sw[i] = 8

print('the child node is ' + str(possible_sw))

node.cost = manhattan(possible_sw, goal)

fringe.append(Node(possible_sw,node.cost,node))

print('the cost this node state: '+ str(node.cost))

for node in expanded[:]:

if node.cost > min_cost:

expanded.pop(0)

#finding the solution

solution = expanded

move = 0

while node.parent:

solution.append(node.state.index(8))

node = node.parent

move += 1

print('moves made '+ str(move))

solution.reverse()

print('moves list '+ str(solution))

endtime = time.time_ns()

executionTime = ( endtime - startime)

print('Execution time in ns: ' + str(executionTime))

return solution

#Try the Manhattan Distance for moving only four direction up,down,left,right

def manhattan(a, b):

return sum(abs(val1-val2) for val1, val2 in zip(a,b))

class Node:

def __init__(self,state,cost,parent = None):

self.parent = parent

self.state = state

self.cost = cost

self.children = []

#test case

p = [0, 1, 2, 3, 4, 5, 6, 8, 7]

p = [0, 1, 2, 3, 8, 4, 6, 7, 5]

#p= [6, 4, 0, 1, 5, 3, 7, 8, 2]

#p = [1, 8, 2, 0, 3, 5, 6, 4, 7]

#p = [1, 3, 2, 0, 5, 7, 6, 8, 4]

print("++++++++++A*++++++++++++")

astar(p)