IMPLEMENTASI ALGORITMA A-STAR DALAM PENCARIAN RUTE TERPENDEK

 

IMPLEMENTASI ALGORITMA A-STAR DALAM PENCARIAN RUTE TERPENDEK

Algoritma A-Star merupakan gabungan antara algoritma pencarian Uniform Cost dan Greedy-Best First. Salah satu implementasi dari algoritma A-Star digunakan untuk mencari jalur tercepat. Pada penelitian ini algoritma A-Star digunakan untuk mencari jalur tercepat atau rute terpendek.

Di Dalam kecerdasan buatan sebuah software atau hardware disebut cerdas ketika memiliki kemampuan untuk melakukan searching, reasoning, planning dan learning.

1.      searching

Searching (pencarian) merupakan proses yang fundamental dalam pengolahan data. Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe data sama (baik bertipe dasar atau bertipe bentukan sebagai contoh untuk melakukan update (perubahan) data tertentu. Searching di bagi menjadi dua bagian yaitu Blind Searching dan Heuristik Searching

a.       Blind Searching

Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki informasi awal, Blind Searching sendiri dibagi menjadi tiga macam yaitu :

-   BFS (Breadth First Search)

-   DFS (Depth-first Search)

-   UCS (Uniform Cost Search)

b.      Heuristik Searching

    Pencarian buta tidak selalu dapat diterapkan dengan baik, hal ini disebabkan waktu aksesnya yang cukup lama & besarnya memori yang diperlukan. Untuk masalah dengan ruang masalah yang besar, teknik pencarian buta bukan metode yang baik karena keterbatasan kecepatan komputer dan memori. Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan -> disebut fungsi heuristic Aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine.

2.      Reasoning

teknik yang digunakan untuk melakukan penalaran terhadap sebuah masalah yang dialami manusia. di dalam teknik ini, pengetahuan menjadi basis utamanya.

Contoh : 

Software permainan catur yang disebut HITECH adalah system KB pertama 

yang berhasil mengalahkan grandmaster dunia, Arnold Danker. 

3.      Planning

Metode penyelesaian masalah dengan cara memecah masalah ke dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadi sebuah solusi lengkap dengan tetap mengingat dan menangani interaksi yang ada antar sub masalah.

 

4.      Learning

Learning ini digunakan untuk membuat mesin-mesin otomatis melalui proses pembelajaran dan pelatihan sedemikian rupa, sehingga bisa menjadi cerdas layaknya seorang manusia. Learning ini  telah diterapkan pada berbagai bidang yaitu transportasi, speech processing, computer vision, robotics dan sebagainya.

 

Gambar di bawah ini adalah sebuah graf simetris tak berarah yang menggambarkan kondisi jalan raya di suatu kota. Terdapat 8 simpul yang menyatakan persimpangan jalan dengan posisi-posisi koordinat dua dimensi (x,y). Setiap busur memiliki 2 atribut, angka pertama menyatakan panjang jalan sebenarnya (dalam satuan kilo meter), dan angka yang berada dalam tanda kurung, menyatakan kecepatan maksimum yang diperbolehkan untuk setiap kendaraan yang melalui jalan tersebut (dalam satuan km/jam). Seorang pimpinan satuan pemadam kebakaran, yang berada di persimpangan S, bermaksud memadamkan api di sebuah gedung yang terletak di persimpangan G. Dia menggunakan mobil pemadam kebakaran dengan kecepatan maksimum 90 km/jam. Bantulah petugas tersebut menemukan rute jalan dengan total waktu tercepat dari S ke G dengan menggunakan Metode A*.

 

 

  

 

 

 

 

 

            Jawaban :

Karena arenanya terbuka hanya 1 simpul, maka S adalah best node nya.

 

F(A) = 5+90=95

F(B) = 10+90=100

F(C)= 5+60=65

            

 

 

 

 

Selanjutnya adalah menentukan node kembali. Seperti yang kita ketahui bahwa node yang terbaik adalah F(C) = 65, closed = S, Open = A,B,C .

 

F(B)=SC+CB+HB

        = 5+4+90=99

F(F)=SC+CF+HF

        =5+12+50=67

 

Langkah kedua C dengan biaya terkecil (65) terpilih menjadi Best Node dan dipindahkan ke Closed. Semua suksesor di C dibuka yaitu B dan F dan dimasukan ke open.

F(B) Jika starting point dari C = 99

F(B) sebelumnya adalah 100

B berganti parent dari S ke C

Open = (A,B,C,F)

Closed = (C,S)

 

F menjadi titik awal karena merupakan best node dari opened list/closed list maka langsung dihitung nilainya

F(E)=SE+FE+HE

        =5+5+100=109

F(G)=CF+FG+HG

        =12+5+40=57

 

 

 

 

 

Hasil akhirnya yaitu :

Jalur terpendek melalui : S>C>F>G dengan nilai 57

Opened list akhir ; (A,B)

Closed list akhir : (S,C,F)