halo halo semuanya Masih bersama saya Ulfa dan video ini akan membahas evaluasi kinerja dari teknik pencarian dfs dan pvc untuk menilai seberapa baik suatu teknik pencarian dengan pendekatan pembentukan pohon ruang status terdapat beberapa aspek yang perlu kita lihat yang pertama adalah completeness Hai yang maksudnya adalah menjamin ditemukan solusi jika memang ada yang kedua adalah aspek optimality Apakah teknik pencarian tersebut bisa menjamin untuk mendapatkan solusi yang optimal misalnya nih Apakah kemudian jalur untuk sampai ke solusinya itu memberikan biaya yang paling minimal aspek berikutnya adalah kompleksitas waktu jadi menilai kira-kira berapa lama waktu yang diperlukan untuk mencapai solusi sedangkan aspek yang terakhir adalah kompleksitas ruang untuk menilai Berapa banyak memori yang diperlukan ketika melakukan pencarian ndak untuk menilai aspek-aspek ini nanti kita akan menggunakan beberapa istilah khusus ya yaitu B itu merepresentasikan branching Factor yaitu maksimum percabangan yang mungkin dari suatu simpul kemudian ada De Des kedalaman dari solusi terbaik yaitu solusi dengan cost yang terendah Hai kemudian m itu merepresentasikan maksimum kedalaman dari ruang status dan m ini bisa saja nanti mencapai tak hingga Hai untuk lebih memahami evaluasi kinerja teknik pencarian Mari kita lihat dengan ilustrasi persoalan X puzzle berikut ini terdapat susunan awal yang menjadi ini hillstate atau status awal dari persoalan influenza tampak pada gambar Allah yang diinginkan adalah bagaimana rangkaian aksi memindahkan ubin kosong sedemikian sehingga diperoleh state akhir seperti tampak pada gambar b b Hai nah pada penyusunan pohon ruang status nanti simpul menunjukkan state atau kondisi dimana posisi ubin kosong berada dan pencabangan dari suatu simpul atau state adalah aksi yang mungkin dilakukan untuk memindahkan ubin kosong dari state pada simpul tersebut nah pencabangan atau aksi yang mungkin dilakukan pergerakan obeng kosong adalah of keatas dan kebawah les kekiri dan read ke kanan Hai Berikut ini adalah contoh pohon ruang status untuk permainan ifazo yang status awalnya seperti pada tampilan sebelumnya aksi yang mungkin dari status awal yang menjadi akar pohon adalah untuk memindahkan ubin kosong ke atas kebawah ke kiri atau ke kanan Hai jika sudah diterapkan aksi-aksi tersebut maka status pencarian solusi menjadi seperti simpul-simpul yang ada pada kedalaman satu ini ini memang kita lihat contoh untuk satu simpul yang paling kiri ya as yang mungkin dilakukan untuk state ini adalah memindahkan ubin kosong ke kiri atau ke kanan hai kenapa tidak mungkin ke atas karena sudah tidak ada lagi posisi ketika mobil kosong dipindahkan ke atas dan kenapa tidak melakukan aksi memindahkan Robin kosong ke bawah karena jika memindahkan Ruben kosong kebawah maka dia akan kembali lagi ke situ sebelumnya kejadiannya doa sini yang mungkin maka akan dihasilkan dua state dibawahnya ini adalah Hai karena belum juga solusi maka bisa dibangkitkan lagi state berikutnya Jika masih ada aksi yang mungkin dilakukan hal yang sama untuk simpul-simpul lain pada kedalaman satu Karena dia belum solusi atau state solusi maka dibangkitkan lagi simpul-simpul lain dengan aksi yang mungkin dilakukan untuk state itu sesuai dengan pemahaman pembentukan pohon ruang status tersebut Berikut ini adalah contoh pembentukan pohon ruang statuse puzzle dengan pendekatan bbbs Dimana status awalnya ini sedikit berbeda ya dari contoh kita sebelumnya nah harap diingat untuk pencabangan pohon gunakan urutan asiang konsisten untuk tiap pencabangan yang mungkin pada semua simpul Hai kemudian lihat Hai nomor status pada setiap simpul Hai disini bisa tampak bahwa pembangkitan simpul itu dilakukan setiap kedalaman dalam satu kedalaman bangkitkan semua simpul ya karena disini terlihat urut nomor urutan dari state yang dibangkitkan itu sesuai dengan urutan pembangkitannya ya nomor Sentul ini sesuai dengan urutan pembangkitannya Oke jadi ketika simpul 234 ini ternyata belum ada yang solusi maka kita bangkitkan lagi simpul-simpul berikutnya dibawahnya Hai demikian seterusnya hingga ditemukan state solusi untuk contoh ini berada pada step Hai sehingga solusi dari persoalan edpuzzle ini adalah rangkaian aksi dari step 1 kemudian ketiga lalu 7 lanjut ke-14 lalu ke-26 dan berakhir di 46 ini solusinya adalah rangkaian aksinya jadi rangkaian aksi yang bisa membawa ini skirted ke gold itu adalah rangkaian aksi tab-tab les Hai daun bright begitu ya solusi untuk evaldo dengan menerapkan bbbs berdasarkan ilustrasi dari penyelesaian persoalan puzzle dengan bfs kita lihat propertinya berdasarkan empat aspek yang sudah dibahas di awal pertama komplit Mas Apakah bebs dijamin mendapatkan solusi jawabnya iya selama branching vektornya terbatas artinya kemungkinan aksi yang bisa dilakukan pada suatu step itu terbatas maka ya bfs pasti akan menemukan solusi Hai apakah kemudian solusinya optimal jawabannya ya Jika setiap langkah untuk berpindah dari satu step keset Rikut nya itu dianggap biayanya sama jadi seperti kita lihat di Australia sebelumnya rangkaian aksi dari inisial state sampai goal state untuk BFF pasti didapatkan pada kedalaman yang seminimal mungkin dia pasti menemukan solusi sehingga jika nanti setiap langkah dianggap piringnya sama pasti dia akan menemukan solusi pada jumlah langkah yang paling sedikit Hai kemudian kompleksitas waktunya Oke untuk setiap kedalaman kita memerlukan waktu untuk membangkitkan simpul-simpul nya ya sehingga pada kedalaman D yaitu de itu adalah kedalaman dimana solusi itu berada maka kompleksitas waktu yang diperlukan adalah B pangkat D Sedangkan untuk kompleksitas ruangnya karena kita perlu membangkitkan semua simpul pada suatu kedalaman dan kita menemukan solusi yaitu pada kedalaman J maka kompleksitas ruang yaitu adalah B pangkat c tidak cukup baik nanti akan kita lihat perbaikan yang mungkin bisa dilakukan untuk kompleksitas ruang ini nah ini adalah properti dari penyelesaian persoalan dengan memanfaatkan teknik bebs Hai Sekarang mari kita lihat jika kita menggunakan pendekatan gbft untuk menyelesaikan permainan ini Plaza nomor pada tiap simpul sama seperti sebelumnya yang menyatakan urutan pembangkitan simpulnya Hai dengan kedalaman di sini kita batasi hanya 12345 kedalaman saja ya untuk menyederhanakan pengontrol status nah solusi Ditemukan saat membangkitkan simpul Hai sehingga jalurnya itu adalah satu 18 28 29 30 31 dengan rangkaian aksinya adalah up up left down right Hai Nah dari ilustrasi tadi kita lihat properti dari dfc yang pertama adalah completeness Apakah dijamin dfs bisa mendapatkan solusi jawabannya ya selama branching vektornya terbatas kemudian ada tambahan Taman penanganan ya Jadi ada penanganan untuk redha dan pas jadi kalau sudah ada jalur yang mengarah pada sheet yang sudah pernah dilalui sebelumnya maka itu tidak akan dilakukan lagi dan juga ada penanganan untuk Raffi tes tes Jadi kalau dari setiap ini sebetulnya sudah dibangkitkan nih dari jalur yang lain maka kita melakukan penanganan untuk tidak membangkitkan state itu lagi maka ya jika ada penanganan tersebut maka deface bisa dijamin mendapatkan solusi Hai kemudian Apakah solusinya Optima nah ini belum tentu bukan berarti selalu tidak ya tapi belum tentu Kenapa karena seperti kita ketahui deface itu melakukan pencarian secara mendalam jadi Mungkin saja dia menemukan solusi tapi setelah melakukan langkah-langkah yang cukup panjang Karena dia memeriksa dulu kedalamannya baru memeriksa ke melebar Oke beda dengan Brad versus yang melakukan pencarian secara melebar jadi disini optimal belum tentu dia ya Hai Kemudian untuk kompleksitas waktunya maka karena kedalaman maksimum itu adalah M maka kompleksitas waktunya B pangkat n karena dalam setiap kali dia menemukan sebuah simpul yang bukan solusi maka dia harus membangkitkan pencabangan anak-anaknya untuk kemudian diperiksa ya sehingga ketika dia nanti dibatasi pada proses pencariannya kedalaman maksimum adalah M maka dia mungkin sampai kedalaman maksimum dulu baru menemukan solusi atau justru tidak menemukan solusi untuk kemudian bakted ya jadi kompleksitas waktunya darah B pangkat m Sedangkan untuk kompleksitas ruangnya disini dia cukup bagus yaitu karena apa dalam satu kedalaman dia tidak perlu kemudian membangkitkan semua simpul pada uang tersebut tapi hanya yang perlu diekspos saja dari step sebelumnya yaitu sehingga disini kompleksitas ruangnya adalah BM BP adalah prinsip vektornya m adalah kedalaman maksimumnya jadi untuk kompleksitas ruangnya dia lebih bagus daripada bhvhv dari sini nanti kita akan melihat bagaimana kalau misalnya yang baik dari bfs kemudian yang baik dari dfs bisa kita manfaatkan untuk kemudian mendapatkan solusi yang relatif optimal Hai demikian video mengenai evaluasi kinerja teknik pencarian dengan pdfs atau BFF berikutnya kita akan membahas backtracking dalam dave's Selamat belajar ya