Rosetta Code

A* search algorithm: Difference between revisions

Page Discussion

A* search algorithm (view source)

Revision as of 09:00, 7 April 2024

2,455 bytes added ,  1 month ago
m
→‎{{header|11l}}: X.throw
 
(10 intermediate revisions by 5 users not shown)
Line 35:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">F AStarSearch(start, end, barriers)
F heuristic(start, goal)
V D = 1
Line 103:
f[neighbour] = G[neighbour] + H
 
X.throw RuntimeError(‘A* failed to find a solution’)
 
V (result, cost) = AStarSearch((0, 0), (7, 7), [[(2, 4), (2, 5), (2, 6), (3, 6), (4, 6), (5, 6), (5, 5), (5, 4), (5, 3), (5, 2), (4, 2), (3, 2)]])
print(‘route ’result)
print(‘cost ’cost)</langsyntaxhighlight>
 
{{out}}
Line 116:
 
=={{header|C}}==
<syntaxhighlight lang="c">
<lang c>
#include <stdlib.h>
#include <stdio.h>
Line 367:
return 0;
}
</syntaxhighlight>
</lang>▼
{{out}}
<pre>
Line 396:
 
=={{header|C sharp|C#}}==
<langsyntaxhighlight lang="csharp">
using System;
using System.Collections.Generic;
Line 646:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 663:
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">
#include <list>
#include <algorithm>
Line 828:
return 0;
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 847:
=={{header|Common Lisp}}==
 
<langsyntaxhighlight lang="lisp">;; * Using external libraries with quicklisp
(eval-when (:load-toplevel :compile-toplevel :execute)
(ql:quickload '("pileup" "iterate")))
Line 961:
0)))
;; Check if this state was already looked at
(unless (gethash position visited))
;; Insert the next node into the queue
(heap-insert
(node :pos position :path (cons position (node-path node))
:cost cost :f-value f-value)
queue)))))
 
;; The actual A* search
Line 1,003:
(a* start goal heuristics #'next-positions 0)
(format t "Found the shortest path from Start (●) to Goal (◆) in ~D steps with cost: ~D~%" steps cost)
(print-path path start goal)))</langsyntaxhighlight>
 
{{out}}
Line 1,023:
=={{header|D}}==
ported from c++ code
<syntaxhighlight lang="d">
<lang D>
 
import std.stdio;
Line 1,180:
return 0;
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,198:
 
=={{Header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">
'###############################
'### A* search algorithm ###
Line 1,446:
end if
end
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,465:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">// Package astar implements the A* search algorithm with minimal constraints
// on the graph representation.
package astar
Line 1,577:
h[last].fx = -1
return h[last]
}</langsyntaxhighlight>
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,633:
fmt.Println("Route:", route)
fmt.Println("Cost:", cost)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,643:
The simplest standalone FIFO priority queue is implemented after Sleator and Tarjan in Louis Wasserman's ''"Playing with Priority Queues"''[https://themonadreader.files.wordpress.com/2010/05/issue16.pdf].
 
<langsyntaxhighlight lang="haskell">{-# language DeriveFoldable #-}
 
module PQueue where
Line 1,669:
deque q = case q of
EmptyQueue -> Nothing
Node (_, x) l r -> Just (x, l <> r)</langsyntaxhighlight>
 
The simple graph combinators:
 
<langsyntaxhighlight lang="haskell">import PQueue
import Data.Map (Map(..))
import qualified Data.Map as Map
Line 1,693:
if x `elem` ns
then Map.empty
else foldr Map.delete (g x) ns </langsyntaxhighlight>
 
Finally, the search algorythmalgorithm, as given in Wikipedia.
 
<langsyntaxhighlight lang="haskell">get :: (Ord k, Bounded a) => Map k a -> k -> a
get m x = Map.findWithDefault maxBound x m
 
Line 1,737:
 
getPath m = reverse $ goal : unfoldr go goal
where go n = (\x -> (x,x)) <$> Map.lookup n m</langsyntaxhighlight>
 
Example
 
<langsyntaxhighlight lang="haskell">distL1 (x,y) (a,b) = max (abs $ x-a) (abs $ y-b)
 
main = let
Line 1,758:
print path
mapM_ putStrLn picture
putStrLn $ "Path score: " <> show (length path) </langsyntaxhighlight>
<pre>λ> main
[(1,1),(2,1),(3,1),(4,1),(5,1),(6,2),(6,3),(6,4),(6,5),(6,6),(7,7)]
Line 1,776:
Implementation:
 
<syntaxhighlight lang="j">
<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
Line 1,804:
end.
((<end){values) ; (<end){best
}}</langsyntaxhighlight>
 
Task example:
 
<langsyntaxhighlight Jlang="j"> Asrch''
┌──┬───┐
│11│0 0│
Line 1,834:
...xxxxx
</syntaxhighlight>
</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}}==
<langsyntaxhighlight lang="java">
package astar;
 
