PHP : Penyelesaian Traveling Salesman Problem (TSP) Menggunakan Algoritma Recursive Best First Search (RBFS) - Elang Sakti
Download Ebook Belajar Arduino PDF, Arduino untuk pemula
Jasa Pembuatan Program Arduino, pemrograman Arduino
# Hack Your Skills! to be Professional Mechatronics

PHP : Penyelesaian Traveling Salesman Problem (TSP) Menggunakan Algoritma Recursive Best First Search (RBFS)

1 komentar
Tulisan ini adalah salah satu tugas Kecerdasan Komputasional.

ABSTRAK

Travelling Salesman Problem (TSP) merupakan sebuah permasalahan optimasi yang dapat diterapkan pada berbagai kegiatan seperti routing. Masalah optimasi TSP terkenal dan telah menjadi standar untuk mencoba algoritma yang komputational. Pokok permasalahan dari TSP adalah seorang salesman harus mengunjungi sejumlah kota yang diketahui jaraknya satu dengan yang lainnya. Semua kota yang ada harus dikunjungi oleh salesman tersebut dan kota tersebut hanya boleh dikunjungi tepat satu kali. Permasalahannya adalah bagaimana salesman tersebut dapat mengatur rute perjalanannya sehingga jarak yang ditempuhnya merupakan rute yang optimum yaitu jarak minimum terbaik. Dalam makalah ini penyelesaian kasus TSP diselesaikan dengan algoritma Recursive Best First Search (RBFS).

A. LATAR BELAKANG MASALAH

Travelling Salesman Problem (TSP) merupakan permasalahan pedagang keliling dalam mencari lintasan terpendek dari semua kota yang dikunjunginya. Dengan syarat kota tersebut hanya boleh dikunjungi satu kali. Banyak permasalahan yang dapat direpresentasikan dalam bentuk Travelling Salesman Problem. Persoalan ini sendiri menggunakan representasi graf untuk memodelkan persolan yang diwakili sehingga lebih memudahkan penyelesaiannya. Diantaranya permasalahan yang dapat direpresentasikan dengan TSP ialah masalah transportasi, efisiensi pengiriman surat atau barang, perancangan pemasangan pipa saluran, proses pembuatan PCB (Printed Circuit Board) dan lain–lain.

Ada beberapa algoritma dan metode yang bisa menyelesaikan TSP ini, antara lain: algoritma Brute Force dengan complete Enumeration, algoritma Branch and Bound, Greedy Heuristik. Dalam Algoritma Bruto Force, hal yang dilakukan ialah dengan cara mengenumerasi seluruh kemungkinan rute yang akan ditempuh. Setelah itu, akan dibandingkan dari seluruh kemungkinan rute yang telah dienumerasi tersebut, rute mana yang memiliki lintasan/bobot yang paling minimum. Namun, jumlah enumerasi dari algoritma ini ialah (n-1)! Yang akan memerlukan waktu yang sangat lama untuk mendapatkan panjang lintasan paling minimum jika n bernilai sangat besar. Seperti Algoritma Brute Force yang mengenumerasi satu per satu kemungkinan jalur yang akan ditempuh, Algoritma Branch and bound ternyata tidak memiliki kompleksitas waktu yang lebih baik dimana algoritma ini juga memilki kompleksitas waktu (n-1)! Dan sangat membutuhkan waktu yang sangat lama untuk mendapatkan panjang lintasan paling minimum jika n bernilai sangat besar.

Sedangkan pada greedy heuristik, pemilihan lintasan akan dimulai pada lintasan yang memilki nilai paling minimum, algoritma ini akan memilih kota selanjutnya yang belum dikunjungi yang mempunyai bobot paling minimum/kota terdekat sampai swmua kota tersebut dikunjungi dan kemudian kembali ke kota awal, tetapi hasil yang didapat bisa sangat jauh dari hasil optimal, semakin banyak kota yang dikunjungi semakin besar pula perbedaan yang dicapai.

Algoritma Heuristik merupakan salah satu algoritma alternatif yang dapat digunakan sebab prosesnya cepat dan memberikan hasil yang diinginkan. Algoritma Heuristik adalah algoritma yang mencari solusi terbaik untuk kasus yang merupakan bagian atau irisan dari permasalahan total dengan harapan dapat menghasilkan solusi optimal untuk keseluruhan kasus melalui proses tambahan, yaitu mencari bobot minimum dengan menggunakan Recursive Best First Search (RBFS) sehingga menghasilkan routing dari graf yang memiliki nilai optimal. Permasalahan pada makalah ini bisa dilihat pada Gambar 1, yaitu mencari jarak terpendek terbaik yang bisa ditempuh oleh sales dan setiap kota hanya boleh dikunjungi satu kali.

Gambar 1. Peta jalur antar kota yang harus dilewati oleh sales
Gambar 1. Peta jalur antar kota yang harus dilewati oleh sales

B. RECURSIVE BEST-FIRST SEARCH (RBFS)

Recursive Best-First Search merupakan algoritma pencarian terbimbing yang mirip dengan algoritma standar Best First Search yang bersifat linear. Desain algoritmanya juga mirip dengan Depth-First Search walaupun dengan model yang sangat berbeda.

Cara kerja RBFS yaitu tetap memperhatikan jalur teratas, kalau misalkan pada tree, maka tree paling atas. Apabila ada jalur yang tidak sesuai, maka jalur teratas akan langsung mengubahnya. Pada saat operasi, setiap operasi yang akan dipilih adalah jalur yang terpendek, dan setiap ada jalur baru, maka jalur teratas akan diurutkan berdasarkan nilai cost yang terkecil.

Hal tersebut akan dilakukan hingga titik akhir adalah jalur yang dituju dan cost yang ditemukan pada jalur terakhir ini lebih kecil dari jalur-jalur yang sudah dilewati sebelumnya. Berikut ini adalah presudocode algoritma untuk RBFS.




C. PEMODELAN

Gambar 2. merupakan representasi bentuk pohon dari peta jalur antar kota yang akan dicari solusinya. Garis putus-putus menunjukkan bahwa jalur yang bisa menjadi solusi adalah jalur yang melewati seluruh kota dan tepat satu kali untuk masing-masing kota. Sedangkan jarak antar kota berdasarkan jalur yang ada pata peta dapat dilihat pada tabel 1.

Gambar 2. Representasi jalur antar kota dalam kasus TSP
Gambar 2. Representasi jalur antar kota dalam kasus TSP


Tabel 1. Tabel jarak antar kota (dalam km)
Tabel 1. Tabel jarak antar kota (dalam km)
Berdasarkan pohon pada Gambar 2, maka proses pencarian RBFS akan dilakukan dengan cara membandingkan setiap simpul yang dilewati dan dicari simpul yang memiliki cost atau jarak yang paling kecil sesuai dengan algoritma pada RBFS. Proses perhitungan untuk menemukan jalur terpendek dengan metode RBFS akan dijelaskan secara singkat seperti pada Tabel 2.

Pada step pertama, hitung jalur asal dengan jalur yang mungkin untuk dilewati. Jalur yang mungkin hanya Bandung (270km) dan Cirebon (327km). Urutkan jarak tersebut berdasarkan yang terpendek. jarak yang terpendek akan dipilih untuk menghitung jarak selanjutnya, sedangkan jarak terpendek kedua akan dijadikan treshold atau patokan untuk dihitung apabila hasil dari jalur yang dibuka dari jarak terpendek lebih besar daripada jarak jalur kedua tersebut. Pada step awal, jarak minimal adalah Jakarta-Bandung, dan yang menjadi treshold adalah jarak Jakarta-Cirebon.

Step kedua yang dibuka adalah jalur Jakarta-Bandung. Kemungkinan yang bisa dilewati adalah jalur Jakarta-Bandung-Cirebon (390km) dan Jakarta-Bandung-Yogyakarta (643). Selanjutnya jarak-jarak tersebut dibandingkan dan dipilih jalur terpendek. Jalur yang terpendek adalah Jakarta-Cirebon dan jalur terpendek kedua adalah Jakarta-Bandung-Cirebon. Sehingga jalur yang akan dibuka selanjutnya adalah jalur Jakarta-Cirebon dan yang menjadi treshold adalah jalur Jakarta-Bandung-Cirebon. Begitu seterusnya hingga didapatkan jarak terpendek untuk menghubungkan semua kota.

