A* search algorithm: Difference between revisions
Content added Content deleted
(added Ol) |
(→{{header|Phix}}: extra credit) |
||
Line 1,814: | Line 1,814: | ||
</pre> |
</pre> |
||
The : represent nodes it did not even look at, the . those added but never gone back to, obviously x represent the path, and together _ and x all nodes actually analysed. |
The : represent nodes it did not even look at, the . those added but never gone back to, obviously x represent the path, and together _ and x all nodes actually analysed. |
||
==Extra credit== |
|||
Well, why not. Note this does not reuse/share any code with the above, although I presume the |
|||
task author assumed it would, instead the main loop uses a priority queue to obtain the next |
|||
lowest cost and a simple dictionary to avoid re-examination/inifinte recursion. |
|||
<lang Phix>--set_rand(3) -- (for consistent output) |
|||
constant optimal = false, |
|||
mtm = true, -- mutli-tile metrics |
|||
target = {1,2,3,4,5,6,7,8,0}, |
|||
-- <-tile found 0..8-> |
|||
mcost = {{0,0,1,2,1,2,3,2,3}, -- position 1 |
|||
{0,1,0,1,2,1,2,3,2}, |
|||
{0,2,1,0,3,2,1,4,3}, |
|||
{0,1,2,3,0,1,2,1,2}, |
|||
{0,2,1,2,1,0,1,2,1}, -- ... |
|||
{0,3,2,1,2,1,0,3,2}, |
|||
{0,2,3,4,1,2,3,0,1}, |
|||
{0,3,2,3,2,1,2,1,0}, |
|||
{0,4,3,2,3,2,1,2,1}}, -- position 9 |
|||
udlr = "udlr", |
|||
dirs = {+3,-3,+1,-1}, -- udlr |
|||
lims = {{9,9,9,9,9,9,9,9,9}, -- up |
|||
{1,1,1,1,1,1,1,1,1}, -- down |
|||
{3,3,3,6,6,6,9,9,9}, -- left |
|||
{1,1,1,4,4,4,7,7,7}} -- right |
|||
function get_moves(sequence grid, bool mtm) |
|||
sequence valid = {} |
|||
integer p0 = find(0,grid) |
|||
for dx=1 to length(dirs) do |
|||
integer step = dirs[dx], |
|||
lim = lims[dx][p0], |
|||
count = 1 |
|||
for i=p0+step to lim by step do |
|||
valid = append(valid,{step,i,udlr[dx],count}) |
|||
if not mtm then exit end if |
|||
count += 1 |
|||
end for |
|||
end for |
|||
return valid |
|||
end function |
|||
function make_move(sequence grid, move) |
|||
integer p0 = find(0,grid), |
|||
{step,lim} = move |
|||
for i=p0+step to lim by step do |
|||
grid[p0] = grid[i] |
|||
grid[i] = 0 |
|||
p0 = i |
|||
end for |
|||
return grid |
|||
end function |
|||
function manhattan(sequence grid) |
|||
integer res = 0 |
|||
for i=1 to 9 do |
|||
res += mcost[i][grid[i]+1] |
|||
end for |
|||
return res |
|||
end function |
|||
sequence problem, grid, new_grid, |
|||
moves, next_moves, move |
|||
procedure show_grid() |
|||
printf(1,"%s\n",join_by(sq_add(grid,'0'),1,3,"")) |
|||
end procedure |
|||
grid = target |
|||
for i=1 to 1000 do |
|||
-- (initially shuffle as if mtm==true, otherwise |
|||
-- output compares answers to different puzzles) |
|||
moves = get_moves(grid,true) |
|||
move = moves[rand(length(moves))] |
|||
grid = make_move(grid,move) |
|||
end for |
|||
problem = grid |
|||
printf(1,"problem (manhattan cost is %d):\n",manhattan(grid)) |
|||
show_grid() |
|||
integer todo = pq_new(), |
|||
seen = new_dict() |
|||
pq_add({{grid,{}},iff(optimal?0:manhattan(grid))},todo) |
|||
setd(grid,true,seen) |
|||
atom t1 = time()+1 |
|||
bool found = false |
|||
integer count = 0, mc |
|||
while not found do |
|||
if pq_size(todo)=0 then ?"impossible" exit end if |
|||
{{grid,moves},mc} = pq_pop(todo) |
|||
if time()>t1 then |
|||
string m = iff(optimal?"moves":"manhattan") |
|||
printf(1,"searching (count=%d, %s=%d)\r",{count,m,mc}) |
|||
t1 = time()+1 |
|||
end if |
|||
next_moves = get_moves(grid,mtm) |
|||
count += length(next_moves) |
|||
integer l = length(moves) |
|||
for i=1 to length(next_moves) do |
|||
move = next_moves[i] |
|||
new_grid = make_move(grid,move) |
|||
mc = manhattan(new_grid) |
|||
if mc=0 then |
|||
if new_grid!=target then ?9/0 end if |
|||
moves = append(moves,move) |
|||
found = true |
|||
exit |
|||
end if |
|||
if getd_index(new_grid,seen)=NULL then |
|||
if optimal then mc = l+1 end if |
|||
pq_add({{new_grid,append(moves,move)},mc},todo) |
|||
setd(new_grid,true,seen) |
|||
end if |
|||
end for |
|||
end while |
|||
if found then |
|||
string s = iff(length(moves)=1?"":"s") |
|||
if optimal then |
|||
s &= sprintf(" (max shd be %d)",iff(mtm?24:31)) |
|||
end if |
|||
grid = problem |
|||
string soln = "" |
|||
for i=1 to length(moves) do |
|||
move = moves[i] |
|||
grid = make_move(grid,move) |
|||
integer {{},{},ch,c} = move |
|||
soln &= ch |
|||
if c>1 then soln&='0'+c end if |
|||
-- show_grid() -- (set the initial shuffle to eg 5 first!) |
|||
end for |
|||
-- show_grid() -- (not very educational!) |
|||
if grid!=target then ?9/0 end if |
|||
printf(1,"solved in %d move%s:%s\n",{length(moves),s,soln}) |
|||
end if |
|||
printf(1,"count:%d, seen:%d, queue:%d\n",{count,dict_size(seen),pq_size(todo)})</lang> |
|||
{{out}} |
|||
Note: The solutions are non-optimal (far from it, in fact), since it searches lowest manhattan() first.<br> |
|||
In fact that set_rand(3), used for all the results below, is somewhat worse than 0, 1, and 2, and the |
|||
first to breach optimal limits, ie 31/24, but obviously only when the optimal flag is set to false, as |
|||
well as being the first to hint at the potential thousand-fold-or-more performance gains on offer.<br> |
|||
An optimal solution can instead be found by searching fewest moves first, albeit significantly slower! |
|||
Note this approach is not really suitable for solving 15-puzzles (or larger).<br> |
|||
with optimal false and mtm false: |
|||
<pre> |
|||
problem (manhattan cost is 20): |
|||
546 |
|||
807 |
|||
321 |
|||
solved in 88 moves:ulddruurdluldrdluurrddlurulldrrdlulurrddlurulldrdlururdllurrdlulddrurdlurdlulurrddlurull |
|||
count:592, seen:371, queue:155 |
|||
</pre> |
|||
with optimal false and mtm true: |
|||
<pre> |
|||
solved in 45 moves:uld2r2u2l2d2r2u2ld2rul2dru2rdl2urdrdlu2rd2luruld2ru2l2dr2uldlu |
|||
count:328, seen:164, queue:82 |
|||
</pre> |
|||
with optimal true and mtm false: |
|||
<pre> |
|||
solved in 26 moves (max shd be 31):rulldrdruulddruullddrruull |
|||
count:399996, seen:163976, queue:13728 |
|||
</pre> |
|||
with optimal true and mtm true: |
|||
<pre> |
|||
solved in 17 moves (max shd be 24):rul2drdru2ld2ru2l2d2r2u2l2 |
|||
count:298400, seen:106034, queue:31434 |
|||
</pre> |
|||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |