Generate and Test - Depth Limited Search

NIM                 : 1730511097

Nama             : Salmaa Felia Mentari

Prodi               : Teknik Informatika

Mata Kuliah : Kecerdasan Buatan

1.    Generate and Test

Generate and test atau biasa disebut dengan pembangkitan dan pengujian merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking, yaitu bergerak ke belakang menuju pada suatu keaadan awal. Generate and test ini termasuk kedalam salah satu jenis teknik pencarian terbimbing atau lebih dikenal dengan nama pencarian heuristic. Pencarian heuristic sendiri merupakan teknik pencarian yang dalam proses pencariannya ada informasi awal yang digunakan. Fungsi heuristic digunakan untuk menghitung path cost dari suatu node awal menuju node tujuan. Dan algoritma yang paling sederhana dalam teknik pencarian heuristic ini ialah algoritma generate and test, dimana algoritma ini merupakan alternative dibangkitkan dengan cara menyusun fasilitas-fasilitas dalam urutan abjad. Adapun langkah dalam membentuk alternatifnya, seperti pada gambar berikut ini.

 Teknik pelacakan generate and test

Dari contoh di atas dapat dilihat cara kerja generate and test:

Node S = Start

Node N = Goal

Solusi = S – A – D – A – E – F – E – G – B – H – B – I – J – I – K – C – L - N

Algoritma dari metode generate and test, sebagai berikut :

a.    Bangkitkan satu kemungkinan solusi (membangkitkan satu titik tertentu atau lintasan tertentu dari keadaan awal).

b.    Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.

c.    Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.

Adapun implementasi dari algoritma Generate and Test ini salah satunya adalah pencarian jalur terpendek. Dan penelitian yang telah dilakukan oleh mahasiswa universitas Kristen duta wacana pada jurnal informatika yaitu  mengimplementasikan konsep pecarian heuristic dengan algoritma Generate and Test pada pencarian rute terpendek dengan studi kasus bus Trans Jogja. Parameter yang digunakan adalah jarak dan waktu. Dari hasil penelitian tersebut didapatkan sebuah system yang mampu menemukan rute terpendek, rute alternative (jika ada), saran trayek yang digunakan beserta analisis perhitungan setiap rute yang ditemukan.

Bus trans jogja resmi beroperasi pada akhir 2007 dengan jam operasi antara pukul 05.30-21.30 WIB dan berhenti di halte-halte khusus yang telah disediakan. Sekarang ini, total jumlah halte yang ada dan tersebar di DIY adalah 108 halte ditambah dengan 4 terminal yang menjadi tempat singgah dan transit bus Trans Jogja sehingga total seluruhnya adalah 112 tempat yang dilalui oleh bus Trans Jogja. Trans Jogja memiliki 8 trayek yaitu 1A, 1B, 2A, 2B, 3A, 3B, 4A, dan 4B.

 

 Gambar 1. Tampilan awal form utama

Gambar 2. Tampilan form utama setelah pencarian

Gambar 3. tampilan form analisis

 Berikut ini merupakan contoh penyelesaian kasus algoritma Generate and Test dengan mengadaptasi situasi dan kondisi bus Trans Jogja.

Gambar 4. Contoh kasus

Pencarian dilakukan dari titik A menuju titik C dengan daftar trayek :

1A melewati halte : A, D, dan C

2A melewati halte : A, E, D, dan C

1B melewati halte : B dan D

2B melewati halte : A dan B

3A melewati halte : B, C, dan E

Waktu jeda 1A = 5 menit, 1B = menit, 2A = 7 menit, 2B = 10 menit, dan 3A = 7 menit

A – B = 8 menit	B – D = 7 menit
A – D = 5 menit	D – C = 8 menit
A – E = 5 menit	E – B = 3 menit
B – C = 7 menit	E – D = 5 menit

Berikut ini adalah langkah-langkah penyelesaian kasus di atas adalah : Menjabarkan satu per satu kemungkinan yang ada.

Gambar 5. Pohon penyelesaian

Table 1. Alur pencarian jarak

		Rute				Pan			Rute		Panjang
		yang				jang			yang		Rute
		mungkin							Dipilih		yang
						Rute					Dipilih
1		ABC			11				ABC		11
2		ABDC			17				ABC		11
3		ADC			10				ADC		10
4		AEBC			11				ADC		10
5		AEBDC			17				ADC		10
6		AEDC			13				ADC		10

Table 2. Alur pencarian waktu

	Rute	Total	Rute	Waktu
	yang	Waktu	yang	yang
	mungkin		Dipilih	Dipilih
		(menit)		(menit)
1	ABC	15	ABC	15
2	ABDC	23	ABC	15
3	ADC	13	ADC	13
4	AEBC	15	ADC	13
5	AEBDC	23	ADC	13
6	AEDC	18	ADC	13

Table 3. Penentuan trayek

	Rute		Trayek	Perhitungan	Total	Total
			yang lewat	Jeda	Waktu	Pindah
	ADC		1A	0	13+0 =	10
					13
	ABC		2B, 3A	10+7 = 17	15+17	1
					= 32
	AEBC		2A, 3A, 1B, 1A	5+7+7	15+24	3
					= 39
				+5=24

2.    Depth Limited Search

