INFORMED AND UN-INFROMED SEARCH

TUGAS 1 " KECERDASAN BUATAN "

Rose Setiana

Teknik Informatika (5b)

Universitas Muhammadiyah Sukabumi

HEURISTIC / INFORMED SEARCH GENERATE AND TEST

Search

Menurut Luger (2005), search adalah sebuah teknik menyelesaikan masalah (problem solving) yang mengembangkan sebuah ruang permasalahan secara sistematik dalam sebuah proses. Terdapat 4 kriteria untuk menentukan performa sebuah metode pencarian, yaitu Completeness, Time Complexity, Space Complexity, dan Optimality. Completeness adalah apakah metode tersebut menjamin ditemukannya solusi jika solusi tersebut ada. Time Complexity adalah lama waktu yang dibutuhkan untuk menemukan solusi tersebut. Space Complexity adalah jumlah memory yang diperlukan dan yang dimaksud Optimality adalah apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang lain.

Metode pencarian dibagi menjadi dua strategi, yaitu uninformed search dan informed search. Uninformed search merupakan suatu strategi pencarian tanpa ada informasi mengenai cost (bobot) atau informasi tertentu sedangkan Informed search merupakan suatu strategi pencarian yang membutuhkan informasi mengenai cost (bobot) atau informasi tertentu.  

Heuristik

Heuristik berfungsi untuk meningkatkan efisiensi dari sebuah proses pencarian. Tidak semua teknik heuristik memenuhi empat kriteria performa suatu metode pencarian. Fungsi heuristik digunakan untuk menghitung path cost dari suatu node awal menuju node tujuan. Fungsi heuristik yang digunakan dalam penelitian ini adalah Straight-line distance atau jarak secara garis lurus. Jarak yang digunakan dalam penelitian ini adalah jarak dan waktu sebenarnya yang diperoleh penulis dari Dinas Perhubungan Komunikasi dan Informatika.

Algoritma Generate and Test

Algoritma Generate and Test merupakan algoritma paling sederhana dalam teknik pencarian heuristik. Dalam Generate and Test, terdapat dua prosedur penting yaitu generate (membangkitkan) yaitu membangkitkan semua solusi yang mungkin dan test (pengetesan) yaitu menguji solusi yang dibangkitkan tersebut. Algoritma Generate and Test menggabungkan algoritma DFS dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju state awal.

Algoritma Generate and Test adalah sebagai berikut :

1. Bangkitkan sebuah solusi yang mungkin

2. Menguji tiap-tiap node yang merupakan solusi dengan cara membandingkan node tersebut dengan node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yangdiharapkan.

3. Jika solusi telah ditemukan, maka keluar dari sistem. Jika belum menemukan solusi, maka kembali ke langkah 1.  

Bus Trans Jogja

            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.

Hasil dan Pembahasan

    Berikut ini akan disajikan gambar implementasi sistem yang telah dibuat oleh penulis. Gambar 1 menunjukkan implementasi tampilan awal Form Utama. Gambar 2 menunjukkan implementasi tampilan Form Utama setelah dilakukan pencarian. Gambar 3 menunjukkan implementasi tampilan Form Analisis. Form Analisis berfungsi untuk menunjukkan halte yang dilewati beserta trayek yang digunakan, perhitungan jarak atau waktu, total perpindahan trayek, serta daftar tempat makan sesuai dengan tujuan. 

          Gambar 1 Tampilan Awal Form Utama 

Gambar 2 Tampilan Form Utama Setelah Pencarian 

Gambar 3 Tampilan Form Analisis

 Berikut ini adalah contoh penyelesaian kasus algoritma Generate and Test dengan mengadaptasi situasi dan kondisi bus Trans Jogja. Gambar 4 dibawah ini menggambarkan kasus yang akan diselesaikan.  

                   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 = 5 menit, 2A = 7 menit, 2B = 10 menit, dan 3A = 7 menit.

Daftar waktu yang dibutuhkan adalah : 

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 :

1.   Menjabarkan satu per satu kemungkinan yang ada. Gambar 5 menggambarkan proses penjabaran satu per satu kemungkinan yang ada

Gambar 5. Pohon Penyelesaian

2. Membuat daftar tabel beserta perhitungan jarak dan waktu untuk setiap jalur yang telah dilewati.

Tabel 1 Tabel Alur Pencarian Jarak