Tabel 2. Step-step pencarian algoritma RBFS
Tabel 2. Step-step pencarian algoritma RBFS

D. IMPLEMENTASI METODE

Model komputasi algoritma untuk menyelesaikan kasus TSP dengan RBFS yaitu dibuat dengan bahasa pemrograman PHP . Hal yang pertama dilakukan adalah pemetaan kota dan jarak antar kota. Peta dibuat dalam bentuk array objek dimana untuk masing-masing kota berisi ID kota, Nama kota, jalur yang mungkin dilalui sekaligus jarak antara kota denga jalur tersebut. Pada source code representasi peta dalam bahsa pemrograman menunjukkan kota Jakarta dan kota Bandung. Kota jakarta memiliki id ‘jkt’ dan jalur yang mungkin dilalui adalah Jakarta-Bandung (bdg) dengan jarak 270 km dan Jakarta-Cirebon (crb) dengan jarak 327 km. Sedangkan kota Bandung, jalur yang mungkin dilewati adalah Bandung-Cirebon (crb) dengan jarak 120 km dan Bandung-Yogyakarta (ygy) dengan jarak 373 km.

Representasi peta dalam bahasa pemrograman
$peta = array(
  'jkt' => (object)array(
      'id'   => 'jkt',
      'name' => 'Jakarta',
      'path' => array(
          'bdg' => 270,
          'crb' => 327
          )
      ),
  'bdg' => (object)array(
      'id'   => 'bdg',
      'name' => 'Bandung',
      'path' => array(
          'crb' => 120,
          'ygy' => 373
          )
      ),
  'crb' => (object)array(
      'id'   => 'crb',
      'name' => 'Cirebon',
      'path' => array(
          'smg' => 305,
          'ygy' => 210
          )
      ),
  'smg' => (object)array(
      'id'   => 'smg',
      'name' => 'Semarang',
      'path' => array(
          'ygy' => 109,
          'srkt' => 97,
          'sby' => 365
          )
      ),
  'ygy' => (object)array(
      'id'   => 'ygy',
      'name' => 'Yogyakarta',
      'path' => array(
          'srkt' => 60
          )
      ),
  'srkt' => (object)array(
      'id'   => 'srkt',
      'name' => 'Surakarta',
      'path' => array(
          'mlg' => 370
          )
      ),
  'sby' => (object)array(
      'id'   => 'sby',
      'name' => 'Surabaya',
      'path' => array(
          'mlg' => 94
          )
      ),
  'mlg' => (object)array(
      'id'   => 'mlg',
      'name' => 'Malang',
      'path' => array()
      )
  );

Dalam proses pencarian, peta tersebut ‘dibaca’ dengan fungsi possible() untuk mengetahui kemungkinan jalur yang akan dilalui dari suatu kota. Fungsi possible() tampak pada Source Code Fungsi possible() , inputnya adalah id kota, dan ouputnya adalah daftar kota yang mungkin dilalui. Pada kode tersebut dilalukan perulangan pada peta dan mencari jalur yang mungkin untuk kota dengan id yang cocok.

Source Code Fungsi possible() 
function possible($kota){
    $ret = array();
    foreach($this->peta as $next){
        foreach($next->path as $key=>$target){
            $tmp = array();
            if($next->id == $kota){
                    $tmp['id']  = $key;
                    $tmp['len'] = $target;
                    array_push($ret,$tmp);
            }else{
                if($key == $kota){
                    $tmp['id']  = $next->id;
                    $tmp['len'] = $next->path[$kota];
                    array_push($ret,$tmp);
                }
            }
        }
    }
    return $ret;
}

Fungsi utama untuk RBFS ada pada fungsi route(). Fungsi route() membutuhkan input kota yang sedang dibuka (di-expand / open) dan menghasilkan jalur dengan cost yang minimal dan jalur yang akan dijadikan backup / treshold. Source code Potongan fungsi route() untuk menghitung path merupakan potongan source code untuk fungsi route(). Pertama akan dicari jalur yang mungkin dilewati dengan pemanggilan fungsi possible(). Setelah itu daftar jalur yang akan dilewati akan dihitung satu-persatu dengan perulangan. Masing-masing jalur akan dihitung besar cost dari jalur awal yaitu pada variabel $tmp[lenmin].

