Strategi Problem Solving: Brute Force, Means-End Analysis, dan Hill Climbing

Gambaran Besar Dulu

Bayangin kamu lagi mau pergi ke sekolah dari rumah. Ada 4 persimpangan yang bisa kamu lewati, dan masing-masing bisa dikombinasikan jadi berbagai rute. Pertanyaannya: rute mana yang paling pendek?

Nah, cara kita nyari jawaban itu ternyata beda-beda. Ada yang nekat nyoba satu per satu. Ada yang berpikir strategis. Ada yang ambil jalan yang “kelihatan bagus” tapi ternyata salah pilihan.

Tiga cara itulah yang akan kita bahas: Brute Force, Means-End Analysis, dan Hill Climbing.

Ketiganya masuk kategori strategi heuristik, artinya: tidak ada jaminan 100% selalu menemukan solusi terbaik dalam semua situasi. Tapi masing-masing punya keunggulan tersendiri.

Strategi 1: Brute Force — “Coba Semua, Tanpa Terkecuali”

Analoginya

Kamu lupa PIN HP sendiri. Yang kamu ingat cuma panjangnya 4 digit. Apa yang kamu lakukan? Coba 0000, 0001, 0002… terus sampai ketemu. Itu Brute Force.

Cara Kerjanya (Step by Step)

1. Buat daftar semua kemungkinan solusi yang ada.
2. Coba solusi pertama. Apakah ini yang benar?
3. Kalau tidak, coba solusi berikutnya.
4. Ulangi sampai solusi yang benar ditemukan.

Diterapkan ke Soal Rute

Katakanlah dari rumah ke sekolah ada 4 persimpangan: A, B, C, D. Semua kemungkinan rute yang bisa dilalui:

• Rumah → A → B → Sekolah
• Rumah → A → C → Sekolah
• Rumah → B → D → Sekolah
• Rumah → C → D → Sekolah
• … dan seterusnya

Brute Force mencatat jarak semua rute itu, lalu memilih yang paling pendek. Hasilnya pasti benar. Tapi kalau persimpangannya ada 100? Bisa ratusan ribu kombinasi yang harus dicek. Lama banget.

Jebakan Umum

• Aman dan pasti menemukan solusi optimal, tapi sangat lambat untuk masalah yang besar.
• Makin banyak pilihan → makin lama waktunya. Ini yang disebut exponential growth (waktu bertambah sangat cepat seiring bertambahnya pilihan).

Strategi 2: Means-End Analysis — “Fokus ke Perbedaan, Kurangi Selisihnya”

Analoginya

Kamu di kamar (posisi sekarang) dan mau ke kantin (tujuan). Kamu sadar kamar dan kantin dipisahkan oleh tangga. Jadi langkah pertama: cari tangga, turun. Setelah di bawah, ada jarak baru ke kantin. Langkah berikutnya: jalan ke arah kantin. Terus begitu sampai sampai.

Cara berpikir ini adalah: lihat jarak antara posisi sekarang dan tujuan, lalu ambil langkah yang paling mengecilkan jarak itu.

Cara Kerjanya (Step by Step)

1. Identifikasi posisi saat ini — kamu ada di mana sekarang?
2. Identifikasi tujuan — kamu mau ke mana?
3. Cari perbedaannya — apa yang memisahkan posisimu dari tujuan?
4. Pilih tindakan yang paling banyak mengurangi perbedaan itu.
5. Ulangi dari langkah 1 dengan posisi yang sudah diperbarui.

Diterapkan ke Soal Rute

• Posisi sekarang: Rumah (jarak ke sekolah = 2 km)
• Tujuan: Sekolah (jarak = 0)
• Di depan ada dua pilihan: belok kiri lewat A (jarak tersisa jadi 1,4 km) atau lurus lewat B (jarak tersisa jadi 1,8 km).
• Pilih lewat A karena mengurangi jarak lebih banyak.
• Sekarang posisi di A. Ulangi proses yang sama.
• Terus begitu sampai tiba di sekolah.

Jebakan Umum