No	Rute yang Mungkin	Panjang Rute	Rute yang Dipilih	Panjang Rute yang 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

.
Tabel 2 Alur Pencarian Waktu

No	Rute yang Mungkin	Total Waktu (menit)	Rute yang Dipilih	Waktu yang Dipilih (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

3. Dari Tabel 1 ditemukan rute terpendek berdasarkan jarak adalah A – D – C dengan total jarak 10        km. Rute alternatif 1 adalah  A – B – C dengan total jarak 11 km. Rute alternatif 2 adalah A – E –        B – C  dengan total jarak 11 km. 

4. Dari Tabel 2 ditemukan rute terpendek berdasarkan waktu adalah A – D – C dengan total waktu 13      menit. Rute alternatif 1 adalah  A – B – C dengan total waktu 15 menit. Rute alternatif 2 adalah A      – E – B – C dengan total waktu 15 menit.  

5. Setelah melakukan perhitungan jarak dan waktu, langkah selanjutnya adalah menentukan trayek          bus yang digunakan pada masing-masing rute. Tabel 3 menunjukkan penentuan trayek pada                masing – masing rute.   

Tabel 3 Penentuan Trayek

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

Berdasarkan analisis perhitungan yang dilakukan maka rute terpendek berdasarkan jarak adalah A – D – C dengan total jarak tempuh 10 km tanpa perpindahan.

Berdasarkan analisis perhitungan yang dilakukan maka rute terpendek berdasarkan waktu adalah A – D – C dengan total waktu tempuh 13 menit tanpa perpindahan trayek.

4. Analisis Sistem

            Analisis yang dilakukan terdiri dari 3 hal yaitu keberhasilan sistem, waktu proses, keefektifan hasil trayek. Keberhasilan sistem dinilai dari keberhasilan sistem dalam menemukan rute terpendek dengan pengujian yang dilakukan terhadap 50 kasus yang berbeda. Waktu proses dibedakan menjadi 2 yaitu waktu proses dengan parameter jarak dan waktu proses dengan parameter waktu. 

Analisis waktu proses dilakukan dengan pengujian terhadap 50 kasus. Hasil trayek dinilai efektif jika saran trayek yang dihasilkan sistem sesuai dengan kenyataan. Analisis hasil trayek dilakukan dengan pengujian terhadap 25 kasus dengan parameter jarak dan waktu. Oleh karena itu, penulis akan membandingkan hasil trayek tersebut dengan saran trayek yang penulis dapatkan dari pakar. Pakar tersebut adalah pramugara bus Trans Jogja.

Berikut ini adalah hasil pengujian yang dilakukan pada masing-masing analisis:

1. Berdasarkan pengujian terhadap 50 kasus, sistem mampu menemukan rute terpendek, alternatif rute (jika ada), dan saran trayek.

2. Berdasarkan pengujian terhadap 50 kasus, waktu rata-rata yang diperlukan sistem untuk menemukan rute terpendek dengan parameter jarak adalah 14,88 detik.

3. Berdasarkan pengujian terhadap 50 kasus, waktu rata-rata yang diperlukan sistem untuk menemukan rute terpendek dengan parameter waktu adalah 14,86 detik.

4. Pengujian keefektifan hasil trayek dengan parameter jarak pada 25 kasus, diketahui 3 kasus tidak sesuai dengan kenyataan.

5. Pengujian keefektifan hasil trayek dengan parameter waktu menunjukkan keberhasilan pada 25 kasus.

5.   KESIMPULAN

Berdasarkan pengujian dan analisa sistem serta memperhatikan keseluruhan proses yang terjadi, maka dapat diperoleh kesimpulan sebagai berikut :

1)  Sistem mampu menerapkan algoritma Generate and Test untuk menemukan rute terpendek, rute  alternated beserta saran trayek.

2)    Sistem mampu menampilkan analisis perhitungan jarak atau waktu beserta jumlah pergantian trayek yang digunakan.

3)    Prosentase keberhasilan sistem dalam menemukan rute terpendek dengan algoritma Generate and Test mencapai 100%.

4)   Perbedaan rata-rata waktu proses yang dibutuhkan sistem dalam menemukan rute terpendek dengan parameter jarak dan waktu tidak terlalu signifikan yaitu 14,88 detik untuk parameter jarak dan 14,86 detik untuk parameter waktu.