Line 2,080:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,097:
=={{header|JavaScript}}==
Animated.<br />To see how it works on a random map go [http://paulo-jorente.de/tests/astar/ here]
<langsyntaxhighlight lang="javascript">
var ctx, map, opn = [], clsd = [], start = {x:1, y:1, f:0, g:0},
goal = {x:8, y:8, f:0, g:0}, mw = 10, mh = 10, neighbours, path;
Line 2,209:
path = []; createMap(); opn.push( start ); solveMap();
}
</syntaxhighlight>
</lang>
{{out}}<pre>
Path: 11
Line 2,215:
</pre>
Implementation using recursive strategy
<langsyntaxhighlight lang="javascript">
function manhattan(x1, y1, x2, y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
Line 2,288:
 
console.log(aStar(board, 0,0, 7,7));
</syntaxhighlight>
</lang>
{{output}} <pre>
[ [ 0, 0 ], [ 1, 1 ], [ 2, 2 ], [ 3, 1 ], [ 4, 1 ], [ 5, 1 ], [ 6, 1 ], [ 7, 2 ], [ 7, 3 ], [ 7, 4 ], [ 7, 5 ], [ 7, 6 ], [ 7, 7 ] ]
Line 2,294:
=={{header|Julia}}==
The graphic in this solution is displayed in the more standard orientation of origin at bottom left and goal at top right.
<langsyntaxhighlight Julialang="julia">using LightGraphs, SimpleWeightedGraphs
 
const chessboardsize = 8
Line 2,332:
println()
end
end</langsyntaxhighlight> {{output}} <pre>
Solution has cost 11:
Tuple{Int64,Int64}[(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (7, 3), (7, 4), (6, 5), (6, 6), (7, 7)]
Line 2,346:
 
=={{header|Kotlin}}==
<langsyntaxhighlight lang="kotlin">
import java.lang.Math.abs
 
Line 2,457:
println("Cost: $cost Path: $path")
}
</syntaxhighlight>
</lang>
{{out}}<pre>
Cost: 11
Line 2,464:
 
=={{header|Lua}}==
<langsyntaxhighlight lang="lua">
-- QUEUE -----------------------------------------------------------------------
Queue = {}
Line 2,664:
print( "can not find a path!" )
end
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,683:
=={{header|Nim}}==
Implementation of the Wikipedia pseudocode.
<syntaxhighlight lang="nim">
<lang Nim>
# A* search algorithm.
 
Line 2,814:
else:
printSolution(path, cost)
</syntaxhighlight>
</lang>
 
{{out}}
Line 2,839:
A very close/straightforward implementation of the Wikipedia pseudocode.
 
<langsyntaxhighlight lang="ocaml">
module IntPairs =
struct
Line 2,968:
print_newline ()
) _board;
print_newline ()</langsyntaxhighlight>
 
{{out}}
Line 2,997:
 
=={{header|Ol}}==
<langsyntaxhighlight lang="scheme">
; level: list of lists, any except 1 means the cell is empty
; from: start cell in (x . y) mean
Line 3,063:
(cons (+ x 1) y)))))
(step1 (- n 1) c-list-set o-list-set))))))))
</syntaxhighlight>
</lang>
 
