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 