SIMULASI PENCARIAN JALAN MENGGUNAKAN ALGORITMA BACKTRACKING Samuel Lukas1, Toni Anwar2, Sony Panji Wicaksono3 Abstract Path Finding is a problem that appears in the development of hardware or software, which related to artificial intelligence Problems. The goal of this experiment is to solve path-finding problem using backtracking algorithm. To reach this goal an application was developed. This application named Path Finding Path Finding Simulation constructed based on Java application that contains three major steps. They are creating random map, creating two objects and located them in the map. and simulated the trip of one object, which try to find another object. This Simulation has three features: simulation, testing, and about. The design and implementation of Path Finding Simulation will be explained in this paper. It also concluded how good backtracking algorithm can be used to solve the problem.
1.PENDAHULUAN Metoda pencarian jalan untuk menemukan suatu objek adalah suatu permasalahan yang sering dihadapi dalam pembuatan piranti keras dan piranti lunak yang berhubungan dengan kecerdasan buatan. Robot yang bergerak dari satu lokasi ke lokasi tertentu yang sudah diketahui tetapi jafen mana yang harus ditempuhnya masih merupakan suatu persoalan apabila robot belum mengetahui rute yang dapat dilalui. Piranti lunak berupa game, khususnya game strategi, menggunakan algoritma tertentu untuk menyelesaikan masalah pencarian jalan, sedemikian rupa sehingga apabila pemain memerintahkan agar pasukan bergerak dari satu posisi ke posisi lain hanya dengan menunjuk mouse. Berbagai metode dapat digunakan dalam menyelesaikan masalah pencarian jalan, salah satunya metode backtracking. Backtracking adalah metode yang sering digunakan untuk mencari solusi dari suatu permasalahan. Cara yang tepat untuk mencari solusi dari suatu permasalahan adalah : membuat daftar solusi yang mungkin, menguji setiap solusi yang mungkin, dan memilih solusi yang benar. Metode backtracking merupakan cara yang sistematis untuk menguji setiap solusi yang mungkin dari persoalan yang ada [10] Dalam masalah pencarian jalan, setiap jalan yang ada dalam peta dapat menjadi solusi untuk menemukan objek yang dicari. Dengan menggunakan metode backtracking, kita dapat menentukan jalan pada peta sampai didapatkan satu solusi, yaitu jalan yang tepat menuju objek yang dicari.
1
Dosen Tetap Jurusan Teknik Informatika, FIK UPH Dosen Tetap Jurusan Teknik Informatika, FIK UPH 3 Alumni Jurusan Teknik Informatika, FIK UPH
2
Simulasi Pencarian Jalan ... (S. Lukas, T. Anwar, S P Wicaksono)
41
Berdasarkan hal di atas, maka penulis mengembangkan suatu aplikasi Simuiasi Pencanan Jalan menggunakan algoritma backtracking. Secara garis besar aplikasi simuiasi pencanan jalan menerapkan algoritma backtracking dalam dua langkah, yaitu membuat peta acak kemudian menentukan lokasi objek yang mencari dan objek yang dicari dan menjalankan simuiasi pencarian jalan dengan algoritma backtracking. 2. BACKTRACKING Sartaj Sahni [1] menyatakan empat langkah yang dilakukan untuk mencari jawaban dari suatu permasalahan. Pertama, membuat daftar seluruh kemungkinan jawaban. Kedua, menguji setiap kemungkinan jawaban. Ketiga, melakukan tindak lanjut terhadap seluruh atau sebagian hasil pengujian dari kemungkinan jawaban yang telah diuji. Keempat, mengidentifikasikan jawaban yang didapat. Namun langkah-langkah di atas hanya dapat dilakukan jika kemungkinan jawabannya terbatas, jika kemungkinan jawabannya tidak terbatas atau sangat besar langkah-langkah di atas sulit dilakukan. Metode backtracking adalah salah satu metode yang sistematik untuk menguji setiap kemungkinan jawaban dari suatu persoalan. Pengujian yang sistematis seringkali dapat mengurangi waktu pengujian dalam kasus terbaik atau kasus yang terburuk. Bahkan metode backtracking dapat mengurangi pengujian terhadap kemungkinan jawaban dengan jaminan bahwa solusi tetap dapat ditemukan. Penerapan metode backtracking dapat digambarkan dalam sebuah state-space tree. Root dari tree adaiah initial state (state awal) sebelum pencarian dilakukan. Node pertama dari tree menggambarkan pilihan dari komponen awal jawaban, node kedua menggambarkan komponen kedua, dan seterusnya. Sebuah node dari sfafespace tree disebut menjanjikan apabila node tersebut merepresentasikan komponen dari jawaban dan masih menuju ke pembentukan jawaban yang utuh. Sebuah node disebut tidak menjanjikan apabila node tersebut tidak merepresentasikan jawaban dan tidak menuju ke pembentukan jawaban yang utuh. Apabila sebuah node adalah promising node maka akan dibentuk child dari node tersebut yang merepresentasikan kemungkinan komponen jawaban selanjutnya. Apabila sebuah node adalah nonpromising node maka node tersebut akan dihapus dan algoritma akan kembali ke parent dari node tersebut. Demikian seterusnya sampai terbentuk jawaban yang utuh dari state-space tree. Ada beberapa contoh penyelesaian masalah yang menggunakan metode backtracking, seperti n-Queens Problem, Hamiltonian Circuit Poblem, Subset-Sum Problem, dan masih banyak lagi. Berikut ini pseudocode yang umum digunakan untuk menerapkan metode backtracking. Backtracking(X[1..i]) lfX[1..i]is a solution write X[1..i] Else For each x element of S,+r and consistent with X[1..i] and constraints do X[i+1]*-x Backtracking(x[1.. i+1]) Hasil dari metode backtracking berupa himpunan hasil atau r)-fup/e(xi,x2 ,xn). Himpunan hasil atau tuple tersebut terbentuk dari himpunan jawaban yang mungkin yang telah diuji dengan metode backtracking. Misalnya untuk n-Queens Problem himpunan hasil atau tuple berisi urutan nomor kolom dari setiap queens. Solusi 42
Jurnal llmiah llmu Komputer, Vol. 4 No. 1 Januari 2006: 41-48
berupa himpunan hasil himpunan kemungkinan Problem), atau dapat kemungkinan jawaban masalah dengan metode
atau tuple dapat memiliki panjang yang sama dengan jawaban (n-Queens Problem dan Hamiltonian Circuit juga memiliki panjang yang berbeda dari himpunan (Subset-Sum Problem). Sebagian besar penyelesaian backtracing menggunakan depth first search.
Walaupun metode backtracking dapat digunakan untuk menyelesaikan ketiga permasalahan di atas, namun metode backtracking bukanlah metode yang sangat efisien. Dalam kasus terburuk (worst case) metode backtracking dapat membuat himpunan seluruh kemungkinan jawaban dan mengujinya satu persatu. Akan tetapi metode backtracking baik digunakan untuk menyelesaikan permasalahan dimana tidak ada algoritma yang dapat menemukan solusinya secara tepat. Metode backtracking menyelesaikan permasalahan dengan lebih optimal karena metode backtracking dapat tidak perlu menguji seluruh kemungkinan jawaban.
3. PERANCANGAN SISTEM Simulasi pencarian jalan menggunakan algoritma backtracking membuktikan bahwa algoritma backtracking dapat menyelesaikan masalah pencarian jalan. Secara garis besar program ini terbagi menjadi dua bagian. Pertama, pembuatan peta random (random map) kemudian meletakkan dua objek (objek yang mencari dan objek yang dicari) dalam peta Kedua, pencarian jalan dengan menerapkan algoritma backtracking. 3.1
Pembuatan Peta Random
Langkah-langkah yang digunakan untuk membuat peta acak yang salah satunya diperlihatkan pada Gambar 1 adalah sebagai berikut: 1. 2 3.
4. 5. 6. 7. 8.
Tentukan luas area peta (500x500 pixels). Pada setiap sisi peta, bangkitkan secara acak 5 kelompok jalan Setiap kelompok jalan berjarak 30 pixels. Hubungkan setiap kelompok jalan sisi kiri dengan satu kelompok jalan sisi alas sedangkan kelompok setiap kelompok jalan sisi kanan dengan satu kelompok jalan sisi atas. Kelompok mana yang saling terhubung dilakukan secara acak. Setiap hubungan antar kelompok jalan membentuk 2 jalan Membuat sebuah kelas jalan untuk setiap jalan yang terbentuk. Mencari setiap persimpangan yang terbentuk oleh jalan-jalan pada peta. Menyimpan data setiap persimpangan dengan cara membuat sebuah kelas simpang untuk setiap persimpangan yang terbentuk. Meletakkan objek pencari dan objek yang dicari pada dua jalan yang berbeda secara acak.
Simulasi Pencarian Jalan ... (S. Lukas. T. Anwar, S.P Wicaksono)
43
• •• GambaM: Salah satu peta acak
3.2. Pencarian Jaian dengan Menggunakan Algoritma Backtracking Langkah-langkah yang dilakukan untuk melakukan simulasi masalah pencarian jalan dengan algoritma backtracking adalah sebagai berikut: 1 2 3. 4.
Mengidentifikasi jalan dimana objek pencari dan objek yang dicari berada Mencari persimpangan-persimpangan yang ada pada jalan dimana objek pencari berada Mengecek apakah jalan tersebut horisontal atau vertikal Mendefinisikan gerak objek pencari. Pendefinisian ini meliputi beberapa langkah yaitu : A. Mendefinisikan lokasi awal objek sebagai sebuah persimpangan. Apabila objek berada pada jalan horisontal maka persimpangan hanya memiliki arah gerak kiri dan kanan, apabila objek berada pada jalan vertikal maka persimpangan hanya memiliki arah gerak atas dan bawah. Memasukkan persimpangan tersebut dalam stack. B Menghitung jarak terpendek yang dilalui untuk mencapai objek yang C dicari dengan asumsi pergerakan sejauh 20 pixels (lihat Gambar 2). Menentukan arah gerak objek sesuai penghitungan jarak terpendek (lihat Gambar 2). y
S
• --X -.„-••-•-
-•*
**
'^
•
| Objek yang mencari 1 Objek yang dicari
h.•
Jarak l Jarak 2
Arah gerakan
Gambar 2: Menentukan jarak terpendek antara objek pencari dan objek yang dicari
44
Jurnal llmiah llmu Komputer, Vol. 4 No. 1 Januari 2006: 41-48
5. 6.
7.
8. 9.
Melakukan pengecekan apabila objek yang dicari tidak terdapat pada jalan yang dilalui atau stack tidak kosong lakukan langkah 6 sampai dengan 8 jika tidak maka berhenti. Apabila tidak ada persimpangan maka gerakan objek pencari mendekati objek yang dicari sejauh 20 pixels arah jalan jika tidak maka masukkan persimpangan dalam stack. Mengecek apakah persimpangan masih memiliki arah atau tidak, apabila tidak maka program melakukan backtracking, yaitu dengan menghapus persimpangan tersebut dari stack dan objek yang mencari kembali ke persimpangan sebelumnya. Apabila persimpangan masih memiliki arah maka program akan mengecek arah gerakan terpendek untuk menentukan jalan selanjutnya. Kemudian kembali ke langkah 6 Apabila program keluar dari loop karena objek yang dicari ditemukan (pada jalan yang sama dengan objek yang mencari), maka objek yang mencari akan bergerak menuju ke objek yang dicari. Jika program keluar dari loop karena stack kosong (objek yang dicari tidak ditemukan), maka program akan memberikan informasi bahwa tidak ada jalan menuju ke objek yang dicari.
4. Penerapan dan Hasil Percobaan 4.1. Penerapan Perancangan Sistem Aplikasi ini dibuat dengan menggunakan piranti lunak Java versi 1.4.1 dengan bahasa pemrograman Java. Aplikasi ini memiliki 3 fitur yaitu simulasi, testing dan about. ^^^w Ti
7
Gambar 3: Tampilan bagian fitur Simulasi
Fitur simulasi berisi program untuk melakukan simulasi pergerakan objek pencari hingga sampai ke objek yang dicari. Fitur ini memiliki tiga bagian yaitu gambar, Titik dan jalan. Pada bagian Gambar, user dapat melakukan pengacakan untuk menentukan peta. Pada bagian Titik, user dapat menentukan letak objek yang Simulasi Pencarian Jalan ... (S. Lukas, T. Anwar, S.P Wicaksono)
45
mencari dan objek yang dicari pada peta. Sedangkan pada bagian Jalan, user dapat menjalankan simulasi. Pada fitur ini setiap langkah perpindahan objek pencari diperlambat hingga sebesar 100ms (0.1 detik) untuk pergerakan sejauh 20 pixels, hal ini bertujuan agar user dapat melihat dengan cukup jelas bagaimana algoritma backtracking dapat digunakan dalam menyelesaikan masalah pencarian jalan. Gambar 3 memperlihatkan tampilan fitur simulasi. Fitur testing berisi program untuk melakukan testing pada program. Pada dasarnya fitur ini sama dengan fitur simulasi. Perbedaannya jika pada fitur simulasi bagian gambar, titik, dan jalan dipisahkan, dan user dapat menentukan gambar dan titik secara acak, maka pada fitur testing bagian gambar, titik, dan jalan digabungkan, dan user tidak dapat menentukan gambar dan titik. Pada fitur ini user akan diminta memasukkan jumlah percobaan yang akan dilakukan, setiap percobaan meliputi bagian gambar, titik, dan jalan yang ketiganya dilakukan oleh program. Apabila percobaan telah selesai dilakukan, program akan memberikan informasi berapa kali objek pencari menemukan objek yang dicari, dan berapa kali tidak dapat menemukan objek yang dicari. Pada fitur ini setiap langkah perpindahan objek yang mencari ditentukan sebesar 10ms (0.01 detik), hal ini bertujuan agar proses percobaan menjadi cepat. User dapat melihat informasi percobaan saat seluruh percobaan selesai dilakukan. Fitur about menyediakan informasi mengenai aplikasi ini. Fitur ini berisi informasi utama mengenai aplikasi simulasi pencarian jalan. Informasi tersebut berupa judul lengkap aplikasi, tahun pembuatan dan nama developer.
4.2. Hasil Percobaan dan Pembahasan Pengujian pertama dilakukan dengan melakukan 30 kali percobaan yang diperlihatkan pada Tabel 1. Setiap percobaan terdiri atas 20 kali simulasi kemudian dicatat keberhasilan objek pencari mencari objek yang dicari. Tabel 1: Tabel hasil pengujian pertama
Percobaan I 2 3 4 5 6 7 8 9 10 ll I2 13 14 15
46
Menemukan 19 15 17 18 18 16 20 16 17 17 18 20 18 1') 19
Gagal 0 0 0 0 0 0 0 0 0 0 0 0 () 0 0
Percobaan 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Menemukan 16 16 16 14 19 17 17 16 16 17 17 17 17 17 17
Gagal 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Jurnal llmiah llmu Komputer, Vol. 4 No. 1 Januari 2006: 41-48
Dari pengujian 600 kali tehihat bahwa objek pencari menemukan objek yang dicah sebanyak 516 kali dan tidak berhasil menemukan objek yang dicah sebanyak 84 kali. Akan tetapi kegagalan pencarian objek adalah 0%. Hal ini disebabkan objek pencari tidak menemukan objek yang dicah karena memang dalam percobaan pada peta tidak adajalan dan objek pencari ke objek yang dicah (Gambar 4).
Objek yang mencari Objek yang dicari
Gambar 4: Peta dengan lokasi objek yang dicari dan objek yang mencari
5.
KESIMPULAN DAN SARAN
Dari pembahasan yang telah dilakukan maka dapat disimpulkan : • • •
Metode backtracking dapat digunakan untuk menyelesaikan masalah pencarian jalan. Peta yang digunakan dalam aplikasi ini adalah peta acak yang dibuat oleh program bukan peta yang sesungguhnya. Simulasi masih bersifat statis, belum memiliki kemampuan untuk mengatasi hal-hal yang bersifat dinamis seperti lalu-lintas (rambu-rambu, lampu lalulintas, kepadatan, dll).
Beberapa saran untuk pengujian lebih lanjut: • •
Penggunaan peta sesungguhnya dalam simulasi, bukan peta yang dibuat dalam program. Penambahan fitur-fitur dalam aplikasi untuk mengatasi kondisi-kondisi yang bersifat dinamis.
Simulasi Pencarian Jalan ... (S. Lukas, T. Anwar, S.PWicaksono)
47
DAFTAR PUSTAKA [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
48
Jerry Banks, Discrete System Simulation, New Jeresy: Prentice Hall, 2001. H.M. Deitel, JAVA HOW TO PROGRAM, New Jeresy: Pearson Education, Inc., 2003. Mario Hadiwinata, Solusi Pemrograman XML Web Service, Jakarta: PT. Elex Media Komputindo, 2003. Adi Kurniadi, Pemrograman Microsoft Visual Basic 6, Jakarta: PT. Elex Media Komputindo, 2002. Yahya Kurniawan, Pemrograman Visual Basic .Net 2003, Jakarta: PT. Elex Media Komputindo, 2003. Anany Levitin, The Design & Analysis of Algorithms, New York: Pearson Education, Inc., 2003. Patrick Naughton, JAVA HANDBOOK, New York: McGraw-Hill, 1996. Roger S. Pressman, Software Engineering - A Practical Approach 5th Edition, New York: McGraw-Hill, 2001. Dan Rahmel, Visual Basic .Net Programer's Refference, California:McGraw Hill/Osborne, 2002. Sartaj Sahni, Data Structure, Algorithms, dan Application IN JAVA, Florida: McGraw-Hill, 2000.
Jurnal llmiah llmu Komputer, Vol. 4 No. 1 Januari 2006: 41-48