Potongan fungsi route() untuk menghitung path
function route($start){
    $next = $this->possible($start['id']);
    
    $lastone = true;
    foreach($next as $nxt){
        
        $chkpath = $start['path'].'-'.$nxt['id'];
        $chkp = explode('-',$chkpath);
        
        if(!strpos('x'.$start['path'],$nxt['id']) || ($chkp[0]==$nxt['id'] && sizeof($chkp)==sizeof($this->peta)+1)){
            $tmp = $nxt;
            if($start['path']==''){
                $tmp['lenmin'] = $nxt['len'];
                $tmp['path']   = $start['id'].'-'.$tmp['id'];
            }else{
                $tmp['lenmin'] = $start['lenmin'] + $nxt['len'];
                $tmp['path']   = $start['path'].'-'.$tmp['id'];
            }
            array_push($this->routing, $tmp);
            $lastone = false;
        }
    }
    
    usort($this->routing,function($a,$b){ return $a['lenmin'] - $b['lenmin']; });

    $open = $this->routing[0];
    $back = $this->routing[1];
    
    if($open['path']){
        $tmp = array();
        $tmp['path'] = $this->KOTA($open['path']);
        $tmp['cost'] = $open['lenmin'];
        array_push($this->result, $tmp);
    }
    
    if($open['path']!=''){
        unset($this->routing[0]);
        $this->route($open);
    }
}


Setelah masing-masing cost dihitung, maka semua kemungkinan jalur yang ada akan diurutkan berdasarkan cost yang terkecil dengan fungsi usort(). Seletah diurutkan, makan jalur dengan cost terkecil akan dibuka (variabel $open) dan jalur terkecil kedua akan dijadikan treshold untuk perbandingan (variabel $back). Selanjutnya pembukaan jalur baru dilakukan pada bagian $this->route($open).

Gambar 7. adalah hasil eksekusi program ketika dijalankan. Jika memilih jalur awal adalah Jakarta, maka sistem membutuhkan 107 kali perulangan dengan jalur terbaik Jakarta-Cirebon-Semarang-Surabaya-Malang-Surakarta-Yogyakarta-Bandung-Jakarta dengan jarak yang ditempuh 2164 km atau sebaliknya. Step-step pencarian jalur yang lengkap bisa dilihat pada tabel 3.

Gambar 7. Hasil eksekusi program tsp
Gambar 7. Hasil eksekusi program

Tabel 3. Step-step pencarian jalur terpendek dengan kota awal Jakarta

