Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

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)

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Theory And Application Bio Science And Bio Technology International Conferences DTA And BSBT 2011 Held As Part Of The Future Generation In Computer And Information Science 258

Authors: Tai-hoon Kim ,Hojjat Adeli ,Alfredo Cuzzocrea ,Tughrul Arslan ,Yanchun Zhang ,Jianhua Ma ,Kyo-il Chung ,Siti Mariyam ,Xiaofeng Song

2011th Edition

3642271561, 978-3642271564

More Books

Students also viewed these Databases questions

Question

=+4. What is your current position?

Answered: 1 week ago