Jika diinginkan untuk mendapatkan sebuah jalan untuk berpindah dari titik asal A ke titik tujuan B, sedangkan alternative jalur yang aakan dilalui ada lebih dari satu macam, maka diperlukan sebuah upaya untuk mencari (search) sebuah jalan yang diinginkan yang lebih optimal.

Pada tutorial ini, akan dipelajari dua bentuk algoritma pencarian (searching) yang termasuk kelompok uninformed searching, yaitu depth first and breadth first.

Teknik pencarian (searching) termasuk ke dalam studi kecerdasan buatan (artificial intelegence – AI). Seperti yang diketahui bersama bahwa tujuan umum dari kecerdasa buatan adalah untuk memberikan komputer suatu kemampuan untuk berpikir atau dengan kata lain berperilaku seperti layaknya manusia. Permasalahn yang kemudian muncul adalah, sayangnya mesin komputer tidak dapat memiliki pikiran seperti yang dimiliki oleh manusia. Sehingga komputer memerlukan serangkaian langkah yang harus dilakukan sebelum menemukan solusi. Yang selanjutnya dilakukan oleh manusia adalah merumuskan langkah dan algoritma kemudian mentranslasikannya ke dalam bentuk yang bisa dimengerti olej komputer.

Representasi Pemodelan Proses Pencarian (Search Representation)

Reperesentasi suatu permasalahan menjadi sangat penting dilakukan sebelum lebih jauh melangkah ke proses inti penyelesaian permasalahn. Demikian juga dengan proses pencarian. Pemodelan usuatu proses pencarian akan lebih memudahkan dan lebih bisa memvisualisasikan langkah-langkah untuk menemukan titik  ysng dituju. Di bawah ini digambarkan sebuah pohon pencarian (search tree). Gambar tersebut menunjukkan serangkaian node yang saling terkoneksi yang akan dilewati pada saat proses pencarian.


Untitled1_3

Dari grafik di atas, jalur koneksi hanya satu arah. Semua jalur hanya akan berjalan dari atas ke bawah. Dengan kata lain A mempunyai jalur ke B dan C, akantetapi B dan C tidak mempunyai jalan menuju ke A. Perumpamaan seperti jalan satu arah.

Setiap huruf yang ada dalam lingkaran adalah sebuah node. Sebuah node dapat dihubungkan dengan node yang lain melaui edge atau path. Node-node yang saling terhubungkan disebut denan bertetangga  (neighbour). B dan C merupakan tetangga dari A. E dan D adalah tetangga dari B, dan B bkan merupakan tettangga dari D atau E karena B tidak dapat dijangkau melalui D maupun E (ingat jalur koneksi hanya satu arah-dari atas ke bawah).

Grafik pencarian yang telah dibuat di atas, juga mempunyai kedalaman (depth) seperti pada gambar di bawah ini:

Untitled2_4

Dari pemodelan pada grafik di atas, kita sudah bisa mendapatkan atau lebih tepatnya menentukan titik asal dan titik tujuan yang akan dicari. Dari grafik juga telah didapatkan node mana saja yang saling bertetangga atau terhubung, seberapa kedalaman tingkatan dari grafik pencarian, dan estimasi jalur yang bisa ditempuh. Akan tetapi ini saja belum bisa untuk memberikan deskripsi algoritma pencarian, akantetapi hal ini akan sangat membantu untuk memahami objek permasalahan sebagai pemahana dasar dari sebuah algoritma pencarian. 

Depth First Search

Pencarian dengan metode depth first searching dilakukan dengan mengambil sebuah node, memeriksa node-node yang manjadi tetangganya, menguraikan node pertama dari node-node tetangganya, mengecek apakah node yang akan diuraikan adalah tujuan, jika ya maka proses pencarian berhenti, akantetapi jika tidak, maka proses akan berlanjut dengan menguraikan node tersebut, demikian seterusnya.

