A* search algorithm: Difference between revisions
J
(J) |
|||
Line 1,771:
Path score: 11</pre>
=={{header|J}}==
Implementation:
<lang J>
barrier=: 2 4,2 5,2 6,3 6,4 6,5 6,5 5,5 4,5 3,5 2,4 2,:3 2
price=: _,.~_,~100 barrier} 8 8$1
dirs=: 0 0-.~>,{,~<i:1
start=: 0 0
end=: 7 7
next=: {{
frontier=. ~.locs=. ,/dests=. ($price)|"1 ({:"2 y)+"1/dirs
paths=. ,/y,"2 1/"2 dests
costs=. ,x+(<"1 dests){price
deals=. (1+locs <.//. costs) <. (<"1 frontier) { values
keep=. costs < (frontier i. locs) { deals
(keep#costs);keep#paths
}}
Asrch=: {{
values=: ($price)$_
best=: ($price)$a:
paths=: ,:,:start
costs=: ,0
while. #paths do.
dests=. <"1 {:"2 paths
values=: costs dests} values
best=: (<"2 paths) dests} best
'costs paths'=.costs next paths
end.
((<end){values) ; (<end){best
}}</lang>
Task example:
<lang J> Asrch''
┌──┬───┐
│11│0 0│
│ │1 1│
│ │2 2│
│ │3 1│
│ │4 1│
│ │5 1│
│ │6 2│
│ │7 3│
│ │7 4│
│ │7 5│
│ │7 6│
│ │7 7│
└──┴───┘
</lang>
Note that this is based on a literal reading of the task, where we are paying a cost to move into a new square -- here, we are not paying for the cost of the start square, because we never move into that square. If we paid to move into the start square, the final cost would have to include that price.
=={{header|Java}}==
| |||