7 Cara Mencari Solusi
Terkait teknologi, beberapa pertanyaan muncul: bagaimana bisa Google Maps mengetahui rute terbaik untuk penggunanya? Bagaimana bisa bot pada permainan catur mengetahui langkah yang tepat untuk setiap giliran, bergantung pada levelnya? Salah satu hal penting yang mereka lakukan adalah mencari solusi. Bentuk solusi bergantung pada permasalahan sehingga dapat bervariasi, seperti rute, pilihan, dan aksi. Ada juga masalah yang ingin mencari solusi terbaik, misalnya rute terpendek, aksi dengan kemungkinan menang tertinggi, dan lain-lain.
Ingatlah pepatah banyak jalan menuju Roma. Terdapat berbagai cara untuk mencari solusi untuk berbagai masalah. Bukti? Kita akan lihat untuk tiga cara pertama dalam menyelesaikan maze (labirin). Kemudian, sisanya dapat dikatakan sebagai cara tambahan yang akan berguna untuk beberapa masalah yang akan disebutkan pada bagian tersebut.
Apa sih cara-caranya? Singkatnya, ini:
- BFS (Breadth-First Search)
- DFS (Depth-First Search)
- Greedy
- Hill climbing
- Genetik
- Online
- Adversarial
Semua istilah berbahasa Inggris, tetapi artinya make sense. Saya akan membahas satu per satu.
Sebelum menjelaskan cara pertama dan kedua, ini adalah maze yang saya gunakan:
Petak biru menunjukkan posisi pemain sekarang. Petak hijau, tentunya, menunjukkan petak yang ingin dituju, atau goal. Petak merah menunjukkan posisi awal.
BFS (Breadth-First Search)
Selah satu terjemahan breadth adalah ‘lebar.’ Jadi, BFS dapat dikatakan sebagai pencarian yang memprioritaskan lebarnya dulu. Pencarian yang lebar memungkinkan jarak yang paling dekat lebih didahulukan dulu. Jadi kayak … tidak perlu cari jauh-jauh kalau ada yang dekat. Caranya sederhana, kunjungi yang paling dekat dulu. Tentunya yang terlalu jauh tidak usah dieksekusi. Gambar ini menunjukkan hal yang saya maksud.
Pada bagian 2 terdapat dua jalan: ke atas dan ke kanan. Jadi, pemain berpecah menjadi dua untuk kedua arah tersebut dan mereka saling bergantian dalam berjalan. Hasilnya terlihat pada gambar 4. Pada gambar 5, 6, dan 7, terlihat bahwa semua pemain mencapai petak masing-masing tidak lebih dari tiga aksi. Dapat dikatakan bahwa BFS ini dapat digunakan untuk mencari banyak aksi minimum juga. Namun, ingat. Semakin banyak pemain, semakin rumit, hehe.
Intinya: BFS mencari yang terdekat terlebih dahulu (dengan cara melebar).
DFS (Depth-First Search)
Mengapa perlu menjalankan pemain lain jika pemain yang dijalankan saat ini masih memungkinkan? Itulah yang dilakukan oleh DFS. Depth berarti ‘kedalaman.’ Artinya, yang didahulukan adalah pencarian yang lebih dalam, tidak peduli seberapa jauh. Pencariannya dilihat dari gambar di bawah ini:
“Wait, sesimpel itu?”
Yep, tetapi hal itu terjadi kalau prioritas utamanya ke atas dan kebetulan goal-nya tinggal ke atas terus saja. Perhatikan bahwa masih ada pemain yang lebih dekat yang dapat bergerak, tetapi diabaikan.
Namun, kalau prioritas utamanya adalah ke kanan, pencariannya bakalan beda. Lihat gambar di bawah ini yang juga menggunakan DFS:
(Bagian 10 hingga 15 tidak digambar karena kebanyakan.) Lihat, dia mengitari semua jalan buntu dari maze! Terlihat pada bagian ke-16, pemain yang lebih jauh dijalankan terlebih dahulu daripada yang sudah jelas-jelas dekat dengan goal. Itulah ciri khas DFS. Dapat dikatakan bahwa DFS belum tentu mencari jalan yang cepat layaknya BFS karena ya … dia memprioritaskan kedalaman.
Intinya: DFS mencari hal yang lebih dalam terlebih dahulu.
Masalah dari BFS dan DFS adalah dia berprioritas kepada arah, bukan goal. Mereka hanya mencari apapun yang mereka dapatkan. Itulah yang disebut pencarian buta karena dia tidak mengetahui apapun tentang aksi yang lebih dekat dengan goal.
Greedy
Daripada hanya asal, memperkirakan jarak goal dari pemain sebelum melakukan pencarian adalah hal yang baik. Sebagai pengganti arah, perkiraan tersebutlah yang dijadikan prioritas, yaitu perkiraan jarak yang terdekat. Itulah yang disebut greedy, yang berarti ‘rakus.’ Dia akan menjalankan pemain ke tempat yang lebih dekat dengan solusi. Jika menggunakan maze yang sama untuk DFS dan BFS, langkahnya sama dengan DFS prioritas ke atas.
Namun, jika maze-nya beda, pemain rakus dapat dijebak. Lihat ini:
(Yang saya gunakan adalah jarak Manhattan, yaitu jumlah jarak horizontal dan vertikal. Pythagoras kurang berguna di sini.) Pada bagian 3, pemain lebih memilih bergerak ke atas karena lebih dekat dengan goal. Namun, justru goal tidak bisa ditemukan jika bergerak ke arah tersebut. Itulah jebakannya. Namun, menurut saya, setidaknya ini lebih pintar daripada DFS.
Intinya: greedy selalu ingin yang terdekat setiap langkahnya.
Hill Climbing
Bagaimana cara meraih puncak dari suatu bukit? Tinggal ikuti saja kan datarannya: kalau masih ada tanjakan, berarti belum di puncak. Kalau sudah tidak ada tanjakan, yay! Puncak ditemukan! Secara tidak langsung, pencarian dengan hill climbing telah digunakan. Kan arti dari namanya saja itu ‘mendaki bukit.’
Meskipun namanya seperti itu, bukan berarti masalahnya harus mengenai bukit. Physical distancing, misalnya, yang perlu dilakukan saat berada di tempat umum. Tentunya, pada masa pandemi ini, semakin banyak orang yang berada di dekat kita, semakin berpotensi kita terjangkit virus. Jadi, yang perlu dilakukan adalah berjalan ke tempat yang lebih sedikit keramaiannya. Kalau misalnya sudah tidak ada, dapat dikatakan itu sebagai tempat yang cukup aman untuk kita. Namun, sebenarnya itu belum dapat dikatakan tempat teraman. Kembali ke bukit, jika kita mencapai puncak, bukan berarti puncak tersebut adalah puncak tertinggi, tetapi hanya sebagai tempat yang tertinggi dibandingkan sekitarnya.
Meskipun demikian, that’s okay. Setidaknya solusi yang ditemukan lebih baik. In a nutshell, konsep seperti ini juga dapat digunakan untuk kecerdasan buatan (nama kerennya artifical intelligence, atau AI) untuk optimisasi.
Intinya: hill climbing mencari solusi dengan “tanjakan” sehingga mencapai puncak. (Sebenarnya untuk mencari jurang juga bisa sih dengan mencari turunan, haha.)
Genetik
Tahu pewarisan silang? Hanya dengan menggabungkan dua tumbuhan berspesies sama tetapi variasinya beda, tumbuhan yang lebih unggul dapat muncul. Cara ini juga dapat digunakan untuk mencari solusi untuk beberapa masalah, misalnya menyelesaikan suatu level dalam permainan, gerakan robot yang optimal, dan menyimulasikan seleksi alam. Untuk memperluas pencarian, terdapat faktor mutasi yang membuat perilaku dari spesies berbeda. Cek video dari Primer di bawah ini jika punya waktu. Video tersebut lebih baik dalam menjelaskan simulasi seleksi alam.
Intinya: genetik menggabungkan dua spesies dan bermutasi untuk mencari spesies yang lebih unggul sebagai solusi.
Online
Pencarian secara online bukan berarti harus ada kuota internet dulu lalu bisa mencari solusi. Sejauh ini, kita mencari solusi dengan cara memikirkan yang ingin dilakukan terlebih dahulu agar solusi dapat ditemukan. Jika permasalahannya kompleks, kita berikan cara-cara tersebut kepada komputer.
Bagaimana jika kita biarkan komputer tersebut juga mencari solusinya? Kita tinggal beritahukan masalah kita kepada komputer. Itulah yang disebut pencarian secara online karena terdapat eksplorasi untuk mendapatkan solusinya dilakukan secara real-time. Dengan kata lain, komputer masuk ke lingkungan yang … dia tidak tahu itu apa … kemudian disuruh mencari solusinya. Ajaibnya, itu bisa. Rekomendasi YouTube salah satunya yang memberikan daftar video yang berpotensi relevan untuk kita.
Namun, komputer tentunya tidak langsung dapat menemukan solusi yang tepat. Layaknya manusia, komputer perlu belajar agar bisa tahu hal yang dilakukan pada lingkungan asing tersebut. Di sinilah peran kecerdasan buatan di sini. Secara singkat, ada banyak macam cara belajar. Misalnya berdasarkan umpan balik, ada yang perlu diberitahukan bahwa ini benar atau salah untuk setiap aksinya (reinforcement learning), ataupun ada yang diberikan data-data awal saja (supervised dan unsupervised learning). Hanya saja … pastikan berikan batasan kepada komputer karena bisa saja komputer mengendalikan kita, hoho ….
Intinya: pencarian secara online memungkinkan ditemukannya solusi dengan mengeksplorasi lingkungan yang belum diketahui sebelumnya.
Adversarial
Suka main catur? Atau permainan apapun yang melibatkan pertarungan? Bagaimana cara memenangkannya? Pencarian untuk kemenangan ini disebut pencarian adversarial yang berarti ‘bermusuhan,’ atau dapat dikatakan kompetitif.
Salah satu cara dari pencarian ini adalah mencari langkah yang paling menguntungkan untuk kita sehingga musuh hanya dapat bergerak dengan gerakan yang membuat kemungkinan kalah kecil. Misalkan dalam catur, saat ingin mengeskak, perlu ada bidak musuh lain yang dapat dimakan pada gerakan selanjutnya agar langkah kita menguntungkan. Dalam congklak, menembak ke lubang musuh dengan benih yang banyak akan memperbesar kemungkinan dalam memenangkan permain, tetapi perlu berhati-hati juga agar tidak sebaliknya. Dalam UNO, menyimpan kartu-kartu spesial seperti plus-two (+2) atau plus-four (+4) akan berguna untuk menangkis serangan musuh yang menurunkan kartu tersebut.
Akan tetapi, menurut saya, dampak negatif dari ditemukannya solusi yang membuat pemain tak terkalahkan adalah permainannya berpotensi besar ditinggalkan. Pikirkan bahwa … untuk apa memainkan permainan tersebut jika sudah ada “cheat”-nya sehingga sudah jelas selalu kalah? Tic-tac-toe, misalnya, yang menemukan cara agar pemain pertama tidak pernah kalah. Selain itu, saya juga pernah temukan cheat untuk congklak dengan tujuh lubang untuk masing-masing pemain, terdiri dari tujuh benih untuk masing-masing lubang, sehingga jika pemain pertama melakukan aksi-aksi dari cheat tersebut, lawannya akan kalah tanpa melakukan apapun. Tentunya itu sangat merugikan untuk permainan congklak jika itu diketahui oleh orang banyak. Agar hal itu terjadi, permainan perlu bervariasi agar cheat-nya sulit ditemukan. Saya berharap bagi pembaca yang tahu cheat-nya, jangan disalahgunakan.
Intinya: pencarian adversarial melibatkan lawan, atau terdiri dari lebih dari satu pemain.
Dari mana materi ini?
Jika pembaca membaca artikel ini, pembaca juga mempelajari hal-hal terkait kecerdasan buatan, atau AI. Mengapa?
Kebanyakan materi yang saya tulis berasal dari buku Artificial Intelligence: A Modern Approach (edisi ketiga) dari Stuart Russell dan Peter Norvig. Untuk bacaan lebih lanjut, coba cek bab 3 hingga bab 5 pada buku tersebut. Jenis-jenis pencarian dari buku tersebut bahkan lebih dari tujuh macam. Selain itu, saya juga sempat menyinggung beberapa macam cara belajar untuk komputer, tetapi sudah di luar topik jika ingin lebih dalam membahasnya. (dan saya masih noob tentang itu, huhu …) Biasanya mereka yang muncul saat mencari jenis-jenis machine learning (pembelajaran mesin) di Google. Jenis-jenis ini juga sebenarnya ada di buku tersebut pada bab 18.