• Strategi ini bisa tidak optimal kalau ada rute yang sebentar jauh tapi akhirnya lebih pendek (misalnya, jalan memutar sedikit tapi menghindari kemacetan parah).
• Terkadang “mengurangi perbedaan sekarang” bukan berarti “pilihan terbaik jangka panjang.”

Strategi 3: Hill Climbing — “Selalu Naik, Pilih yang Lebih Tinggi”

Analoginya

Bayangin kamu buta dan dilepas di pegunungan. Tugasmu: cari puncak tertinggi. Caramu? Tiap langkah, kamu raba tanah sekitar — mana yang lebih tinggi, ke sana kamu melangkah. Terus sampai tidak ada lagi yang lebih tinggi di sekitarmu.

Masalahnya: bisa jadi kamu ada di bukit kecil, bukan gunung utama. Kamu berhenti karena merasa sudah di puncak, padahal ada gunung yang jauh lebih tinggi di sebelah sana.

Cara Kerjanya (Step by Step)

1. Mulai dari posisi awal.
2. Lihat semua langkah yang tersedia dari posisi ini.
3. Pilih langkah yang membuat kita paling dekat ke tujuan (atau paling “tinggi” dalam konteks optimasi).
4. Pindah ke posisi baru itu.
5. Ulangi sampai tidak ada langkah yang lebih baik lagi.

Kenapa Hill Climbing Bisa Gagal?

Ini inti dari diskusi yang perlu dipahami betul.

Ada situasi yang disebut local maxima (puncak lokal). Ini adalah posisi yang lebih baik dari semua posisi di sekitarnya, tapi bukan yang terbaik secara keseluruhan.

Gambaran sederhananya seperti ini:

         /\        /\
        /  \      /  \
       /    \    /    \
------/      \--/      \-------
    Bukit    Lembah   Gunung
    kecil              besar

Kalau kamu mulai dari sebelah kiri, Hill Climbing akan membawa kamu ke puncak bukit kecil. Di sana, semua langkah sekitar lebih rendah, jadi algoritma berhenti. Padahal ada gunung besar di sebelah kanan yang jauh lebih tinggi.

Itulah local maxima problem — terjebak di solusi yang “terlihat terbaik” padahal bukan yang optimal.

Perbandingan Ketiga Strategi

Latihan Langsung

Latihan Brute Force

Dari rumah ke sekolah ada 4 persimpangan: A, B, C, D. Jarak tiap segmen:

• Rumah → A = 500 m
• Rumah → B = 300 m
• A → C = 400 m
• B → C = 600 m
• A → D = 700 m
• B → D = 200 m
• C → Sekolah = 300 m
• D → Sekolah = 500 m

Tugas: hitung semua rute yang mungkin dan tentukan yang terpendek.

• Rute 1: Rumah → A → C → Sekolah = 500 + 400 + 300 = 1.200 m
• Rute 2: Rumah → A → D → Sekolah = 500 + 700 + 500 = 1.700 m
• Rute 3: Rumah → B → C → Sekolah = 300 + 600 + 300 = 1.200 m
• Rute 4: Rumah → B → D → Sekolah = 300 + 200 + 500 = 1.000 m ✓ (terpendek)

Latihan Means-End Analysis

Dari posisi awal (Rumah), kamu punya dua pilihan langkah pertama: ke A (sisa jarak ke sekolah menjadi 1.100 m) atau ke B (sisa jarak menjadi 700 m). Langkah mana yang dipilih Means-End Analysis? Ke B, karena mengurangi jarak paling banyak. Dari B, pilihan berikutnya: ke C (sisa 300 m) atau ke D (sisa 500 m). Pilih ke C. Hasil akhir: 1.200 m — bukan yang terpendek! Padahal Brute Force menemukan 1.000 m. Ini contoh nyata Means-End Analysis tidak selalu optimal.

Tiga Pertanyaan Kuis

1. Sebuah brankas punya kode 3 digit angka (0-9). Berapa banyak kemungkinan kombinasi yang harus dicoba kalau menggunakan metode Brute Force?

2. Dalam Means-End Analysis, apa yang dilakukan pertama kali sebelum menentukan langkah berikutnya?

3. Jelaskan dengan kata-katamu sendiri apa yang dimaksud “local maxima” dalam Hill Climbing, dan mengapa itu menjadi masalah!