Penjelasan di atas mungkin akan sedikit menjemukan jika ini merupakan tutorial pertama tentang depth first search. Untuk lebih memahami dan menggambarkan proses tersebut, mari  ita ambil sebuah contoh bahwa kita mendapatkan permasalahn untuk memilih mencari jalur dari A menuju ke F.

Untitled3_2



Step 0

Kita mulai dengan node yang menjadi asal pencarian , dalam kasus ini adlah node A.

Untitled4_2

Untuk mempermudah pamahaman, digunakan istilah Open List untuk menyimpan track yang ingin kita lakukan dan Closed List untuk menyimpan track yang telah dilakukan atau dilewati. Pada tahap awal, Closed List belum memiliki isi, sedangkan Open List memiliki isi berupa node A sebagai node yang ingin diproses.

·         Open List: A

·         Closed List: <kosong>



Step 1

Selanjutnya kita urai node A, yang mempunyai dua node tetangga yaitu node A dan node B.

Untitled5_3

Setelah proses ekspansi dari node A ini, maka A akan masuk ke dalam Closed List dan node B dan C yang akan dilakukan proses ekspansi selanjutnya padanya, masuk ke salam Open List.

·         Open List: B, C

·         Closed List: A



Step 2

Pada Open list terdapat 2 buah node. Untuk depth first search dan breadth first search, selalu yang diurai terlebih dahulu adalah item node yang pertama dari Open list. Item pertama pada open list pada kasus ini adalah node B. B bukan merupakan tujuan dari yang kita harapkan, jadi dari node B dilakukan eksplorasi terhadap node-node yang menjadi tetangganya (neighbour).

Untitled6_2

Karena node B telah diurai, maka node B yang tadinya berada di dalam open list, sekarang berpindah ke dalam closed list. Sehingga closed list mempunyai dua item yaitu A dan B. Sedangkan dari hasil penguraian B didapatkan 2 node tetangga yaitu D dan E yang akan diproses selanjutnya. Sehingga item di open list bertambah menjadi D, E dan C. Kita lihat bahwa hasil dari eksplorasi B yaitu D dan E diletakkan pada open list di depan C (di bagian awal open list). Disinilah letak perbedaan dengan breadth first search, dimana hasil eksplorasi ditaruh dibelakangnya.

·         Open List: D, E, C

·         Closed List: A, B



Step 3

Karen D berada di awal open list, maka dilakukan proses terhadap  D, Karen ingat pada depth first search atau pada breadth first search yang dilakukan proses pertama kali adalah node yang berada di awal. Karena D bukan merupakan tujuan yang dimaksud, maka dilakukan ekspansi terhadap D,. Karena D tidak mempunyai node tetangga, maka tidak ada penambahan item pada open list. Dan D berpindah ke dalam closed list. Tersisa E dan C pada open list.

·         Open List: E, C

·         Closed List: A, B, D



Step 4

Sekarang giliran E yang akan diproses, karena sekarang E berada di awal open list. Dari proses penguraian E akan didapatkan dua node tetangga yaitu F dan G yang dimasukkan kemudian ke awal open list. Sehingga terdapat tiga item pada open list yaitu F, G dan C. Pada closed list mendapat tambahan E yang baru saja selesai kita uraikan. Sehingga di closed  list terdapat 4 item yaitu ABDE.

Untitled7_4

·         Open List: F, G, C

·         Closed List: A, B, D, E



Step 5

Selanjutnya kita urai F yang berada di awal open list. Sebelum kita urai, seperti tahap-tahap yang sebelumnya dicek apakah dia merupakan tujuan. Ternyata F merupakan tujuan yang dicari. Sehingga, tidak perlu dilanjutkan proses ekspansi/penguraian. Item F berpindah dari open list menuju ke closed list, sehingga pada closed list terdapat 6 item yaitu, A,B,D,E, dan F. Ini merupakan hasil akhir, karena sekali lagi tujuan F sudah diadapatkan.

Untitled8_2

·         Open List: G, C

·         Closed List: A, B, D, E, F



Dari beberapa tahap yang telah kita lakukan, maka didapatkan hasil dengan mnegggunakan metode depth first search.