Step Rute Cost
1 Jakarta-Bandung 270
2 Jakarta-Cirebon 327
3 Jakarta-Bandung-Cirebon 390
4 Jakarta-Cirebon-Bandung 447
5 Jakarta-Cirebon-Yogyakarta 537
6 Jakarta-Cirebon-Yogyakarta-Surakarta 597
7 Jakarta-Bandung-Cirebon-Yogyakarta 600
8 Jakarta-Cirebon-Semarang 632
9 Jakarta-Bandung-Yogyakarta 643
10 Jakarta-Cirebon-Yogyakarta-Semarang 646
11 Jakarta-Bandung-Cirebon-Yogyakarta-Surakarta 660
12 Jakarta-Cirebon-Yogyakarta-Surakarta-Semarang 694
13 Jakarta-Bandung-Cirebon-Semarang 695
14 Jakarta-Bandung-Yogyakarta-Surakarta 703
15 Jakarta-Bandung-Cirebon-Yogyakarta-Semarang 709
16 Jakarta-Cirebon-Semarang-Surakarta 729
17 Jakarta-Cirebon-Semarang-Yogyakarta 741
18 Jakarta-Cirebon-Yogyakarta-Semarang-Surakarta 743
19 Jakarta-Bandung-Yogyakarta-Semarang 752
20 Jakarta-Bandung-Cirebon-Yogyakarta-Surakarta-Semarang 757
21 Jakarta-Cirebon-Semarang-Surakarta-Yogyakarta 789
22 Jakarta-Bandung-Cirebon-Semarang-Surakarta 792
23 Jakarta-Bandung-Yogyakarta-Surakarta-Semarang 800
24 Jakarta-Cirebon-Semarang-Yogyakarta-Surakarta 801
25 Jakarta-Bandung-Cirebon-Semarang-Yogyakarta 804
26 Jakarta-Bandung-Cirebon-Yogyakarta-Semarang-Surakarta 806
27 Jakarta-Cirebon-Bandung-Yogyakarta 820
28 Jakarta-Bandung-Yogyakarta-Semarang-Surakarta 849
29 Jakarta-Bandung-Cirebon-Semarang-Surakarta-Yogyakarta 852
30 Jakarta-Bandung-Yogyakarta-Cirebon 853
31 Jakarta-Bandung-Cirebon-Semarang-Yogyakarta-Surakarta 864
32 Jakarta-Cirebon-Bandung-Yogyakarta-Surakarta 880
33 Jakarta-Cirebon-Yogyakarta-Bandung 910
34 Jakarta-Cirebon-Bandung-Yogyakarta-Semarang 929
35 Jakarta-Cirebon-Yogyakarta-Surakarta-Malang 967
36 Jakarta-Cirebon-Bandung-Yogyakarta-Surakarta-Semarang 977
37 Jakarta-Cirebon-Semarang-Surabaya 997
38 Jakarta-Cirebon-Yogyakarta-Semarang-Surabaya 1011
39 Jakarta-Cirebon-Bandung-Yogyakarta-Semarang-Surakarta 1026
40 Jakarta-Bandung-Cirebon-Yogyakarta-Surakarta-Malang 1030
41 Jakarta-Bandung-Yogyakarta-Semarang-Cirebon 1057
42 Jakarta-Cirebon-Yogyakarta-Surakarta-Semarang-Surabaya 1059
43 Jakarta-Bandung-Cirebon-Semarang-Surabaya 1060
44 Jakarta-Cirebon-Yogyakarta-Surakarta-Malang-Surabaya 1061
45 Jakarta-Bandung-Yogyakarta-Surakarta-Malang 1073
46 Jakarta-Bandung-Cirebon-Yogyakarta-Semarang-Surabaya 1074
47 Jakarta-Cirebon-Semarang-Surabaya-Malang 1091
48 Jakarta-Cirebon-Semarang-Surakarta-Malang 1099
49 Jakarta-Cirebon-Yogyakarta-Semarang-Surabaya-Malang 1105
50 Jakarta-Bandung-Yogyakarta-Surakarta-Semarang-Cirebon 1105
51 Jakarta-Cirebon-Yogyakarta-Semarang-Surakarta-Malang 1113
52 Jakarta-Cirebon-Semarang-Yogyakarta-Bandung 1114
53 Jakarta-Bandung-Yogyakarta-Semarang-Surabaya 1117
54 Jakarta-Bandung-Cirebon-Yogyakarta-Surakarta-Semarang-Surabaya 1122
55 Jakarta-Bandung-Cirebon-Yogyakarta-Surakarta-Malang-Surabaya 1124
56 Jakarta-Cirebon-Yogyakarta-Surakarta-Semarang-Surabaya-Malang 1153
57 Jakarta-Bandung-Cirebon-Semarang-Surabaya-Malang 1154
58 Jakarta-Bandung-Yogyakarta-Cirebon-Semarang 1158
59 Jakarta-Cirebon-Semarang-Surakarta-Yogyakarta-Bandung 1162
60 Jakarta-Bandung-Cirebon-Semarang-Surakarta-Malang 1162
61 Jakarta-Bandung-Yogyakarta-Surakarta-Semarang-Surabaya 1165
62 Jakarta-Bandung-Yogyakarta-Surakarta-Malang-Surabaya 1167
63 Jakarta-Bandung-Cirebon-Yogyakarta-Semarang-Surabaya-Malang 1168
64 Jakarta-Cirebon-Semarang-Yogyakarta-Surakarta-Malang 1171
65 Jakarta-Bandung-Cirebon-Yogyakarta-Semarang-Surakarta-Malang 1176
66 Jakarta-Cirebon-Semarang-Surakarta-Malang-Surabaya 1193
67 Jakarta-Cirebon-Yogyakarta-Semarang-Surakarta-Malang-Surabaya 1207
68 Jakarta-Bandung-Yogyakarta-Semarang-Surabaya-Malang 1211
69 Jakarta-Bandung-Cirebon-Yogyakarta-Surakarta-Semarang-Surabaya-Malang 1216
70 Jakarta-Bandung-Yogyakarta-Semarang-Surakarta-Malang 1219
71 Jakarta-Bandung-Cirebon-Semarang-Yogyakarta-Surakarta-Malang 1234
72 Jakarta-Cirebon-Bandung-Yogyakarta-Surakarta-Malang 1250
73 Jakarta-Bandung-Yogyakarta-Cirebon-Semarang-Surakarta 1255
74 Jakarta-Bandung-Cirebon-Semarang-Surakarta-Malang-Surabaya 1256
75 Jakarta-Bandung-Yogyakarta-Surakarta-Semarang-Surabaya-Malang 1259
76 Jakarta-Cirebon-Semarang-Yogyakarta-Surakarta-Malang-Surabaya 1265
77 Jakarta-Bandung-Cirebon-Yogyakarta-Semarang-Surakarta-Malang-Surabaya 1270
78 Jakarta-Cirebon-Bandung-Yogyakarta-Semarang-Surabaya 1294
79 Jakarta-Bandung-Yogyakarta-Semarang-Surakarta-Malang-Surabaya 1313
80 Jakarta-Bandung-Cirebon-Semarang-Yogyakarta-Surakarta-Malang-Surabaya 1328
81 Jakarta-Cirebon-Bandung-Yogyakarta-Surakarta-Semarang-Surabaya 1342
82 Jakarta-Cirebon-Bandung-Yogyakarta-Surakarta-Malang-Surabaya 1344
83 Jakarta-Cirebon-Bandung-Yogyakarta-Semarang-Surabaya-Malang 1388
84 Jakarta-Cirebon-Bandung-Yogyakarta-Semarang-Surakarta-Malang 1396
85 Jakarta-Cirebon-Yogyakarta-Surakarta-Malang-Surabaya-Semarang 1426
86 Jakarta-Cirebon-Bandung-Yogyakarta-Surakarta-Semarang-Surabaya-Malang 1436
87 Jakarta-Cirebon-Semarang-Surabaya-Malang-Surakarta 1461
88 Jakarta-Cirebon-Yogyakarta-Semarang-Surabaya-Malang-Surakarta 1475
89 Jakarta-Bandung-Cirebon-Yogyakarta-Surakarta-Malang-Surabaya-Semarang 1489
90 Jakarta-Cirebon-Bandung-Yogyakarta-Semarang-Surakarta-Malang-Surabaya 1490
91 Jakarta-Cirebon-Semarang-Surabaya-Malang-Surakarta-Yogyakarta 1521
92 Jakarta-Bandung-Yogyakarta-Cirebon-Semarang-Surabaya 1523
93 Jakarta-Bandung-Cirebon-Semarang-Surabaya-Malang-Surakarta 1524
94 Jakarta-Bandung-Yogyakarta-Surakarta-Malang-Surabaya-Semarang 1532
95 Jakarta-Bandung-Cirebon-Yogyakarta-Semarang-Surabaya-Malang-Surakarta 1538
96 Jakarta-Bandung-Yogyakarta-Semarang-Surabaya-Malang-Surakarta 1581
97 Jakarta-Bandung-Cirebon-Semarang-Surabaya-Malang-Surakarta-Yogyakarta 1584
98 Jakarta-Bandung-Yogyakarta-Cirebon-Semarang-Surabaya-Malang 1617
99 Jakarta-Bandung-Yogyakarta-Cirebon-Semarang-Surakarta-Malang 1625
100 Jakarta-Cirebon-Bandung-Yogyakarta-Surakarta-Malang-Surabaya-Semarang 1709
101 Jakarta-Bandung-Yogyakarta-Cirebon-Semarang-Surakarta-Malang-Surabaya 1719
102 Jakarta-Cirebon-Bandung-Yogyakarta-Semarang-Surabaya-Malang-Surakarta 1758
103 Jakarta-Bandung-Yogyakarta-Surakarta-Malang-Surabaya-Semarang-Cirebon 1837
104 Jakarta-Cirebon-Semarang-Surabaya-Malang-Surakarta-Yogyakarta-Bandung 1894
105 Jakarta-Bandung-Yogyakarta-Cirebon-Semarang-Surabaya-Malang-Surakarta 1987
106 Jakarta-Bandung-Yogyakarta-Surakarta-Malang-Surabaya-Semarang-Cirebon-Jakarta 2164
107 Jakarta-Cirebon-Semarang-Surabaya-Malang-Surakarta-Yogyakarta-Bandung-Jakarta 2164

