Combinatorial problems adalah jenis permasalahan yang berhubungan dengan objek-objek dengan jumlah yang terbatas. "Combinatorial" mengacu pada penyusunan item-item. Combinatorial problems, merupakan permasalahan yang paling sulit diselesaikan baik secara teori maupun dalam prakteknya. Salah satu contoh permasalahan kombinatorial yang cukup terkenal adalah Traveling Salesman Problem atau disingkat TSP dan Knapsack Problem.
Rute terpendek sudah pasti dapat ditemukan dengan menggunakan metode brute-force atau exhaustive search, yaitu dengan mencoba setiap kemungkinan rute yang ada lalu mengukur total jarak dan membandingkan dengan jarak terpendek yang ditemukan sebelumnya. Metode brute-force memiliki kelemahan yaitu memerlukan waktu dan proses komputasi yang tidak efektif atau lambat bahkan untuk jumlah lokasi yang relatif sedikit karena memiliki kompleksitas O(n!). Sebagai contoh, untuk 7 titik lokasi dimana satu lokasi merupakan tempat awal, maka diperlukan 7! = 5040 proses evaluasi.
Traveling Salesman Problem
Traveling Salesman Problem atau TSP adalah permasalahan yang cukup terkenal di bidang sains komputer. Skenario dari permasalahan ini adalah ketika seorang penjual keliling (salesman) yang berdagang harus menghampiri setiap lokasi yang ada sebanyak satu kali setiap lokasi dan kembali ke lokasi awal. Penjual haris menentukan rute mana yang paling efektif untuk setiap lokasi yang didatangi dan kembali. Semakin pendek rute yang ditempuh tentu semakin baik. Untuk menemukan rute terpendek dari sejumlah lokasi merupakan permasalahan eksponensial yang rumit, menentukan rute terpendek dari 20 lokasi lebih dari 2x lipat lebih sulit dari 10 lokasi.Rute terpendek sudah pasti dapat ditemukan dengan menggunakan metode brute-force atau exhaustive search, yaitu dengan mencoba setiap kemungkinan rute yang ada lalu mengukur total jarak dan membandingkan dengan jarak terpendek yang ditemukan sebelumnya. Metode brute-force memiliki kelemahan yaitu memerlukan waktu dan proses komputasi yang tidak efektif atau lambat bahkan untuk jumlah lokasi yang relatif sedikit karena memiliki kompleksitas O(n!). Sebagai contoh, untuk 7 titik lokasi dimana satu lokasi merupakan tempat awal, maka diperlukan 7! = 5040 proses evaluasi.
 |
| Metode brute-force dalam mencari jarak terpendek |
Knapsack Problem
Permasalahan lain yang cukup dikenal dan termasuk combinatorial problem adalah knapsack problem atau rucksack problem. Terdapat sejumlah barang masing-masing dengan berat dan nilainya, dimasukan ke sebuah ransel yang memiliki kapasitas berat maksimum. Maka perlu dicari barang apa saja yang dapat dimasukan ke dalam ransel sehingga barang yang dibawa memiliki total nilai tertinggi tanpa melebihi kapasitas ransel. |
| Knapsack problem |
Aplikasi
Berikut beberapa contoh pengaplikasian dari optimasi combinatorial optimization :- Menentukan rute optimal untuk mengantarkan paket ke beberapa tempat.
- Menentukan armada taksi mana yang terdekat untuk menjemput penumpang.
- Mengembangkan jaringan atau jalur-jalur penerbangan penerbangan.
- Vehicle Routing.
0 komentar:
Posting Komentar