Implementasi metode A Search Untuk Pencarian Rute Terpendek pada Aplikasi PHP
A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it builds up a treeof partial paths. The leaves of this tree (called the open set or fringe) are stored in a priority queue that orders the leaf nodes by a cost function, which combines a heuristicestimate of the cost to reach a goal and the distance traveled from the initial node. Specifically, the cost function is
.
.Here, g(n) is the known cost of getting from the initial node to n; this value is tracked by the algorithm. h(n) is a heuristic estimate of the cost to get from n to any goal node. For the algorithm to find the actual shortest path, the heuristic function must be admissible, meaning that it never overestimates the actual cost to get to the nearest goal node. The heuristic function is problem-specific and must be provided by the user of the algorithm.
For example, in an application like routing, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points.
If the heuristic h satisfies the additional condition h(x) ≤ d(x, y) + h(y) for every edge (x, y) of the graph (where d denotes the length of that edge), then h is called monotone, or consistent. In such a case, A* can be implemented more efficiently—roughly speaking, no node needs to be processed more than once (see closed set below)—and A* is equivalent to running Dijkstra’s algorithm with the reduced cost d’(x, y) = d(x, y) + h(y) − h(x).
(Wikipedia)
Source Code A* Search in PHP Programming :
This Program created by M Luthfi Channari SK-36-02 Telkom University
<html>
<head>
<style>
#header {
background-color:black;
color:white;
text-align:center;
padding:5px;
}
#footer {
background-color:black;
color:white;
clear:both;
text-align:center;
padding:5px;
}
</style>
</head>
<body>
<div id=”header”>
<h1> Hasil Penelusuran</h1>
</div>
<img src=”map.jpg” alt=”mapkota” width=”888″ height=”498″>
<form name=”form1″ method=”get” action=”hasil_cari.php” style=”width: 300px;”>
<input type=”text” name=”asal” placeholder=”masukkan tempat awal…” style=”padding:8px 15px;
background:rgba(50, 50, 50, 0.2);
border:0px solid #dbdbdb;”/>
<input id=”tombol” type=”submit” name=”Submit” value=”Cari rute” style=”position:relative;
padding:5px 15px;
left:-8px;
border:2px solid #207cca;
background-color:#207cca;
color:#fafafa;”/>
</form>
<br>
<br>
<?php
error_reporting(0);
$tempatasal=$_GET[‘asal’]; //ambil asal
$tujuanakhir=’rumah’; //tujuan akhir = rumah
include “koneksi.php”;
$data_array=array(); // jika mengetikan $data_array maka jalankan method array
array_push($data_array, $tempatasal);
$hasilgn=0;
$gntotal=0;
$fn2=500;// pendeklarasian pertama untuk pembanding
$x=0; // pendeklarasian pertama untuk pembanding
$y=’kosong’; //pendeklarasian pertama untuk pembanding
while($tujuanakhir!=$y){ // ketika tujuan akhir tidak samadengan rumah maka jalankan
if ($y==’kosong’){ //untuk pembanding state pertama
$select=mysql_query(“SELECT * from ai WHERE tempat1=’$tempatasal’ order by h_n ASC”);// pengambilan pertama
}else{
$select=mysql_query(“SELECT * from ai WHERE tempat1=’$y’ order by h_n ASC”);// untuk tempat baru yg udah diproses
}
while($ambil=mysql_fetch_array($select)){
$tujuan=$ambil[‘tempat2’]; //untuk next state ngambil dari tempat2
$hntujuan=$ambil[‘h_n’]; // ngambil hn dari tabel
$gntujuan=$ambil[‘g_n’]; //ngambil gn dari tabel
$fn=$hntujuan+$gntujuan; // hn+gn=fn
if(($fn+$gntotal) < $fn2){ // pembanding fn
$fn2=$fn+$gntotal; //ganti fn baru ke fn2
echo “Jarak dipilih: <br/>”;
echo “$fn2<br/>”;
$hasilgn=$gntujuan; //ganti hasil gn baru
$hasiltujuan=$tujuan; //ganti hasil tempat baru yg diambil
};
};
$gntotal=$gntotal+$hasilgn;
$y=$hasiltujuan; //untuk loop
array_push($data_array, $hasiltujuan);// untuk memasukan data ke dalam aray
$x++; // fungsi untuk menghitung array x+1
};
echo”<center>”;
echo”Rute terpendek yang dilewati adalah : “;
$z=0;
while ($z <= $x) {
print_r($data_array[$z]);
echo” “;
?> <tr>
<?php
$z++;
};
?>
<br>
<br><div id=”footer”>
Creator by Andi & Luthfi
</div>
Major thanks for the blog post.Much thanks again. Awesome.
Ini satu file kang ? Atau di bagi lagi kode nya ?
mohon maaf, saya ingin bertanya. apakah kita perlu membuat database lagi?