Berbagai Teknik Pendekatan Masalah

     Dalam kesempatan ini, kita akan membahas beberapa kasus dan pendekatan yang digunakan untuk menyelesaikannya. Kamu akan belajar mencari alternatif solusi untuk masalah dan membandingkan hasil yang diperoleh dari setiap alternatif.

1. Memilih Jalur Terpendek

     Salah satu kasus klasik yang digunakan sebagai contoh penerapan konsep berpikir komputasional dalam menyelesaikan masalah adalah memilih jalan terpendek untuk mencapai tujuan. Pada kasus ini, terdapat beberapa teknik pendekatan yang umum digunakan. Sebagai contohnya, jika kamu ingin berpergian dari posisi A ke posisi H seperti yang ditunjukkan oleh Gambar dibawah ini
, terdapat beberapa alternatif jalur yang dapat dilalui. Jalur mana yang harus dipilih untuk mencapai rute terpendek?

A. Algoritma greedy

     Algoritme greedy adalah suatu teknik dalam ilmu komputer yang digunakan untuk memecahkan masalah optimasi dengan cara memilih solusi terbaik pada setiap tahapnya hingga mencapai solusi optimal secara keseluruhan. 

     Algoritme greedy melakukan pendekatan dengan cara mengambil keputusan berdasarkan informasi yang ada di setiap langkahnya. Pada setiap langkahnya, algoritme greedy bekerja dengan dua dasar prinsip berikut ini:

(1) Jika dalam setiap langkah yang dilakukan memberikan hasil terbaik, maka hasil keseluruhan adalah yang terbaik.

(2) Algoritme greedy tidak mengenal adanya proses iterasi (perulangan) atau mengubah keputusan yang sudah dibuat Konsep algoritme greedy dapat saja memberikan hasil yang terbaik, tetapi dapat juga memberikan hasil yang kurang baik dibanding dengan pendekatan yang lain.

Sebagai contoh bagaimana pendekatan algoritme greedy bekerja, mari kita lihat kasus pada Gambar di atas di mana kamu ingin pergi dari lokasi A ke I. Pada langkah pertama, kamu harus memilih untuk pergi ke B atau C. Berdasarkan data, jarak ke C adalah jarak yang paling pendek. Oleh karena kamu ingin memilih jarak terpendek, maka kamu akan memilih untuk pergi ke C. Dari C, kamu dapat memilih untuk bergerak ke D atau E. Oleh karena jarak ke D lebih pendek, maka kamu akan memilih untuk pergi ke D. Selanjutnya dari D, kamu dapat memilih untuk bergerak ke F atau G. Karena jarak ke G lebih pendek maka kamu akan memilih jalur G. Selanjutnya dari G, Kamu hanya bisa langsung ke I. Melalui jalur yang dipilih dari A ke C ke D ke G dan I, jarak yang ditempuh adalah 22 km.

     Dari contoh di atas, kita dapat melihat bagaimana algoritme greedy bekerja. Pada kasus ini, apakah algoritme greedy bekerja dengan baik? Apakah jalur yang dipilih merupakan jarak terpendek dari A ke I? Menurut kamu, apakah ada jalur dengan jarak lebih pendek?

B. Algoritma dinamis

     Algoritme dinamis bertujuan untuk menemukan solusi optimal terbaik dari masalah yang ada. Cara yang dilakukan adalah dengan memecah masalah yang kompleks menjadi masalah yang lebih kecil dan sederhana, kemudian mencari solusi untuk setiap masalah kecil tersebut.

     Proses optimalisasi digunakan dalam algoritme dinamis, di mana algoritme ini mencari solusi minimum dan maksimum. Untuk mendapatkan solusi yang optimal, seluruh alternatif solusi yang ada dikumpulkan dan kemudian dipilih solusi terbaik. Berbeda dengan algoritme greedy, pada contoh kasus jalur terpendek, algoritme dinamis akan mengidentifikasi seluruh alternatif jalur yang ada, menghitung masing-masing jalur, dan memilih jalur terpendek.

Pada Gambar, kamu akan memiliki daftar jalur alternatif sebagai berikut:

1. A ke B ke H dan ke I.

2. A ke C ke D ke F ke H dan ke I.

3. A ke C ke D ke G dan ke I.

4. A ke C ke E dan ke I.

Setelah mengidentifikasi semua alternatif jalur yang ada, langkah selanjutnya adalah menghitung jarak masing-masing jalur. Jika dihitung, maka jarak yang perlu ditempuh untuk masing-masing jalur adalah sebagai berikut:

1. A ke B ke H dan ke I = 21 Km.

2. A ke C ke D ke F ke H dan ke I = 25 Km.

3. A ke C ke D ke G dan ke I = 22 Km.

4. A ke C ke E dan ke I = 23 Km.

Dari perhitungan di atas, dapat dilihat bahwa jalur A-C-D-G-I merupakan jalur terpendek dengan jarak tempuh 22 km. Kamu dapat membandingkan bahwa pendekatan menggunakan metode algoritme dinamis merupakan pendekatan yang lebih tepat untuk menyelesaikan kasus mencari jalur terpendek.

Dari contoh di atas, dapat dilihat bahwa algoritme greedy tidak dapat menghasilkan solusi terbaik. Hal ini dikarenakan algoritme greedy tidak menghitung terlebih dahulu hasil akhir sebelum mengambil sebuah keputusan. Keputusan pada setiap langkahnya hanya berdasarkan informasi yang ada pada saat itu. Oleh karena itu, dapat disimpulkan bahwa pada kasus mencari jalur tercepat, algoritme dinamis dapat memberikan hasil yang lebih baik dibanding algoritme greedy.

2. Perjalanan Sales