[0:00]Assalamualaikum warahmatullahi wabarakatuh. Ya, kali ini jumpa lagi dengan saya Ahmad Solihin. Ya, yang kali ini kita akan membahas mengenai konsep atau cara kerja algoritma Best First Search, BFS ya. Eh bukan Bread ya, karena ada Bread, ada Best, ada Deep. Nah, kali ini kita bahas mengenai Best First Search ya. Eh algoritma ini merupakan ya salah satu konsep dasar dari pencarian, ya, eh yang tentunya eh sering kita temukan gitu ya dalam berbagai aplikasi. Eh mari kita mulai saja.
[1:00]Ya, yang pertama Best First Search ini merupakan salah satu algoritma pencarian terbimbing, informed heuristic search, yang berusaha mencari solusi terbaik berdasarkan ukuran (fungsi) tertentu. Pencarian itu sebenarnya ada dua, ada yang terbimbing, ada yang tidak terbimbing, ya, atau dalam istilah eh bahasa Inggrisnya atau umumnya itu ada informed search atau heuristic search, ya. Eh dan nanti ada eh uninformed search. Ya. Nah, algoritma BFS ini berusaha mencari solusi terbaik berdasarkan eh satu ukuran atau fungsi tertentu. Ya, jadi ada ada ukuran atau ada fungsi tertentu yang menjadi dasar pencarian. Ya. Oke, nah, pencarian terbimbing atau informed search gitu ya heuristic search itu eh ada beberapa sih sebenarnya. Ada Generate and Test (GT) algorithm, ada Best First Search (BFS) algorithm: Greedy BFS, A* ya, eh dua di antara yang akan kita bahas adalah di eh termasuk eh algoritma Best First Search ya, yaitu Greedy Best First Search dan juga A-Star ya. Nah, Greedy dan juga A-Star ya. Kita akan nanti akan mulai penjelasan mengenai Greedy eh Greedy BFS. Nah, algoritma yang lain yang masuk ke dalam informed search ada Hill Climbing ya, simple Hill Climbing, Steepest Ascent Hill Climbing dan sebagainya. Ini eh tidak kita bahas di eh video ini. Nah, eh selain tadi eh sudah sempat disinggung, selain pencarian terbimbing atau informed search sebenarnya ada pencarian buta atau uninformed search atau sering disebut sebagai blind search, ya. Eh dua algoritma yang masuk dalam pencarian buta adalah Breadth First Search dan juga Depth First Search ya. Ini biasanya dipakai untuk penelusuran data ya, penelusuran data ada yang sifatnya Deep, ada yang sifatnya Bread, ya. Ini eh sudah dibahas di video-video saya sebelumnya. Baik, eh nah, sebelum kita membahas mengenai algoritma BFS-nya itu sendiri, ya, eh kita awali dengan penyelesaian satu masalah, yaitu harus diawali dengan mendefinisikan masalah yang tepat. Ya, pendefinisian ini mencakup spesifikasi yang tepat mengenai keadaan awal dan solusi yang diharapkan. Jadi sebelum melakukan pencarian, menerapkan algoritma, kita harus tahu dulu gitu kan ya. Eh kondisi kita ada di mana ya, kemudian solusi yang diharapkan atau tujuan kita itu ke mana gitu ya. Sama seperti kita melomba lari, start dan finish-nya juga harus jelas. Kalau start dan finish-nya enggak jelas, ya nanti larinya tidak akan punya arah, jadi enggak tentu arah, bisa jadi enggak selesai gitu kan ya. Eh karena tidak jelas kondisi awal dan juga akhirnya. Kemudian yang kedua, masalah dapat didefinisikan secara formal dengan 5 komponen. Ini eh dalam konsep algoritma pencarian atau penyelesaian masalah itu eh permasalahan bisa di-break down, dibagi menjadi 4 atau 5 komponen, ya. Yang pertama adalah initial state atau keadaan awal, kondisi saat ini, kondisi awal. Kemudian yang kedua ada action description atau deskripsi aksi, ya, nanti akan kelihatan di contoh lah gitu kan ya. Kemudian transition model, model transisi, eh goal test ini adalah uji solusi untuk me ini sebuah fungsi untuk melihat apakah kondisi yang terkini itu sudah sudah sesuai dengan solusi atau belum. Kemudian yang terakhir adalah Path Cost atau kompensasi jalur atau eh biaya gitu kan ya. Eh Path Cost ini eh merupakan eh satu ukuran gitu kan ya yang yang dinyatakan eh dengan biasanya berupa angka gitu kan ya, eh resource atau daya atau eh biaya ya yang diperlukan untuk untuk yang telah ditempuh gitu ya. Kalau bicara jarak ya mungkin eh berapa kilo yang sudah ditempuh. Bicara waktu ya berapa detik, berapa menit dan sebagainya. Kita lanjutkan. Ya, ini ini contoh ya, contoh pendefinisian ruang masalah. Misalnya ini ada sebuah peta gitu kan ya. Nah, katakanlah initial state-nya misal kondisi saat ini itu kita sedang berada di Semarang. Oke, berarti kita sedang berada di Semarang. Kemudian nanti eh action description-nya, oh ya dari Semarang ini bisa ke Demak, bisa ke Kudus, bisa ke Salatiga, bisa ke Purwodadi dan sebagainya gitu kan ya. Jadi itu itu action description, go to mana gitu kan ya. Kemudian transition model, transition model ini merupakan sebuah persamaan atau fungsilah gitu kan ya yang melibatkan tadi ya, kondisi awal dan juga akhir, ya. Eh hasil atau result dari eh kalau dari S dari start state ke A ke dikenai action description, maka hasilnya gimana gitu ya. Contoh misalnya go Kendal ya dari Semarang ke Kendal ya nanti dia hasilnya adalah berada di Kendal gitu ya. Nah, kemudian goal test ini adalah fungsi yang tadi dibilang bahwa apakah ini sudah berada di tempat tujuan atau belum ya. Nah, Path Cost ini ya berupa jarak ya. Eh kalau kalau di pemetaan seperti ini ya biasanya berupa jarak. Kita lanjutkan. Nah, eh setelah secara naratif eh masalah permasalahan itu didefinisikan, ya kita bisa representasikan ruang keadaan atau masalah itu dalam bentuk eh salah satunya adalah graph. Ya, jadi kita bisa representasikan dalam bentuk graph seperti ini ya, di mana eh setiap node itu biasanya mewakili titik-titik ya. Setiap node ini adalah titik dari dari kota. Ini node. Kemudian angka-angka ini ya mewakili cost tadi gitu ya. Path Cost-nya dan tanda panah ini adalah arah ya, yang bisa ditempuh. Dari M ke A ini bisa ditempuh tapi dari A ke M ini tidak bisa ditempuh dan seterusnya. Ya, selain itu bisa juga pakai tree ya, representasinya ruang keadaan pakai tree. Nah, dalam eh video ini kita akan membahasnya menggunakan representasi dalam bentuk graph gitu kan ya. Ya, contoh misalnya jika node awal M dan tujuan T, ada berapa kemungkinan jalur yang dapat ditempuh? Mau pakai graph atau tree, ya jawabannya sama, ya. M menuju T, ya. Jadi M bisa lewat M, A, B, C, E, H, T. Atau M, A, B, C, E, T. Dan seterusnya gitu kan ya. Kalau kita hitung ada sekitar lima empat kemungkinan, ya. Dengan tree juga sama ya pasti M D ada kemungkinan ke sana ya, M D C E H T dan seterusnya ya. Ini ada beberapa kemungkinan gitu kan ya, jalur yang bisa ditempuh. Nah, sekarang kita mulai masuk ke Best First Search-nya atau Best First Search ya. Eh node yang dipilih di dalam BFS ini berdasarkan evaluation function f(n), f(n) paling rendah akan dipilih.
[8:52]Fungsi heuristik h(n) adalah estimasi jarak terdekat antara node tertentu n dengan node tujuan. Jika h(n) = 0 maka n adalah node tujuan. Greedy BFS f(n) = h(n). A* f(n) = h(n) + g(n).
[9:20]Jadi kalau eh biayanya atau eh fungsinya itu sudah nol, maka itu sudah berada di tujuan ya. Kita akan bahas eh di contoh nanti akan lebih detail. Nah, kalau dalam Greedy BFS ya, ini fungsinya sederhana di mana f(n) = h(n). Ya, tapi kalau dalam A* itu nanti ada tambahkan tambahan f(n) = h(n) + g(n) ya. Ini nanti akan lebih jelas di contoh saya, ya. Nah, contoh ya, ini contoh kasus yang eh di buku buku-buku textbook ya, terkait dengan penjelasan algoritma pencarian biasanya menggunakan contoh ini ya, ini contoh umum, ya. Di mana eh ini kondisi kota-kota di eh kota Roma di sana gitu kan ya. Ya, eh dengan jarak eh berapa kilo antar kota ini gitu kan ya. Oke, ini kasus yang akan kita bahas. Nah, contohlah misalnya, kita eh diminta untuk mencari jalur terpendek gitu kan ya antara Arad ke Bucharest gitu. Ya kan ya, dari Arad ke Bucharest ya. Kalau kita bisa lihat secara visual ya, eh karena kita makhluk rata-rata ya, makhluk visual, ya maka eh ya kita akan cenderung untuk oh ya lurus saja ke sini gitu. Ya, lurus saja ke sini gitu kan ya. Nah, namun algoritma atau komputer kan tidak bisa seperti itu ya, dia harus mengkalkulasi segala kemungkinan yang bisa ditempuh untuk menuju ke Bucharest gitu kan ya. Nah, dan itu bisa jadi tidak ke sini langsung gitu ya, tapi dia ada perhitungan-perhitungan tertentu. Itu yang akan kita bahas. Oke, nah, kita pertama pakai algoritma Greedy BFS ya. Jadi, eh kalau karena tadi tujuanannya adalah ke Bucharest dan juga initial state-nya atau awalnya adalah ke Arad, maka pada saat kita berada di Arad gitu kan ya, ya Best Path-nya masih nol di sini ya. Path Cost-nya masih nol. Nah, cuman belum belum sampai tujuan.
[11:32]Ya jadi initial state ya. Pertama initial state-nya Arad, ya. Oke, kemudian yang kedua, nah dari Arad ini ada dua kemungkinan gitu kan ya. Bisa ke Zerind, bisa ke Sibiu, bisa ke Timisoara. Yang masing-masing punya punya cost-nya, Path Cost-nya ya, kalau ke Zerind itu 75 ya, 75. Ke Sibiu 140, ya ke Timisoara 118. Nah, dari sini kita pilih yang terbaik ya, kita pilih yang terpendek, ya. Rute terpendek yaitu Arad ke Zerind dengan Path Cost-nya adalah 75. Nah, apakah sudah sampai tujuan? Ya, tentu belum gitu kan ya. Oh, ini baru sampai Zerind, masih jauh dari Bucharest gitu kan ya. Tapi Path inilah yang akan ditempuh, ya. Jadi, saya ganti pointer dulu sebentar, ya. Jadi Path inilah yang akan di ditempuh ke atas. Nah, oke, kita lanjut apa karena belum berhenti, maka algoritma akan berlanjut gitu kan ya. Nah, sekarang ya, eh setelah kita tadi menempuh ke sini ya, ke sini ke sini sudah dihitung, ya. Berikutnya adalah dari Arad Zerind Oradea, ya. Lanjut lagi karena kan tadi kan yang dipilih adalah jalur ini, maka dilanjutkan jalurnya. Ya, dilanjutkan jalurnya ke Oradea. Ya, dengan Path Cost-nya adalah kalau ini ditotal adalah eh 146, ya kan, 146. Nah, Arad ke Sibiu tadi 140. Ya, sedangkan di Arad ke Timisoara adalah 118. Nah, 146, ya, dibandingkan 140 dan 118 tentu paling kecil adalah 118. Sehingga Path inilah yang akan dipilih oleh algoritma berikutnya. Sekarang algoritma beralih ke sini, ya. Algoritma pindah ke Timisoara, ya, dengan Path Cost-nya 118. Nah, dari Timisoara itu, eh sekarang eh tentunya algoritma itu bisa bergerak ke Lugoj, ya. Eh ke Lugoj itu 118 + eh 118 + 111 ya, di sini gitu kan ya. Itu hasilnya adalah 229. Ya, kemudian tadi yang sudah ditempuh itu adalah ini, ya. 146, sedangkan yang ketiga adalah ini, ya.
[14:25]Eh 140 maka inilah yang paling paling baik gitu kan ya. Ya, paling pendek ya, 140. Sehingga algoritma sekarang beralih ke Sibiu, ya. Jadi, dari Arad ke Sibiu, ini yang terbaik.
[15:37]Ya. Oke, nah, bagaimana langkah selanjutnya? Dari Oradea menuju ke Sibiu, ya, pasti ke sana. Ya, nah, ternyata dari Oradea menuju ke Sibiu itu 297, lebih eh besar gitu kan ya dibandingkan lewat Arad Sibiu terus Rimnicu Vilcea. Ya, ini sekarang jadi jalur terpendek yaitu 220, ya. Begitu seterusnya gitu kan ya. Eh selanjutnya Arad Timisoara Lugoj gitu kan ya, ini jadi yang terpendek, ya. Dan seterusnya sampai nanti intinya setiap ketemu titik itu akan akan apa ya? Akan dicek apakah sudah sampai Bucharest atau belum, ya. Begitu seterusnya nanti teman-teman semua bisa mengikuti alur algoritma ini dengan pelan-pelan gitu kan ya, bisa diulang-ulang, ya. Hingga nanti, nah ini ini menarik ya. Pada satu titik gitu kan ya, itu eh ada eh lima kemungkinan. Jadi, Arad, Zerind, Oradea terus Sibiu, ya, itu adalah 297 terus juga ada Arad, Sibiu, Fagaras, ya, dan juga ke Bucharest, ya. Ini kemungkinan kedua. Kemungkinan ketiga adalah Arad, Sibiu, Rimnicu Vilcea, Pitesti dan juga ke sampai sini ya. Nah, dan seterusnya gitu kan ya, ini ada beberapa ada lima kemungkinan. Nah, di sini sudah ada yang mencapai Bucharest, ya. Yaitu Arad, Sibiu, Fagaras, Bucharest. Nah, namun ya, eh walaupun sudah mencapai Bucharest tapi ini bukan jalur terpendek di antara yang lain. Sehingga pencarian itu tidak berhenti di sini, ya. Sudah mencapai tujuan Bucharest, apakah pencarian dapat dihentikan? Tidak, karena dia bukan jalur terpendek. Jadi, selalu algoritma mencari jalur yang terpendek atau Path Cost yang yang yang paling kecil. Ya. Nah, sehingga pencarian masih berlanjut gitu kan ya. Ya, berlanjut terus seperti tadi alur yang sebelumnya hingga nanti pada akhirnya ketemu eh jalur terpendeknya ya, ini masih beberapa langkah lagi ya.
[18:22]Ada naik ke atas, naik ke bawah, ada banyak kemungkinan gitu kan ya hingga Nah, oh sorry sebelum ini. Nah, hingga ketemu Path Cost terakhir ya, yang ternyata paling pendek itu adalah dari Arad, Sibiu, Rimnicu Vilcea, Pitesti hingga terakhir Bucharest. Ya, jadi ternyata lewat bawah di sini, lewat tengah ya, bukan lewat atas atau bukan lewat bawah. Ini dengan Path Cost-nya adalah 418, ya. Oke, nah itu Greedy Best First Search ya. Kalau dilihat dari langkahnya terlihat bahwa langkah tersebut cukup panjang ya. Eh ini tentunya akan membutuhkan waktu yang cukup lama untuk menemukan tujuan. Ya, tadi ibaratnya sudah oh hampir menemukan tujuan tapi eh harus dicari lagi, dicari lagi karena eh dia akan memikirkan atau mempertimbangkan eh ada eh kemungkinan jalur yang lain yang lebih baik atau tidak, gitu ya. Itu maka disebut sebagai Greedy, dia akan kunjungi hampir kunjungi semua node gitu kan ya untuk mencari jalur yang terbaik. Oke, itu terkait dengan Greedy Best First Search ya. Ya, selanjutnya algoritma A*. Algoritma A* ini merupakan ya boleh dibilang perbaikan dari algoritma Greedy BFS tadi, ya. Di mana eh fungsinya bukan cuma h(n) ya, bukan cuman berapa eh cost atau berapa jarak yang sudah ditempuh, tapi juga estimasi jarak ke tujuan, ya. Ini untuk apa namanya? Memastikan ya, bahwa eh kita sudah berada di arah yang benar gitu ya. Jadi eh diestimasikan juga jarak dengan tujuannya gitu ya. Ya ada fungsi biaya, kemudian kalau h(n) ini biaya yang sudah ditempuh, sedangkan g(n) ini adalah estimasi biaya menuju tujuan. Biaya dalam kaitan-kaitan dengan peta tadi ya jarak. Ya, kita lihat kembali gitu ya, kasus Romanian ini gitu ya, eh bahwa eh ini adalah jarak, kemudian yang sebelah kanan di sini, ini adalah eh berapa eh jarak ke Bucharest gitu kan ya, dari kota tertentu. Misalnya dari Arad ke Bucharest itu ternyata diestimasikan 366. Ya, dari Arad eh dari misalnya Fagaras ke ke Bucharest. Fagaras mana Fagaras? Ya, Fagaras ke Bucharest itu diestimasikan 178. Ini kan estimasi, ini estimasi. Jadi kalau yang ini real ya, yang ini estimasi. Nah, itu akan dipakai ya, dipakai untuk eh menjadi menjadikan algoritmanya menjadi lebih terarah ya. Oke, contoh misalnya Path Arad Sibiu, ya. Jadi Arad Sibiu misalnya berada di sini, ya. Nah, ini kalau dihitung berapa f(n)-nya, itu maka h(n) + g(n). h(n)-nya berapa? Oh, 140 dari Arad ke Sibiu kan 140.
[21:33]Sedangkan g(n)-nya ya, g(n)-nya itu kan estimasi jarak ke tujuan, ya. Eh kita cari di situ Sibiu, mana Sibiu. Nah, Sibiu adalah 253, ya. Nah, sehingga 140 + 253 sehingga nanti dianggap cost-nya adalah 393, ya. Ini cost-nya karena ditambah.
[22:54]Langkah langkah kedua nih setelah initial state. Langkah ketiga, ya, eh ternyata langsung nih Arad Sibiu Rimnicu Vilcea Pitesti ini langsung menjadi jarak yang paling paling baik gitu kan ya. Ya, karena dia punya eh Path Cost-nya adalah 415.
[23:37]Ya. Nah, eh terakhir, eh belum ya. Belum ini eh ternyata ada yang lebih pendek ya. Arad Sibiu Fagaras gitu kan ya. Eh dibanding Arad Sibiu Rimnicu Vilcea Pitesti Bucharest gitu kan ya. Dibanding ke sini, ya. Ini eh lebih pendek ya. Yaitu 417. Ya, namun demikian ini juga masih belum berhenti ya. Pada saat ditambah dengan ini itu akan menjadi lebih panjang nanti gitu kan ya. Nah, sehingga yang terakhir menang, ya, sama seperti tadi hasilnya adalah eh melewati Arad Sibiu Rimnicu Vilcea Pitesti dan terakhir Bucharest, ya. Ini kalau dibandingkan dengan algoritma yang sebelumnya, Greedy Best First Search gitu kan ya, maka ini jauh lebih singkat gitu kan ya. Langkahnya tidak banyak gitu kan ya dibanding algoritma yang sebelumnya, ya. Algoritma A* dapat menemukan tujuan lebih cepat dibanding Greedy BFS, ya. Oke, saya kira itu gitu kan ya. Mudah-mudahan bisa memberikan gambaran mengenai algoritma pencarian eh Greedy BFS dan juga A* ya. Nah ini ada perbandingan antara Greedy Best First Search dengan Greedy BFS untuk menemukan tujuan, ya. Eh Anda bisa klik atau bisa berkunjung ke website ini ya, eh untuk melakukan perbandingan itu. Nah, ini perbandingan sekarang Breadth First Search, Greedy BFS dengan A* ya. Ini eh kita bisa eh klik gitu kan ya, eh dan juga bisa lihat hasil perbandingannya seperti apa, ya. Tentunya eh dengan A* nanti ini lebih cepat ya. Teorinya kan begitu seperti tadi sudah didemonstrasikan ya, kalau di eh ini ini eh mencari ya, eh dari titik tertentu ke titik tertentu dalam kotak ini dengan ada obstacle itu mana yang paling cepat ya, nanti Anda bisa bisa coba gitu kan ya, dibandingkan. Oke, baik ini ada beberapa referensi, mungkin teman-teman bisa berkunjung atau bisa membaca kembali ya, terakhir, terima kasih. Semoga video ini bermanfaat, sampai ketemu lagi di lain kesempatan. Assalamualaikum warahmatullahi wabarakatuh.
