MidTermAstarSearch

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