Implementasi Metode Hill Climbing Untuk Pencarian Rute Terpendek
Metode Hill Climbing merupakan salah satu metode yang masuk dalam kategori metode pencarian heuristik. Dinamakan Hill Climbing ( HC ) atau pendakian bukit karena mempunyai aturan produksi dengan cara menukar dua posisi kota yang saling berdekatan seperti orang yang mendaki bukit. Hill Climbing ( HC ) dibagi menjadi dua jenis yaitu Simple HC ( HC sederhana ) dan Steepest-Ascent HC ( HC dengan memilih kemiringan yang paling tajam/curam ). Untuk cara kerja Metode Hill Climbing silahkan cari referensi sendiri.
Berikut adalah contoh implementasi Metode Hill Climbing pada pemerograman PHP.
Source Code Pencarian : (mohon untuk tidak disalahgunakan)
<html>
<title>Rute Terpendek dengan Hill Climbing</title>
<head>
<link href=”letak.css” media=”all” rel=”stylesheet”>
<meta http-equiv=”Content-Type” content=”text/html; charset=utf-8″>
</head>
<body bgcolor=”#FFFFFF” leftmargin=”0″ topmargin=”0″ marginwidth=”0″ marginheight=”0″>
<div class=”proses”>
<?php
error_reporting(0);
include “koneksi.php”;
$kodeasal=$_POST[‘asal’];
$kodetujuan=$_POST[‘tujuan’];
$lp=$_POST[‘lp’];
if ($lp==0){
$lp=0;
}else{
$lp=1;
};
$hasil_akhir=array();
$i=-1;
array_push($hasil_akhir, $kodeasal);
$hr_dipilih=500;
$x=0;
$y=0;
if ($kodetujuan==$kodeasal){
echo”<script>alert(‘Masukkan tempat Asal dan Tujuan yang berbeda.’);history.go(-1);</script>”;
}else{
//Cek Jalur
while($kodeasal != $kodetujuan){
if($y==0){
$select=mysql_query(“SELECT * from jalur WHERE kode_lokasi=’$kodeasal’ ORDER BY heuristik DESC”);
}else{
$select=mysql_query(“SELECT * from jalur WHERE kode_lokasi=’$y’ ORDER BY heuristik DESC”);
};
while($aray=mysql_fetch_array($select)){
$jarak=$aray[‘heuristik’];
if($aray[‘kode_tujuan’]==$kodetujuan){
$hr_tujuan=$aray[‘heuristik’];
}
if ($jarak > $x){
$hr_dipilih=$jarak;
$kodeasal=$aray[‘kode_tujuan’];
$pilih_lokasi=$aray[‘kode_lokasi’];
if ($lp!=0){
echo “<center>Asal $pilih_lokasi | “;
echo “periksa lokasi $kodeasal – HR : $hr_dipilih<br/></center>”;
}
};
};
$hasil=$kodeasal;
$de=’CATAT’;
$y=0;
if(in_array($hasil, $hasil_akhir)){
$y=$pilih_lokasi;
$x=$hr_dipilih;
$hasil=”-“;
$de=’JANGAN CATAT’;
if ($lp!=0){
echo “<center>Lokasi $kodeasal udah dipilih, kembali ke $y dengan syarat HR > $x<br/><br/></center>”;
};
}else{
//cek HR yang dipilih
$select5=mysql_query(“SELECT * from rute WHERE kode_lokasi=’$hasil’ ORDER BY heuristik DESC”);
while ( $aray5=mysql_fetch_array($select5)) {
if ($aray5[‘kode_tujuan’]==$kodetujuan){
$hr_lanjut=$aray5[‘heuristik’];
};
};
$select6=mysql_query(“SELECT * from rute WHERE kode_lokasi=’$pilih_lokasi’ ORDER BY heuristik DESC”);
while ( $aray6=mysql_fetch_array($select6)) {
if ($aray6[‘kode_tujuan’]==$kodetujuan){
$hr_seb=$aray6[‘heuristik’];
};
};
//Periksa HR Tujuan
if ($hr_seb < $hr_lanjut){
$y=$pilih_lokasi;
$x=$hr_dipilih;
$hasil=”-“;
$de=’JANGAN CATAT’;
if ($lp!=0){
echo “<center>Lokasi dipilih $kodeasal, Karena HR terkecil <br/>Bandingkan heuristik tujuan apakah lebih kecil di lokasi $kodeasal ?<br/>($hr_lanjut lebih kecil dari $hr_seb ?)”;
echo “<br/>JAWAB : Tidak, Oke kembali ke $y, “;
echo “dengan HR > $hr_dipilih<br/><br/><br/></center>”;
};
}else{
if ($lp!=0){
echo “<center>Lokasi dipilih $kodeasal, Karena HR terkecil <br/>Bandingkan apakah heuristik tujuan lebih kecil di lokasi $kodeasal ?<br/>($hr_lanjut lebih kecil dari $hr_seb ?)”;
echo “<br/>JAWAB : Ya, Oke Lajuut periksa lokasi $kodeasal<br/><br/><br/></center>”;
};
$x=0;
};
};
if($de==’CATAT’){
$i++;
array_push($hasil_akhir, $hasil);
$total_jarak=$total_jarak+$hr_dipilih;
};
};
if ($lp!=0){
print_r($hasil_akhir);
};
};
?>
</div>
<center>
<h1>Peta Pencarian Rute Terpendek</h1>
<h3>Dengan Algorima Hill Climbing</h3>
</center>
<!– Save for Web Slices (peta.psd) –>
<table id=”Table_01″ width=”801″ height=”601″ border=”0″ cellpadding=”0″ cellspacing=”0″>
<tr>
<td colspan=”21″>
<img src=”images/2peta_01.gif” width=”800″ height=”61″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”61″ alt=””></td>
</tr>
<tr>
<td colspan=”9″ rowspan=”2″>
<img src=”images/2peta_02.gif” width=”415″ height=”103″ alt=””></td>
<td colspan=”2″>
<?php
if(in_array(10, $hasil_akhir)){
?>
<img src=”images/peta_03.gif” width=”41″ height=”50″ alt=””>
<?php }else{?>
<img src=”images/2peta_03.gif” width=”41″ height=”50″ alt=””><?php } ?></td>
<td colspan=”10″ rowspan=”2″>
<img src=”images/2peta_04.gif” width=”344″ height=”103″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”50″ alt=””></td>
</tr>
<tr>
<td colspan=”2″ rowspan=”3″>
<img src=”images/2peta_05.gif” width=”41″ height=”134″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”53″ alt=””></td>
</tr>
<tr>
<td colspan=”5″ rowspan=”4″>
<img src=”images/2peta_06.gif” width=”257″ height=”109″ alt=””></td>
<td>
<?php
if(in_array(3, $hasil_akhir)){
?>
<img src=”images/peta_07.gif” width=”54″ height=”42″ alt=””>
<?php }else{?>
<img src=”images/2peta_07.gif” width=”54″ height=”42″ alt=””><?php } ?>
</td>
<td colspan=”3″ rowspan=”10″>
<img src=”images/2peta_08.gif” width=”104″ height=”274″ alt=””></td>
<td colspan=”3″ rowspan=”2″>
<img src=”images/2peta_09.gif” width=”103″ height=”81″ alt=””></td>
<td colspan=”2″>
<?php
if(in_array(6, $hasil_akhir)){
?>
<img src=”images/peta_10.gif” width=”51″ height=”42″ alt=””>
<?php }else{?>
<img src=”images/2peta_10.gif” width=”51″ height=”42″ alt=””><?php } ?></td>
<td colspan=”5″ rowspan=”3″>
<img src=”images/2peta_11.gif” width=”190″ height=”100″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”42″ alt=””></td>
</tr>
<tr>
<td rowspan=”14″>
<img src=”images/2peta_12.gif” width=”54″ height=”394″ alt=””></td>
<td colspan=”2″ rowspan=”8″>
<img src=”images/2peta_13.gif” width=”51″ height=”192″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”39″ alt=””></td>
</tr>
<tr>
<td rowspan=”13″>
<img src=”images/2peta_14.gif” width=”31″ height=”355″ alt=””></td>
<td colspan=”2″ rowspan=”4″>
<?php
if(in_array(4, $hasil_akhir)){
?>
<img src=”images/peta_15.gif” width=”58″ height=”48″ alt=””>
<?php }else{?>
<img src=”images/2peta_15.gif” width=”58″ height=”48″ alt=””><?php };?></td>
<td colspan=”2″ rowspan=”7″>
<img src=”images/2peta_16.gif” width=”55″ height=”153″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”19″ alt=””></td>
</tr>
<tr>
<td rowspan=”12″>
<img src=”images/2peta_17.gif” width=”79″ height=”336″ alt=””></td>
<td colspan=”2″ rowspan=”4″>
<?php
if(in_array(7, $hasil_akhir)){
?>
<img src=”images/peta_18.gif” width=”42″ height=”46″ alt=””>
<?php }else{?>
<img src=”images/2peta_18.gif” width=”42″ height=”46″ alt=””><?php };?></td>
<td colspan=”2″ rowspan=”10″>
<img src=”images/2peta_19.gif” width=”69″ height=”219″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”9″ alt=””></td>
</tr>
<tr>
<td rowspan=”11″>
<img src=”images/2peta_20.gif” width=”59″ height=”327″ alt=””></td>
<td rowspan=”4″>
<?php
if(in_array(1, $hasil_akhir)){
?>
<img src=”images/peta_21.gif” width=”41″ height=”55″ alt=””>
<?php }else{?>
<img src=”images/2peta_21.gif” width=”41″ height=”55″ alt=””><?php };?></td>
<td colspan=”3″>
<img src=”images/2peta_22.gif” width=”157″ height=”4″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”4″ alt=””></td>
</tr>
<tr>
<td rowspan=”10″>
<img src=”images/2peta_23.gif” width=”62″ height=”323″ alt=””></td>
<td rowspan=”3″>
<?php
if(in_array(2, $hasil_akhir)){ ?>
<img src=”images/peta_24.gif” width=”41″ height=”51″ alt=””>
<?php }else{?>
<img src=”images/2peta_24.gif” width=”41″ height=”51″ alt=””><?php };?></td>
<td rowspan=”10″>
<img src=”images/2peta_25.gif” width=”54″ height=”323″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”16″ alt=””></td>
</tr>
<tr>
<td colspan=”2″ rowspan=”9″>
<img src=”images/2peta_26.gif” width=”58″ height=”307″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”17″ alt=””></td>
</tr>
<tr>
<td colspan=”2″ rowspan=”6″>
<img src=”images/2peta_27.gif” width=”42″ height=”173″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”18″ alt=””></td>
</tr>
<tr>
<td rowspan=”7″>
<img src=”images/2peta_28.gif” width=”41″ height=”272″ alt=””></td>
<td rowspan=”7″>
<img src=”images/2peta_29.gif” width=”41″ height=”272″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”70″ alt=””></td>
</tr>
<tr>
<td rowspan=”6″>
<img src=”images/2peta_30.gif” width=”34″ height=”202″ alt=””></td>
<td colspan=”2″ rowspan=”2″>
<?php
if(in_array(8, $hasil_akhir)){
?>
<img src=”images/peta_31.png” width=”51″ height=”47″ alt=””>
<?php }else{?>
<img src=”images/2peta_31.png” width=”51″ height=”47″ alt=””><?php };?></td>
<td rowspan=”6″>
<img src=”images/2peta_32.gif” width=”21″ height=”202″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”40″ alt=””></td>
</tr>
<tr>
<td rowspan=”5″>
<img src=”images/2peta_33.gif” width=”11″ height=”162″ alt=””></td>
<td rowspan=”2″>
<?php
if(in_array(5, $hasil_akhir)){
?>
<img src=”images/peta_34.gif” width=”45″ height=”42″ alt=””>
<?php }else{?>
<img src=”images/2peta_34.gif” width=”45″ height=”42″ alt=””><?php };?></td>
<td rowspan=”5″>
<img src=”images/2peta_35.gif” width=”48″ height=”162″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”7″ alt=””></td>
</tr>
<tr>
<td colspan=”2″ rowspan=”4″>
<img src=”images/2peta_36.gif” width=”51″ height=”155″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”35″ alt=””></td>
</tr>
<tr>
<td rowspan=”3″>
<img src=”images/2peta_37.gif” width=”45″ height=”120″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”3″ alt=””></td>
</tr>
<tr>
<td rowspan=”2″>
<img src=”images/2peta_38.gif” width=”21″ height=”117″ alt=””></td>
<td colspan=”2″>
<?php
if(in_array(9, $hasil_akhir)){
?>
<img src=”images/peta_39.gif” width=”41″ height=”48″ alt=””>
<?php }else{?>
<img src=”images/2peta_39.gif” width=”41″ height=”48″ alt=””><?php };?></td>
<td rowspan=”2″>
<img src=”images/2peta_40.gif” width=”49″ height=”117″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”48″ alt=””></td>
</tr>
<tr>
<td colspan=”2″>
<img src=”images/2peta_41.gif” width=”41″ height=”69″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”1″ height=”69″ alt=””></td>
</tr>
<tr>
<td>
<img src=”images/spacer.gif” width=”59″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”41″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”62″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”41″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”54″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”54″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”11″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”45″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”48″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”31″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”10″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”48″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”34″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”21″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”30″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”21″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”79″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”21″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”21″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”20″ height=”1″ alt=””></td>
<td>
<img src=”images/spacer.gif” width=”49″ height=”1″ alt=””></td>
<td></td>
</tr>
</table>
<center>
<div class=”tulisan”>
<h3>Rute terpendek : </h3><h3 style=”color:yellow”><?php
$e=0;
while ( $e <= ($i+1) ) {
if ($hasil_akhir[$e] == 1){
echo “Bandung -> “;
}else if ($hasil_akhir[$e] == 2){
echo “Tarogong -> “;
}else if ($hasil_akhir[$e] == 3){
echo “Terminal -> “;
}else if ($hasil_akhir[$e] == 4){
echo “Simpang Lima -> “;
}else if ($hasil_akhir[$e] == 5){
echo “Samarang -> “;
}else if ($hasil_akhir[$e] == 6){
echo “Karangpawitan -> “;
}else if ($hasil_akhir[$e] == 7){
echo “Wanaraja -> “;
}else if ($hasil_akhir[$e] == 8){
echo “Bayongbong -> “;
}else if ($hasil_akhir[$e] == 9){
echo “Malangbong -> “;
}else if ($hasil_akhir[$e] == 10){
echo “Sucinaraja -> “;
}
$e++;
};?></h3>
<h3>Total Perkiraan Jarak : <?php echo $total_jarak;?> KM</h3>
</div>
<form name=”rute1″ action=”2peta.php” method=”POST”>
<p>Tempat Asal:</p>
<span class=”css3-metro-dropdown css3-metro-dropdown-color-2673ec”>
<?php
$pilih_asal=mysql_query(“SELECT * from rute GROUP BY kode_lokasi ORDER BY nama_lokasi ASC”);
?>
<select type=”text” name=”asal”>
<?php while($data=mysql_fetch_array($pilih_asal)){ ?>
<option value=”<?php echo $data[‘kode_lokasi’]?>”><?php echo $data[‘nama_lokasi’]?>( <?php echo $data[‘kode_lokasi’]?>)</option>
<?php }; ?>
</select>
</span>
<p>Tempat Tujuan:</p>
<span class=”css3-metro-dropdown css3-metro-dropdown-color-2673ec”>
<select type=”text” name=”tujuan”>
<?php
$pilih_asal2=mysql_query(“SELECT * from rute GROUP BY kode_lokasi ORDER BY nama_lokasi ASC”);
while($data_tujuan=mysql_fetch_array($pilih_asal2)){ ?>
<option value=”<?php echo $data_tujuan[‘kode_lokasi’]?>”><?php echo $data_tujuan[‘nama_lokasi’]?>( <?php echo $data_tujuan[‘kode_lokasi’]?>)</option>
<?php }; ?>
</select>
</span><br/>
<p>Tampilkan Proses?</p>
<span class=”css3-metro-dropdown css3-metro-dropdown-color-2673ec”>
<select type=”text” name=”lp”>
<option value=”0″>Tidak</option>
<option value=”1″>Ya</option>
</select>
</span><br/>
<input type=”submit” name=”submit” value=”Cek Rute”>
</form>
</center>
</body>
</html>
A big thank you for your blog. Really Cool.
Ini satu file ? Atau di bagi lagi ?
Ini satu file ? Atau ada tambahan lagi?
boleh minta source code yang lengkap