MidTermAstarSearch
Jump to navigation
Jump to search
Note 'explanation' In this graph: The path direction is downward. Each step costs 10. Node numbers are the value of the heuristic. (estimated remaining cost to reach the goal) The test required us to find the order of the nodes expanded in an A* search, and to indicate if the heuristic is admissible. The heuristic is not admissible because it overestimates in one case the cost to reach the goal. Start: n15. Goal: n0. ---------------n15-------------- / / | \ \ n11 n8 n7 n6 n10 / / \ / \ \ n2 n3 n9 n5 n20----> n0 ) NodeNames=: ;:'n15 n11 n8 n7 n6 n10 n2 n3 n9 n5 n20 g0' heuristic=: ;@:(".@:}.&.>)NodeNames NB. entry for each node Paths=: ".;._2]0 :0 NB. columns are start_node end_node path_cost 0 1 10 0 2 10 0 3 10 0 4 10 0 5 10 1 6 10 2 7 10 2 8 10 4 9 10 4 10 10 5 11 10 10 11 10 ) Universe=: NodeNames;Paths extractNodes=: 0&{:: extractPaths=: 1&{:: links=: 2&(]\>) NB. (links 0 1 2) -: 0 1,:1 2 NB. cost function weigh=: [: +/ links@:>@[ ((i.~ _ 2&{.) { 2&{"1@]) extractPaths@] NB. path weigh Universe NB. the heuristic is the ordered vector of estimates for each node of the graph weighAStar=: 1 : 'weigh + m {~ {:@:;@:[' steps=: #@>@[ NB. path steps Universe Choice=:2 : '{.@I.@(= u)@:(v"0 _)' NB. frontier (<./)Cost steps Universe BreadthFirst=: 0: IndexShortest=: <./ Choice steps NB. frontier IndexShortest Universe IndexLongest=: >./ Choice steps NB. needs all paths, works not IndexCheapest=: <./ Choice weigh IndexAStar=: <./ Choice (heuristic weighAStar) NB. heuristic must be defined here as noun toString=: >@(({~ 0&+)~ :: [) extractNodes NB. 1 toString Universe toIndex=: (0+[) :: (]i.<@:>@[) extractNodes NB. 1 toIndex Universe Display=: [: smoutput toString ExtractFrontier=: toIndex ((I.@e.~ _ 1 ,@{. ]) { ]) extractPaths@] NB. 'Arad'ExtractFrontier Universe Transition=: 1&{"1@ExtractFrontier NB. frontier is a list of boxed paths NB. frontier Choose universe returns index of next path to follow IsEmpty=: 0 = # IsGoal=: 1 : (':'; 'x m&-:@toString y') graphSearch=: adverb define : '`display isEmpty choose isGoal transition'=. m 'initial goal'=. x universe=. y explored=. '' frontier=. ,<initial toIndex universe while. 0=isEmpty frontier do. i=. frontier choose universe path=. i >@{ frontier universe display~ state=. {: path if. state isGoal universe do. path return. end. frontier=. (<<<i){frontier NB. elision explored=. explored , state adjacencies=. state transition universe unseenAdjacencies=. adjacencies -. explored NB. , {:@>frontier frontier=. frontier , path <@,"1 0 unseenAdjacencies end. EMPTY ) (;:'n15 g0') Display`IsEmpty`IndexAStar`('g0'IsGoal)`Transition graphSearch Universe