Tugas Kecerdasan Buatan

Breadth-first Search
2.1 Pengertian Breadth First Search
Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi
semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1. Algoritma ini memerluka-n sebuah antrian q untuk
menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk
mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu
masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean
untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.
2
2.2 Metode Pencarian
Salah satu contoh kakas pencarian yang menggunakan metode BFS adalah WebCrawler. WebCrawler adalah suatu kakas yang membuat indeks isi dari suatu dokumen di Web yang
selanjutnya akan dimanfaatkan oleh mesin pencari. Terdapat tiga langkah yang dilakukan oleh
WebCrawler ini ketika mengunjungi dokumen, yaitu menandai bahwa suatu dokumen telah
dikunjungi, mengenali link yang terdapat pada dokumen tersebut, kemudian isinya didaftarkan
pada daftar indeks. Pada akhirnya, WebCrawler aakan menampilkan
file yang paling banyak berkaitan dengan kata kunci.
Contoh hasil pencarian dengan WebCrawler
Kata kunci : "molecular biology human genome
project"
Hasil pencarian :
1000 Guide to Molecular Biology Databases
0754 Guide to Molecular Biology Databases
0562 Biology Links
0469 bionet newsgroups
0412 Motif BioInformatics Server
0405 LBL Catalog of Research Abstracts (1993)
0329 Molecular Biology Databases
0324 GenomeNet WWW server
0317 DOE White Paper on Bio-Informatics
0292 Molecular biology
0277 Oxford University Molecular Biology Data
Centre Home Page
0262 Biology Internet Connections
0244 Harvard Biological Laboratories - Genome
Research
0223 About the GenomeNet
0207 Biology Index
Algoritma BFS yang diterapkan pada WebCrawler ini adalah mendaftarkan setiap link yang ada dan menyimpannya dalam data base kemudian mengunjunginya satu persatu sambil mencatat linkyang berhubungan
3. Depth-first Search
3.1 Pengertian Depth First Search
Depth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul
sebelum simpul tetangganya. Berkaitan dengan mesin pencari, DFS ini cenderung mengindeks
dokumen berdasarkan suatu link.
3.2 Metode Pencarian
Algoritma DFS yang diterapkan pada mesin pencari dalam melakukan pengindeksan adalah
mengunjungi suatu server kemudian menyimpan semua link yang berhubungan dengan server
tersebut baru kemudian mengunjungi server lain. Salah satu yang menerapkan algoritma DFS pada mesin pencarian adalah FTPSearch. FTPSearch adalah suatu mesin pencari dokumen
yang tersimpan di jaringan ITB. Dapat diakses pada http://ftpsearch.itb.ac.id. FTPSearch akan menampilkan daftar hasil pencarian berdasarkan server. File-file yang tersimpan pada suatu server akan ditampilkan terlebih dahulu kemudian baru berpindah pada server lain. FTPSearch tidak memperhatikan file mana yang lebih berkaitan dengan kata kunci karena FTPSearch tidak melakukan observasi sampai pada isi dokumen tapi hanya melihat judul dokumen.

