Application of Breath-first search in AI(route search)
According to bfs, it is a search method to go through all the nodes layer by layer, until the gal has been found.
To make it simple, there is a visiting sequence of bfs:
Attention:
When we have goal test with node 0 we should create 1,2,3 node but nothing to do with goal test, as before, when we have goal test with node 1, we should create 4,5,6 immediately and so on.
Here comes an exercise:
A red bird wants to find the yellow bird in the shortest route and find this route in the shortest time.
we want to use the bfs, while due to the physical situation, we have to offer some methods to avoid heading back and visiting the some position twice.
below is my code in python3:
importfrontiersdefsolve(problem):state=problem.initial_state#thestartlocationmap={}#adictostorethewholemapmap[state]=set()#asettostoreanodemap[state].add(0)#addtheparentsinformationtoasetmap[state].add('root')#initializetherootnodequeue_node_created=frontiers.Queue()#storethepositionofnodescreatedqueue_node_created.push(state)#initializationpath_stack=frontiers.Stack()#storethepathininvertedorderlist_queue=[]#storethepathinrightorderwhileTrue:node_value=queue_node_created.pop()#popthenodeinthequeueforgoal_testorexpendingnewnodesifproblem.goal_test(node_value):#goaltestwhileTrue:list_1=list(map[node_value])iftype(list_1[0])==str:parent_node_value=list_1[1]last_action=list_1[0]#findactiontakenandparentnodeelse:parent_node_value=list_1[0]last_action=list_1[1]#findactiontakenandparentnodeiflast_action=='root':#iffindtherootbreakpath_stack.push(last_action)#storetheactiontakennode_value=parent_node_value#refreshthenode_valueprint(last_action)whilenotpath_stack.is_empty():list_queue.append(path_stack.pop())returnlist_queue#returnthepathelse:Next_steps=problem.get_successors(node_value)#getsuccessorsfornodeinNext_steps:node_position=node[0]ifnode_positioninmap.keys():#incasethatthesamenodeisvisitedmorethantwicecontinueelse:map[node_position]=set()#pushthenodeinfo(parent'spositionandaction)intomapmap[node_position].add(node_value)map[node_position].add(node[1])queue_node_created.push(node_position)#pushthenewnodeintothequeue
In the appendix, there are two pictures of the result and the shade of color means the frequency of visiting in our algorithm.
At the beginning, I used the list with dictionaries in it. The list represents the whole tree and a dictionary act as a layer. In this way, I can easily store the entire tree. But, after testing, the effect of it was quite low, like the 24th or 25th floor could be the deepest layer in 1 min's running.
I felt hopeless due to the perform of what I had programmed. I spent 2days to finish it. Thanks to my female friend who is much smarter than me, I found a better solution to deal with node storage and new node' test in sequence just as you can see in my code.
Pay more attention to the scope of the variables, semantic problems and solutions to the problem. we can save lots of time.
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。