Algoritma Pencarian Part 1 : Mendefinisikan Masalah Sebagai Suatu Ruang Keadaan

Metode pencarian adalah bagian dari kesimpulan, dimana setiap state menggambarkan hipotesis dalam sebuah rangkaian deduktif. metode pencarian dikatakan penting untuk menyelesaikan permasalahan karena setiap state (keadaan) menggambarkan langkah-langkah untuk menyelesaikan permasalahan

Mendefinisikan Masalah Sebagai Ruang Keadaan

Secara umum untuk mendekripsikan suatu permaslahan dengan baik harus:

1. Mendefinisikan suatu ruang keadaan
2. Menerapkan satu atau lebih keadaan awal.
3. Menetapkan satu atau lebih tujuan
4. Menetapkan kumpulan aturan

Contoh : Masalah teko air

Ada dua buah teko masing-masing berkapasitas 4 galon (Teko A) dan 3 galon (Teko B). Tidak ada tanda menunjukkan batas ukuran pada kedua teko tersebut. 

Permasalahannya : Bagaimana kita dapat mengisikan tepat 2 galor air kedalam teko yang berkapasitas 4 galon?

Dari permasalahan diatas untuk mendefinisikan masalah sebagai ruang keadaan kita tentukan langkah-langkah sebagai berikut:

 A. Identifikasi ruang keadaan

      Permasalahan ini dapat dilambangkan dengan (x,y), dimana:

      - x = air yang diisikan pada teko A

      - y = air yang diisikan pada teko B

B. Keadaan awal dan tujuan

     - Keadaan awal kedua teko dalam keadaan kosong (0,0)

     - Tujuan, keadaaan dimana pada teko 4 galon berisi tepat 2 galor air (2,n) 

 

C. Aturan-aturan

     Mendifinisikan aturan pada permasalahan teko air

GRAPH KEADAAN

Graph terdiri dari node-node yang menunjukkan keadaan, yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator. metode pencarian akan berusaha menemukan kombinasi dari item-item yang dimulai dari start meunju ke goal. berikut merupakan contoh graph keadaan dari masalag teko air sebelumnya:

POHON PELACAKAN

Untuk menghindari kemungkinan adanya proses pelacakan suatu node secara berulang, maka digunakan struktur pohon.

Struktur pohon digunakan untuk menggambarkan keadaan secara hirarkis. pohon juga terdiri dari beberapa node. 

1. Node Akar

    - Terletak pada level ke-0 (menunjukan kedaan awal yang biasanya disebut topik/objek)

    - Mempunyai node cabang sucessor yang sering disebut dengan node "anak" dan perantara

    - pencarian mundur dapat dilakukan jika node anak/perantara memiliki predecessor

2. Node daun

    - node yang tidak memiliki anak dan menunjukan akhir dari pencarian

    - berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end)

Berdasarkan graph keadaan dari permasalahan teko sebelumnya. maka kita dapat membuat pohon pelacakan seperti berikut:

Dari gambar diatas saya mendefinisikan istilah yang ada pada pohon pelacakan agar lebih mudah untuk dipahami.

1. node akar merupakan node yang memiliki warna ungu, sedangkan node anak/perantara ditunjukan dengan kotak berwarna putih
2. node daun ditunjukan dengan warna biru yang merupaka goal yang diharapkan. (node D juga bisa disebut node daun karena berisi jalan buntu)
3. node bewarna hijau sering sebebut sebagai repeat node, node ini tidak perlu ditulis ataupun dijabarkan lebih mendalam. (boleh ditulis dengan memberikan simbol yang berbeda)
4. garis panah penghubung node memiliki angka yang menunjukan dengan menggunakan rule nomer berapa node tersebut dapat dijabarkan.

Sekian dulu ya teman-teman.. selanjutnya akan dibahas tentang metode pencarian buta., Kalian bisa klik link dibawah ini untuk membaca bagiana part 2 nya.. Terima kasih ^_^