4. Pola strategi menemukan file pada suatu
mesin pencari
Secara umum terdapat 3 pola strategi yang dilakukan oleh user mesin pencari untuk menemukan file yang sesuai dengan kata kunci yaitu strictly depth-first strategy, extreme breathfirst
strategy dan partially breath-first pattern)
4.1 Pengertian
Metode strictly depth-first srategy berarti pengguna mengamati tiap link hasil dari mesin pencari mulai dari atas, dan memutuskan segera untuk membuka dokumen atau tidak.
Metode extreme breath-first strategy berarti pengguna melihat keseluruhan link daftar hasil
pencarian kemudian memilih link yang mengacu ke dokumen yang paling sesuai lalu mengunjungi link tersebut. Sekali-kali pengguna juga melihat kembali daftar hasil pencarian lalu mengunjungi ulang beberapa link yang menurut dia berkaitan. Metode partially breath-first pattern merupakan metode campuran dimana pengguna melihat beberapa link baru memutuskan link mana yang akan dibuka.
4.2 Hasil Eksperimen
Pada eksperimen yang dilakukan oleh penelitian yang dilakukan oleh Kerstin Klockner, Nadine
Wirshum, Anthony Jameson, empat puluh satu subjek diberi waktu sepuluh menit untuk mendapatkan informasi tentang “Assessment centers” dengan cara membuka dokumen yang
relevan yang dikembalikan oleh Google sebagai respon pencarian. Sebuah daftar hasil pencarian
terdiri dari 25 hasil telah disiapkan sebelumnya dan disajikan dalam sebuah halaman web. Subjek harus menggulung layer untuk dapat melihat keseluruhan halaman. Gerakan mata para subjek dan aksi klik tetikus direkam dengan bantuan pendeteksi ASL
3
504. Berdasarkan rekaman video yang dibuat melalui pendeteksi itu, pemrosesan hasil pencarian
yang dilakukan para subjek dianalisis. Tiga kategori diidentifikasi : Sebagian besar subjek
(65%) mengaplikasikan strategi DFS. Kebalikannya, minoritas subjek mengaplikasikan pola strategi BFS yang ekstrim, melihat ke seluruh daftar hasil pencarian sebelum membuka sebuah
dokemen. Pola BFS yang parsial ditunjukkan oleh sisa 20% subjek, yang terkadang melihat ke
beberapa entri berikutnya sebelum memilih dokumen yang akan dibuka. Pada eksperimen dua, dua puluh tujuh subjek diminta untuk melakukan dua aktivitas yang sama dengan eksperimen satu, dengan waktu 5 menit untuk masing-masing aktivitas. Untuk menciptakan situasi yang membuat BFS terlihat relative menarik, kita memperbolehkan subjek untuk membuka maksimal sepuluh dari 25 dokumen yang di daftar, memberi penghargaan kepada mereka untuk setiap penemuan dokumen yang relevan (hamper setengah dari dokumen relevan). Di sini,
strategi yang berlawanan ditemukan lagi : 52% subjek tidak menunjukkan niat untuk melihat
keseluruhan daftar. Minoritas subjek sebanyak 11% menggunakan strategi BFS yang ekstrim, melihat ke seluruh daftar sebelum membuka sebuah dokumen; sisanya sebanyak 37% mengaplikasikan strategi campuran, melihat dulu ke dua sampai enam dokumen berikutnya dalam daftar.
4. Analisis
Berdasarkan penelitian yang dilakukan oleh Kerstin Klockner, Nadine Wirshum, Anthony Jameson pada makalahnya yang berjudul “Depth- and Breadth-First Processing of Search Result” kita dapat menyimpulkan bahwa pengguna cenderung melakukan pencarian secara strictly depth-first strategy . Yaitu melihat suatu link yang paling atas dari hasil pencarian kemudian mengaksesnya dan terus menelusuri link yang terdapat pada document tersebut yang berkaitan dengan kata kunci yang dicari.
Sehingga agar pencarian oleh FTP search lebih efektif perlu ada penyesuaian dengan algoritma
mesin pencari. Algoritma yang menurut kami paling sesuai adalah algoritma BFS pada mesin
pencari yang akan menampilkan daftar file yang paling dekat relefansinya dengan kata kunci.
Metode FTP search melakukan hal yang sama dengan WebCrawler yaitu mengunjungi setiap server, mencatat link file dan memasukkannya ke dalam basis data. Sehingga file yang paling relevan ditempatkan di bagian paling atas daftar hasil pencarian. Perbedaan dengan web crawler ftp search akan mengelompokkan file-file tersebut
berdasarkan server. Kelebihan metode baru ini bagi pengguna FTP search adalah pengguna akan dapat langsung melihat file yang paling relevan pada bagian atas daftar hasil pencarian dan meminimalisasi pengaksesan lintas server.
5. Kesimpulan
Berdasarkan analisis yang dilakukan maka algoritma BFS pada mesin pencarian dengan memperhatikan kebiasaan pengguna dalam membuka file daftar hasil pencarian akan mengefektifkan pencarian file di ftp search. Sehingga daftar hasil pencarian FTP search dapat lebih memudahkan pengguna dalam melakukan pencarian.