{{out}}
<langsyntaxhighlight lang="scheme">
(define level '(
(1 1 1 1 1 1 1 1 1 1)
Line 3,121:
 
(for-each print solved)
</syntaxhighlight>
</lang>
 
<pre>
Line 3,167:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/A*_search_algorithm
Line 3,214:
unshift @path, $pos = $from{$pos};
}
print "$grid\nvalue $values{$finish} path @path\n";</langsyntaxhighlight>
{{out}}
<pre>
Line 3,230:
 
===Extra Credit===
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/A*_search_algorithm
Line 3,307:
abs($r1 - $r2) + abs($c1 - $c2)
} @tiles;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,326:
Note that the 23 visited nodes does not count walls, but with them this algorithm exactly matches the 35 of Racket.
 
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""
x:::::::
Line 3,398:
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</langsyntaxhighlight>-->
 
{{out}}
Line 3,421:
lowest cost and a simple dictionary to avoid re-examination/inifinte recursion.
 
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--set_rand(3) -- (for consistent output)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">optimal</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
Line 3,566:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"count:%d, seen:%d, queue:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">pq_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)})</span>
<!--</langsyntaxhighlight>-->
 
{{out}}
Line 3,603:
=={{header|PowerShell}}==
 
<langsyntaxhighlight lang="powershell">function CreateGrid($h, $w, $fill) {
$grid = 0..($h - 1) | ForEach-Object { , (, $fill * $w) }
return $grid
Line 3,715:
Write-Output "Cost: $cost"
$routeString = ($route | ForEach-Object { "($($_[0]), $($_[1]))" }) -join ', '
Write-Output "Route: $routeString"</langsyntaxhighlight>
{{out}}
<pre>
Line 3,728:
Cost: 11
Route: (0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (7, 3), (6, 4), (7, 5), (6, 6), (7, 7)
▲</langpre>
 
=={{header|Picat}}==
<syntaxhighlight lang="picat">% Picat's tabling system uses an algorithm like Dijkstra's to find an optimal solution.
% Picat's planner supports A* search with heuristics.
% See the program for the 15-puzzle at https://rosettacode.org/wiki/15_puzzle_solver#Picat
%
main =>
Maze = new_array(8,8),
Obs = [(2,4), (2,5), (2,6), (3,6), (4,6), (5,6), (5,5), (5,4), (5,3), (5,2), (4,2), (3,2)],
foreach ((R0,C0) in Obs)
Maze[R0+1,C0+1] = 100
end,
foreach (R in 1..8, C in 1..8)
(var(Maze[R,C]) -> Maze[R,C] = 1; true)
end,
search((1,1),(8,8),Maze,Cost,Path),
writeln(cost=Cost),
println([(R0,C0) : (R1,C1) in Path, R0 = R1-1, C0 = C1-1]).
 
table (+,+,+,min,-)
search(G,G,_Maze,Cost,Path) => Cost = 0, Path = [G].
search(S@(R,C),G,Maze,Cost,Path) =>
neibs(R,C,Neibs),
member(S1,Neibs),
S1 = (R1,C1),
search(S1,G,Maze,Cost1,Path1),
Cost = Cost1+Maze[R1,C1],
Path = [S|Path1].
 
neibs(R,C,Neibs) =>
Neibs = [(R1,C1) : Dr in [-1,0,1], Dc in [-1,0,1], R1 = R+Dr, C1 = C+Dc,
R1 >= 1, R1 <= 8, C1 >= 1, C1 <= 8, (R,C) != (R1,C1)].
</syntaxhighlight>
{{out}}
<pre>
cost = 11
[(0,0),(1,0),(2,0),(3,0),(4,0),(5,1),(6,2),(6,3),(6,4),(6,5),(6,6),(7,7)]
</pre>
 
=={{header|Python}}==
 
<langsyntaxhighlight lang="python">from __future__ import print_function
import matplotlib.pyplot as plt
 
Line 3,833 ⟶ 3,871:
plt.xlim(-1,8)
plt.ylim(-1,8)
plt.show()</langsyntaxhighlight>
 
{{out}}
Line 3,842 ⟶ 3,880:
This code is lifted from: [https://jeapostrophe.github.io/2013-04-15-astar-post.html this blog post]. Read it, it's very good.
 
<langsyntaxhighlight lang="racket">#lang scribble/lp
@(chunk
<graph-sig>
Line 4,065 ⟶ 4,103:
<path-display>
 
(path-image random-M random-path))</langsyntaxhighlight>
 
{{out}}
Line 4,078 ⟶ 4,116:
=={{header|Raku}}==
{{trans|Sidef}}
<syntaxhighlight lang="raku" perl6line># 20200427 Raku programming solution
 
class AStarGraph {
Line 4,170 ⟶ 4,208:
.join.say for @grid ;
 
say "Path cost : ", cost, " and route : ", route;</langsyntaxhighlight>
{{out}}<pre>██████████
█x.......█
Line 4,184 ⟶ 4,222:
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX program solves the A* search problem for a (general) NxN grid. */
parse arg N sCol sRow . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N=8 /*No grid size specified? Use default.*/
Line 4,266 ⟶ 4,304:
say ind translate(L'│', , .) /*display a " " " " */
end /*c*/ /*a 19x19 grid can be shown 80 columns.*/
say ind translate('└'_"┘",'┴',"┼"); return /*display the very bottom of the grid. */</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 4,291 ⟶ 4,329:
 
=={{header|SequenceL}}==
<langsyntaxhighlight lang="sequencel">
import <Utilities/Set.sl>;
import <Utilities/Math.sl>;
Line 4,391 ⟶ 4,429:
value when point.x = i and point.y = j else
map[i,j] foreach i within 1 ... size(map), j within 1 ... size(map[1]);
</syntaxhighlight>
</lang>
{{out|Output|text=&nbsp;}}
<pre>
Line 4,409 ⟶ 4,447:
=={{header|Sidef}}==
{{trans|Python}}
<langsyntaxhighlight lang="ruby">class AStarGraph {
 
has barriers = [
Line 4,513 ⟶ 4,551:
grid.each { .join.say }
 
say "Path cost #{cost}: #{route}"</langsyntaxhighlight>
{{out}}
<pre>
Line 4,532 ⟶ 4,570:
{{works with|Bourne Again SHell}}
 
<langsyntaxhighlight lang="bash">
#!/bin/bash
 
Line 4,905 ⟶ 4,943:
main "$@"
 
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 4,922 ⟶ 4,960:
=={{header|Wren}}==
{{trans|Sidef}}
<langsyntaxhighlight ecmascriptlang="wren">var Equals = Fn.new { |p1, p2| p1[0] == p2[0] && p1[1] == p2[1] }
 
var Contains = Fn.new { |pairs, p|
Line 5,038 ⟶ 5,076:
}
for (line in grid) System.print(line.join())
System.print("\npath cost %(cost): %(route)")</langsyntaxhighlight>
 
{{out}}
Line 5,058 ⟶ 5,096:
=={{header|zkl}}==
{{trans|Python}}
<langsyntaxhighlight lang="zkl"> // we use strings as hash keys: (x,y)-->"x,y", keys are a single pair
fcn toKey(xy){ xy.concat(",") }
 
Line 5,112 ⟶ 5,150:
} // while
throw(Exception.AssertionError("A* failed to find a solution"));
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">class [static] AStarGraph{ # Define a class board like grid with barriers
var [const] barriers =
T( T(3,2),T(4,2),T(5,2), // T is RO List
Line 5,139 ⟶ 5,177:
1 # Normal movement cost
}
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">graph:=AStarGraph;
route,cost := AStarSearch(T(0,0), T(7,7), graph);
println("Route: ", route.apply(fcn(xy){ String("(",toKey(xy),")") }).concat(","));
Line 5,150 ⟶ 5,188:
foreach x,y in (route){ grid[x][y]="+" }
grid[0][0] = "S"; grid[7][7] = "E";
foreach line in (grid){ println(line.concat()) }</langsyntaxhighlight>
{{out}}
<pre>
Alextretyak
1,453

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/273037...363359"