5)    Hasil keefektifan hasil trayek yang dihasilkan parameter jarak mencapai 88% dan keefektifan mencapai 100% untuk parameter waktu.    

REFERENSI

       Https://www.academia.edu

       Kusumadewi, Sri. (2003). Artificial Intelligence: Teknik dan Aplikasinya, Edisi Pertama.  Graha Ilmu. 

      Luger, G,F. (2005). Artificial Intelligence : Structures and Strategies for Complex Problem Solving, . Addison-Wesley. 

      Russel, Stuart J and Norvig. (1995). Artificial Intelligence : A Modern Approach. New Jersey: Prentice Hall, Inc.

     Shaffer,C.A. (1997). A Practical Introduction to Data Structure and Algorithm Analysis. New Jersey : Prentice Hall, Inc. 

       Wilson, R. dan Watkins, J. (1990). Graphs Theory. Toronto : John Willey & Sons, Inc

ITERATIVE DEPEENING SEARCH

   Iterative Deepening Search Iterative Deepening Search (IDS) merupakan metode yang menggabungkan kelebihan BFS (complete dan optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan sedikit memori). Tetapi konsekuensinya adalah time complexity-nya menjadi tinggi. Perhatikan gambar 1. IDS melakukan pencarian secara iteratif menggunakan penelusuran Depth-Limited-Search (DLS) dimulai dengan batasan level 0. Jika belum ditemukan solusi, maka dilakukan iterasi ke-2 dengan batasan level 1. Demikian seterusnya sampai ditemukan solusi.  

Penelusuran di setiap proses pencariannya menggunakan cara kerja DFS, yaitu dengan menelusuri satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Demikian seterusnya sampai ditemukan solusi. [1] Dengan adanya kelebihan pada DFS, maka IDS hanya membutuhkan memori yang kecil karena hanya simpul dalam path saja yang disimpan. Sama halnya dengan BFS, metode IDS dapat menemukan solusi terbaik karena pencarian dilakukan secara merata terlebih dahulu hingga batas bertambah dan perulangan terjadi, ini mendukung IDS untuk menemukan solusi tanpa akan menemukan jalan buntu jika percabangan ke bawah pada pohon tidak terbatas

IMPLEMENTASI ALGORITMA DALAM STUDI KASUS

Kakuro muncul pertama sekali pada tahun 1966 di majalah teka teki Amerika Serikat pada tahun 1966. Pada saat itu, permainan teka-teki itu bernama "Cross Sums". Pada tahun 1980, seorang pria Jepang yang bernama Maki Kaji mengadakan kunjungan bisnis ke Amerika Serikat. Maki adalah seorang penggemar teka-teki, seperti orang Jepang pada umumnya. Maki sangat tertarik dengan permainan teka-teki ini, sehingga setelah kembali ke Jepang, Maki mulai membuat dan mempublikasi permainan ini di Jepang. Permainan ini dinamakan kasan kurosu, kombinasi dari kata Jepang untuk "tambah", dan kata Inggris "cross" dalam bahasa Jepang. Selanjutnya, kasan kurosu berubah nama menjadi kakuro. Pemain hanya bisa memasukkan angka dari 1 hingga 9, sehingga jumlah angka sama dengan petunjuk. Tidak boleh terdapat angka yang sama pada baris dan kolom yang sama. Hanya akan ada satu solusi untuk setiap puzzle.

1.Angka yang dapat dimasukkan adalah 1 sampai

2. Jumlah dari angka secara horizontal harus sama dengan petunjuk atau nilai yang tertulis di samping

3. Jumlah dari angka secara vertikal harus sama dengan petunjuk atau nilai yang tertulis di atas

4. Hanya boleh terdapat satu angka pada satu baris yang sama dan satu kolom yang sama

5.  Hanya boleh terdapat satu angka pada satu baris yang sama dan satu kolom yang sama

Iterative Deepening Search

Pencarian jawaban Kakuro dilakukan dengan menggunakan algoritma pencarian Iterative Deepening Search (IDS).
Pencarian dimulai dari kotak pertama, yaitu kotak-0. Apabila kotak-0 adalah kotak petunjuk, maka majukan indeks kotak dan lanjutkan pemeriksaan pada kotak-1. Kotak-1 hingga kotak-8 juga merupakan kotak petunjuk, sehingga pencarian berlanjut hingga kotak-9. Pencarian dilanjutkan ke kotak-9. Kotak-9 kosong atau dianggap bernilai ’0’, tambahkan angka sekarang dengan satu = ’1’ dan uji angka ’1’ pada kotak-9. Ternyata angka ’1’ tidak menyalahi aturan, karena belum terdapat angka ’1’ pada baris pertama atau kolom pertama. Tempatkan angka ’1’ pada kotak-9.

