A* search algorithm: Difference between revisions
→{{header|Phix}}: extra credit
(added Ol) |
(→{{header|Phix}}: extra credit) |
||
Line 1,814:
</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.
==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}}==
| |||