A* search algorithm: Difference between revisions
Content added Content deleted
(J) |
|||
Line 1,771: | Line 1,771: | ||
Path score: 11</pre> |
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}}== |
=={{header|Java}}== |