E. KESIMPULAN

Penggunaan RBFS dalam mencari rute terpendek terbaik untuk kasus ini dengan kota asala Jakarta adalah jalur :
Jakarta – Cirebon – Semarang – Surabaya – Malang – Surakarta – Yogyakarta – Bandung - Jakarta
atau jalur sebaliknya dengan pangjang rute adalah 2164 km. Sampel aplikasi bisa diakses di alamat http://lab.elangsakti.com/tsp/ .

F. REFERENSI

Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
Russell, S. J., Norvig, P, Artificial Intelligence: A Modern Approach, 2003.


Source Code lengkap Class RBFS:

<?php
class TSP{
    var $peta = array();
    var $routing = array();
    var $result = array();
    
    function start( $kota ){
        $start = array('id'=>$kota, 'path'=>'');
        $this->route($start);
        return $this->result;
    }
    
    function setPeta($peta){
        $this->peta = $peta;
    }
    
    function possible($kota){
        $ret = array();
        foreach($this->peta as $next){
            foreach($next->path as $key=>$target){
                $tmp = array();
                if($next->id == $kota){
                        $tmp['id']  = $key;
                        $tmp['len'] = $target;
                        array_push($ret,$tmp);
                }else{
                    if($key == $kota){
                        $tmp['id']  = $next->id;
                        $tmp['len'] = $next->path[$kota];
                        array_push($ret,$tmp);
                    }
                }
            }
        }
        return $ret;
    }
    
