Breadth First Search (BFS) dan Depth-First Search (DFS)

Algoritma Pencarian
            Algoritma Pencarian (Search Algorithm) adalah algoritma yang digunakan untuk menemukan sebuah item yang spesifik di dalam sekumpulan item. Item tersebut bisa berupa sebuah record di dalam database atau bisa juga berupa element dari ruang pencarian yang didefinisikan oleh prosedur ataupun perhitungan matematis. Dalam Kecerdasan buatan, algoritma pencarian dibagi menjadi dua metode, yaitu:

1. Breadth First Search (BFS)
                         Pada metode ini, melakukan pencarian secara melebar yang mengunjungi simpul secara preorder. Maksud dari preorder tersebut adalah melakukan pengecekan dengan mengunjungi suatu simpul kemudian mengunjungi simpul lainnya yang ada di sebelah/bertetanggaan dengan simpul yang sudah dikunjungi tersebut dan begitu seterusnya sampai menemukan solusi.
                 Contoh metode pencarian dengan BFS

Maka penyelesaiannya : 1, 2, 3, 4, 5, 6, 7, 8, 9
Kelebihan :
a. Jika menemukan solusi lebih dari satu, metode ini menjamin menemukan solusi yang paling baik
b. Tidak akan menemui jalan buntu
Kekurangan :
a. Membutuhkan memori yang lumayan banyak
b. Membutuhkan waktu yang cukup lama



2. Depth-First Search (DFS)
                        Pada metode ini, memakai algoritma penelusuran struktur graf / pohon. Simpul ditelusuri dari akar kemudian ke salah satu cabangnya. Misalnya prioritas penelusuran berdasarkan anak pertama (simpul sebelah kiri), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.Setelah sampai di level terdalam belum ditemukan solusi, maka penelusuran akan kembali ke  1 level sebelumnya untuk menelusuri yang sebelah kanan sampai lever terdalam, kemudian jika masih belum ditemukan maka akan lanjut menelusuri ke simpul anak kedua pada pohon biner [simpul sebelah kanan] dengan menelusuri sampai level terdalam dan seterusnya.
Contoh metode pencarian DFS

Maka penyelesaiannya : A-B-D-H-E-I-C-F-G-J-K-L
Kelebihan :
a. Membutuhkan memori yang relatif kecil
b. Membutuhkan waktu yang relatif singkat karena jika solusi yang dicari berada pada level yang dalam dan paling kiri maka akan menemukan solusi tanpa harus menguji lebih banyak lagi
Kekurangan :
a. Tidak optimal, jika terdapat solusi lebih dari satu, metode ini tidak ada jaminan untuk menemukan solusi paling baik
b. Memungkinkan tidak ditemukannya tujuan yang diharapkan

Komentar

Posting Komentar

Postingan populer dari blog ini

Besaran Vektor dan Skalar

Gambar
DASAR TEORI 1. B esaran Vektor & Skalar 1.1 Besaran Vektor         Besaran Vektor merupakan besaran fisika yang memiliki nilai dan arah . Nilai dan arah menjadi informasi yang saling berhubungan. Dalam menyatakan vektor, nilai vektor harus diikuti arahnya. Contoh besaran vektor adalah perpindahan, kecepatan, gaya, momentum, medan listrik dll.         Besaran vektor biasanya digambarkan dengan anak panah lurus. Arah besaran ditunjukkan oleh arah   panahnya, sedangkan   besar vektor nya digambarkan dengan panjang garis anak panah tersebut.           Apabila tanda panah mengarah ke kanan atau atas, maka artinya positif dan diberi tanda (+) dan jika sebaliknya, bila menggambar vektor ke kiri atau bawah maka artinya negatif dan diberi tanda (-).         Vektor dilambangkan dengan tanda panah di atas suatu huruf(sebelah kiri). Dibeberapa buku penulisan hurufnya dicetak tebal, cetak miring atau huruf kapital. Untuk menuliskan besaran vektor, diberi penambahan lambang mutl
Baca selengkapnya

Tugas Rumah

Gambar
TUGAS RUMAH 1.       Samakan satuan kecepatan, jarak, dan waktu dari helikopter tersebut dan hitung kecepatannya ( Pada https://id.wikipedia.org/wiki/Helikopter ) (Heli ini mencatat rekor terbang sejauh 122,35 km dan lama terbang satu jam 20 menit 49 detikPada waktu lain ia terbang hingga ketinggian 3427 meter dan rekor kecepatan 122 km/jam) dan jelaskah apakah helikopter termasuk GLB atau GLBB ?   2.  Kapan percepatan dibilang negatif dan kapan dibilang positif ? Kemudian carilah contoh kasus dari masing-masing percepatan tersebut dan berikan hitungan matematisnya.                                                                                          JAWAB : ·         Percepatan dibilang positif apabilakecepatan benda bertambah tiap selang waktu dan akan dibilang percepatan negatif apabila kecepatan nilai dari benda tersebut bernilai negatif terhadap waktu atau benda mengalami perlambatan pada suatu waktu. Jadi percepatan negatif bisa juga disebut dengan
Baca selengkapnya

PAPER

PENERAPAN TEKNOLOGI MAGLEV ( Magnetic Levitation )  PADA TRANSPORTASI UMUM BUS Ayu Ainun A’ziziyyah Program Studi Teknologi Informasi Fakultas Teknologi Informasi dan Industri Institut Teknologi Telkom Surabaya Jl. Gayungan PTT 17-19 Surabaya Telp. 081139808009 E-mail : ayuainun0@gmail.com ABSTRACT              This paper was made against the background by the rampant traffic accidents caused by public transportation, both limited and economic. Bus public transportation is a transportation that is widely used by the community, but in terms of safety and comfort, passengers in this transportation do not guarantee. Lots of traffic accidents caused by buses, either because of a sleepy driver or a reckless driver. It is often found that bus drivers break through the road boundary between the left and right lanes simply because they are forced to break through the density of the road or break through traffic signs. This causes inconvenience to passengers and other roa
Baca selengkapnya