ANGGOTA KELOMPOK

Kelompok 6

Adhistianita Safira Husna

Membuat algoritma Dynamic Programming, laporan, visualisasi

Siti Vanesa Rahma

Membuat algoritma Brute Force, tahapan dan laporan

Zefanya Darma Putri

Membuat visualisasi, website, analisis dan laporan

Apa ini?

Things You Should Know

Membandingkan 2 algoritma pencarian untuk permainan Word Search. Algoritma tersebut adalah Brute Force dan Dynamic Programming

Brute Force

Brute force adalah metode penyelesaian masalah dengan mencoba semua kemungkinan kombinasi secara sistematis. Ini melibatkan pengujian setiap opsi secara berurutan hingga solusi ditemukan. Meskipun metode ini dapat efektif untuk masalah dengan ruang pencarian kecil, pada kasus yang lebih kompleks, brute force dapat menjadi tidak efisien dan membutuhkan waktu yang lama.

Brute Force code in C++

Dynamic Programming

Dynamic programming adalah metode pemrograman yang digunakan untuk memecahkan masalah kompleks dengan mengingat hasil sebelumnya (memoization). Pendekatan ini menghindari perhitungan berulang pada submasalah yang sama, sehingga dapat mengoptimalkan waktu eksekusi dan mengurangi kompleksitas.

Dynamic Programming code in C++

Word Search

Word search game adalah permainan teka-teki yang mana pemain mencari kata-kata tertentu dalam grid huruf. Mereka harus menemukan kata-kata secara horizontal, vertikal, dan diagonal, baik dari kiri ke kanan maupun sebaliknya. Kata-kata tersembunyi di dalam grid biasanya terkait dengan tema tertentu. Sistem akan menggarisbawahi atau memberi tanda setelah menemukan kata tersebut. Permainan ini digunakan untuk hiburan atau sebagai latihan kejelian baca.

TESTING

Hasil Analisis

  • Brute Force, kompleksitas konstan sebesar O(8*L*M*N) untuk seluruh kasus (worst case hingga best case), yang mana L merupakan target kata yang dicari, M jumlah baris tabel, dan N jumlah kolom tabel
  • Dynamic Programming, pada worst case dan average case memiliki kompleksitas O(8*X*M*N) yang mana X merupakan maksimum kemunculan karakter unik pada target kata (worst case terjadi ketika seluruh karakter pada target kata yang dicari dan grid sama), dan best case O(8*M*N) yaitu ketika seluruh karakter pada kata dan grid merupakan karakter unik

Berdasarkan hasil analisis, dapat disimpulkan bahwa algoritma dynamic programming lebih efisien dari pada Brute Force dalam mencari kata. Selain itu, kompleksitas algoritma Dynamic Programming (O(8*M*N)) juga lebih kecil dibandingkan dengan kompleksitas brute force (O(8*L*M*N)). Hal ini menunjukkan bahwa Dynamic Programming dapat memberikan kinerja yang lebih baik dalam mencari kata pada tabel dengan ukuran dan panjang kata yang sama.

Penutup

Jadi dalam kehidupan ini, belajarlah dari kedua metode tersebut,

Gunakan "brute force" dengan bijak, jangan hanyut dalam kelelahan.

Dan manfaatkan "dynamic programming" untuk mencapai tujuan,

Dengan strategi yang tepat, kehidupan kita akan semakin indah terurai.