    function route($start){
        $next = $this->possible($start['id']);
        
        $lastone = true;
        foreach($next as $nxt){
            
            $chkpath = $start['path'].'-'.$nxt['id'];
            $chkp = explode('-',$chkpath);
            
            if(!strpos('x'.$start['path'],$nxt['id']) || ($chkp[0]==$nxt['id'] && sizeof($chkp)==sizeof($this->peta)+1)){
                $tmp = $nxt;
                if($start['path']==''){
                    $tmp['lenmin'] = $nxt['len'];
                    $tmp['path']   = $start['id'].'-'.$tmp['id'];
                }else{
                    $tmp['lenmin'] = $start['lenmin'] + $nxt['len'];
                    $tmp['path']   = $start['path'].'-'.$tmp['id'];
                }
                array_push($this->routing, $tmp);
                $lastone = false;
            }
        }
        
        usort($this->routing,function($a,$b){ return $a['lenmin'] - $b['lenmin']; });
    
        $open = $this->routing[0];
        $back = $this->routing[1];
        
        if($open['path']){
            $tmp = array();
            $tmp['path'] = $this->KOTA($open['path']);
            $tmp['cost'] = $open['lenmin'];
            array_push($this->result, $tmp);
        }
        
        if($open['path']!=''){
            unset($this->routing[0]);
            $this->route($open);
        }
    }
    
    function KOTA( $path ){
        foreach($this->peta as $kota){
            $path = str_replace($kota->id,$kota->name,$path);
        }
        return $path;
    }
}
?>



Written by Hari Santoso
PHP : Penyelesaian Traveling Salesman Problem (TSP) Menggunakan Algoritma Recursive Best First Search (RBFS)
Bahasan: Tulisan ini adalah salah satu tugas Kecerdasan Komputasional. ABSTRAK Travelling Salesman ...
Published at Sabtu, 18 Juli 2015, Updated at Sabtu, 18 Juli 2015
Reviewed by dr. on
Rating: 4.7

1 komentar :