Depth limited search merupakan salah satu metode teknik blind search/uninformed search, merupakan pencarian solusi tanpa adanya informasi yang dapat mengarahkan pencarian untuk mencapai goal state dari current state disebut pencarian buta. Algoritma depth limited search sendiri memberikan batas kedalaman pada algoritma dept first search (Russel & Norvig, 1995). Dengan algoritma depth limited search, penelusuran depth first search data dibatasi sehingga tidak melakukan penelusuran terlalu dalam. Gambaran kerja algoritma depth limited search dapat digambarkan dalam bentuk tree. Tree merupakan sebuah graf tidak berarah dan merupakan jaringan bersambung yangtidak memiliki untai (loop) sehingga dengan demikian dapat disimpulkan bahwa sebuah tree dapat dibentuk dari graf sederhana karena graf sederhana tidak memiliki self loop ataupun edge parallel. Tree terdiri dari sekumpulan elemen. Elemen tree adalah akar atau root dan simpul. Derajat atau degree sebuah simpul menunjukkan jumlah anak pada simpul tersebut. Adapun algoritma depth limited search adalah sebagai berikut :

a.    Tetapkan node awal dengan kedalaman = 0 dan tentukan batas kedalaman.

b.    Cek apakah kedalaman node adalah node tujuan. Jika benar maka proses berhenti, jika tidak maka lanjut ke langkah c.

c.    Cek apakah kedalaman node sama dengan batas kedalaman yang telah ditentukan. Jika benar, maka lanjutkan proses dengan menelusur hanya node-node yang berada dalam batas kedalaman yang telah ditentukan dan belum dikunjungi dengan kembali kelangkah b. Jika tidak, maka lanjutkan ke langkah d.

d.    Perluas node dan kembali ke langkah b.

Implementasi Algoritma Depth Limited Search salah satunya seperti yang telah diterapkan pada hint permainan peg solitaire. Dimana papan permainan versi inggris ukuran 3x3 dan triangular berukuran 4x4, 5x5, serta 7x7, mampu menemukan solusi yaitu sisa satu kelereng serta mampu menangani apabila tidak menemukan solusi. Penerapan algoritma depth limited search pun mampu menampilkan semua perpindahan langkah hingga ditemukan sisa 1 kelereng. Hal ini dibuktikan dengan cara menguji 10 soal pada system. Dari hasil pengujian 10 soal pada system, 9 soal berhasil diselesaikan dan 1 soal gagal diselesaikan karena tidak menemukan solusi berupa sisa 1 kelereng. Pada awal permainan, lubang tengah pasti dikosongkan. Peg solitaire ini dimainkan dengan cara :

1.    Kelereng akan melompati kelereng lain menuju lubang kosong.

2.    Kelereng yang telah dilompati akan hilang atau keluar dari permainan.

3.    Permainan akan dianggap selesai apabila hanya tersisa satu kelereng.

Strategi terbaik yang dapat dilakukan agar dapat menemukan solusi pada permainan peg solitaire adalah mengarahkan kelereng ke lubang bagian tengah dan menyelamatkan kelereng terisolasi yang terdapat di lubang-lubang bagian pinggir. Gerakan kelereng yang diperbolehkan adalah melangkah ke kanan, melangkah ke kiri, melangkah ke atas, dan ke bawah.

System yang dibangun dari hasil penelitian pada jurnal infromatika menggunakan 8 form yang terdiri dari form utama, form jenis soal, form permainan untuk inggris dan eropa serta triangular, form tampil tree untuk inggris dan eropa serta triangular, form instruksi, dan form detail. Implementasi form permainan untuk papan versi inggris dapat dilihat pada gambar dibawah ini:

 gambar 1. Form permainan

            Penelusuran solusi permainan Peg Solitaire dengan algoritma Depth Limited Search dilakukan untuk menemukan jalur solusi menuju sisa 1 kelereng dengan algoritma Depth Limited Search dimana batas kedalamannya adalah jumlah kelereng. Adapun satu contoh kasus penyelesaian suatu kondisi pada permainan Peg Solitaire versi inggris dengan ukuran 3x3 dengan menggunakan penelusuran pohon Depth Limited Search. Contoh penerapan ini menggunakan jenis soal cross atau salib yang terdiri dari 6 kelereng yang membentuk salib.

gambar 2. Penerapan algoritma Depth Limited Search pada papan versi inggris dengan tipe soal salib

Gambar 3. Jalur solusi

gambar 4. Hasil penelusuran algoritma Depth Limited Search

Daftar Pustaka

Nugraha, Dedi., & Winiarti, Sri. 2014. Pengembangan Media Pembelajaran Sistem  Pelacakan pada Mata Kuliah Kecerdasan Buatan Berbasis Multimedia, Jurnal Sarjana Teknik Informatika. Yogyakarta : Universitas Ahmad Dahlan.

Helvin, Ivanka Eka Santhi., Virginia, Gloria., Purwadi, Joko. 2007. Perbandingan Algoritma Genetika dengan Algoritma Generate Test pada Perencanaan Tata Letak Fasilitas Rumah Sakit Umum, Jurnal Informatika. Yogyakarta : Universitas Kristen Duta Wacana.

Welianto, Selvy., Santosa, R Gunawan., C, Antonius Rachmat. 2012. Implementasi Algoritma Generate And Test pada Pencarian Rute Terpendek, Jurnal Informatika. Yogyakarta : Universitas Kristen Duta Wacana.

R, Griffin Theresia., Purwadi, Joko., C, Antonius Rachmat. 2011. Implementasi Algoritma Depth Limited Search pada Permainan Peg Solitaire, Jurnal Informatika. Yogyakarta : Universitas Kristen Duta Wacana.

Mahafi, Galang Aditya., & Hermawan, Galih. 2013. Game Edukasi Penyakit Malaria dan Cara Pencegahannya, Jurnal Ilmiah Komputer dan Informatika (KOMPUTA). Bandung : UNIKOM

Adha, M Aidil. 2010. Peta Interaktif Pencarian Jalur Terpendek dengan Menggunakan Algoritma Semut untuk Penjemputan Barang, Tugas Akhir. Pekanbaru : Universitas Islam Negeri Sultan Syarif Kasim.