Majukan indeks dan lanjutkan pemeriksaan pada kotak-10. Kotak-10 kosong atau dianggap bernilai ’0’, tambahkan angka sekarang dengan satu = ’1’ dan uji angka ’1’ pada kotak-1. Angka ’1’ menyalahi aturan, karena telah terdapat angka ’1’ pada baris yang sama (sebelah kiri). Tambah angka dengan satu dan uji dengan angka ’2’. Ternyata angka ’2’ tidak menyalahi aturan, karena belum terdapat angka ’2’ pada baris pertama atau kolom kedua, kemudian hasil penjumlahan baris juga sama dengan 3 (sesuai dengan nilai penjumlahan baris pada kotak-8 yang menjadi kotak petunjuk). Tempatkan angka ’2’ pada kotak-10

Pencarian dilanjutkan ke kotak-11. Kotak-11 merupakan kotak petunjuk, majukan indeks pencarian ke kotak-12. Kotak-12 merupakan kotak petunjuk, majukan indeks pencarian ke kotak-13. Kotak-13 kosong atau dianggap bernilai ’0’, tambahkan angka sekarang dengan satu = ’1’ dan uji angka ’1’ pada kotak-13. Ternyata angka ’1’ tidak menyalahi aturan, karena belum terdapat angka ’1’ pada baris pertama atau kolom yang sama. Tempatkan angka ’1’ pada kotak-13.

Bila setelah diuji hingga angka ’9’ dan suatu kotak jawaban masih tidak dapat diisi angka, maka pencarian backtrack ke kotak jawaban sebelumnya, dan melakukan pengujian kembali dengan angka yang lain.

Demikian pencarian berlangsung, hingga semua kotak jawaban terisi dengan angka yang valid. Pada posisi ini, solusi soal Kakuro telah terpecahkan, apabila terjadi backtrack pada kotak-0, maka soal Kakuro tidak memiliki solusi atau penyelesaian.

Demikian pencarian berlangsung, hingga semua kotak jawaban terisi dengan angka yang valid. Pada posisi ini, solusi soal Kakuro telah terpecahkan.

Apabila terjadi backtrack pada kotak-0, maka soal Kakuro tidak memiliki solusi atau penyelesaian.

Hasil

1. Sistem dapat digunakan untuk mencari jawaban dari permainan teka-teki Kakuro dengan   menggunakan algoritma pencarian Iterative Deepening Search (IDS) sehingga pembuat soal Kakuro   dapat menguji apakah soal yang telah dibuatnya mempunyai solusi atau tidak.

2. Sistem dapat menampilkan langkah-langkah pencarian IDS, sehingga user dapat melihat proses   pencarian yang dilakukan oleh sistem.

3. Bila soal Kakuro tidak memiliki jawaban, maka sistem akan menampilkan pesan kesalahan.

4. Sistem dapat menampilkan langkah-langkah pencarian IDS, sehingga user dapat melihat proses   pencarian yang dilakukan oleh sistem.

5. Sistem dapat mencari jawaban lebih cepat apabila digunakan pencarian cepat (sistem tidak mencatat langkah-langkah pencarian).

6. User dapat memainkan Kakuro dengan langsung memasukkan angka pada kotak-kotak yang kosong. Apabila solusi Kakuro ditemukan, maka sistem akan menampilkan pesan.

REFERENSI

Cormen, et.al, 2009, Introduction to Algorithms, Third Edition. MIT Press, Massachusetts.

Freeman Joan, dan Utami Munandar, 2001, Cerdas dan Cemerlang, PT. Gramedia Pustaka Indonesia,  Jakarta

Hurlock, 2010, Psikologi Perkembangan, Penerbit Erlangga, Jakarta.

Le Compte, D., 2010, 200 Crazy Clever Kakuro Puzzles, Lulu.com.

Prasetyo, R. Muhammad Khalil, 2012, Penyelesaian Permainan Checkers Pada Mobile Device Berbasis Android Menggunakan Algoritma Iterative Deepening Search, USU, Medan.