# 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&{::

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
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')

:
'`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