Combinatorial problem merupakan suatu
permasalahan matematis untuk menyusun, mengelompokkan,
mengurutkan, atau memilih sejumlah objek diskrit tertentu.
Sampai saat ini, combinatorial problem masih menjadi salah
satu bidang yang sering diteliti karena dengan semakin berkembangnya ilmu pengetahuan
diharapkan akan ditemukan metode-metode maupun pendekatan pendekatan baru yang bisa menjadi
sebuah cara penyelesaian terbaik untuk permasalahan
ini. Ini adalah masalah yang meminta.
Secara eksplisit atau implisit, untuk mendapati objek kombinatorial seperti permutasi sebuah komputasi, kombinasi, atau bagian yang terpenuhi kendala tertentu. Sebuah diinginkan objek kombinatorial juga mungkin diperlukan untuk memiliki beberapa properti tambahan seperti sebagai nilai maksimum atau biaya minimum. Secara umum, masalah kombinasi yang paling sulit di komputasi, baik dari sudut pandang teoritis dan praktis. Kesulitan untuk membuktikan fakta-fakta berikut. Pertama, jumlah objek kombinatorial biasanya tumbuh sangat cepat dengan ukuran masalah, mencapai besaran yang tak terbayangkan bahkan untuk contoh berukuran sedang. Kedua, tidak ada algoritma untuk memecahkan sebagian besar masalah tersebut persis dalam jumlah yang diterima waktu. Selain itu, sebagian besar ilmuwan komputer percaya bahwa algoritma tersebut tidak ada. Dugaan ini memiliki telah tidak terbukti atau tidak terbukti, dan tetap belum terpecahkan yang paling penting masalah dalam ilmu komputer teoritis.
Secara eksplisit atau implisit, untuk mendapati objek kombinatorial seperti permutasi sebuah komputasi, kombinasi, atau bagian yang terpenuhi kendala tertentu. Sebuah diinginkan objek kombinatorial juga mungkin diperlukan untuk memiliki beberapa properti tambahan seperti sebagai nilai maksimum atau biaya minimum. Secara umum, masalah kombinasi yang paling sulit di komputasi, baik dari sudut pandang teoritis dan praktis. Kesulitan untuk membuktikan fakta-fakta berikut. Pertama, jumlah objek kombinatorial biasanya tumbuh sangat cepat dengan ukuran masalah, mencapai besaran yang tak terbayangkan bahkan untuk contoh berukuran sedang. Kedua, tidak ada algoritma untuk memecahkan sebagian besar masalah tersebut persis dalam jumlah yang diterima waktu. Selain itu, sebagian besar ilmuwan komputer percaya bahwa algoritma tersebut tidak ada. Dugaan ini memiliki telah tidak terbukti atau tidak terbukti, dan tetap belum terpecahkan yang paling penting masalah dalam ilmu komputer teoritis.
Contoh combinatorial problem adalah
travelling salesman problem, knapsack problem, dan vehicle routing
problem.
- Vehicle Routing Problem (VRP) merupakan permasalahan m-travelling salesman. Dalam permasalahan ini, terdapat m-salesman yang berangkat dari suatu kota kemudian melakukan kunjungan ke sejumlah kota. Setiap kota hanya dapat dikunjungi oleh satu salesman saja. Tujuan utamanya adalah meminimalkan total jarak atau total biaya perjalanan. VRP merupakan permasalahan klasik yang sangat dekat dengan kehidupan manusia. Contoh permasalahan yang dapat diselesaikan dengan pendekatan VRP adalah penentuan rute pengiriman surat, laundry, dan koran. Sampai saat ini, sudah banyak algoritma heuristik yang dihasilkan dari penelitian-penelitian untuk menyelesaikan permasalahan VRP, diantaranya adalah genetic algorithm, tabu search, simulated annealing, dan ant colony. Dalam prosesnya, meski-pun memberikan hasil yang memuaskan, algoritma algoritma penyelesaian tersebut memiliki beberapa parameter tertentu. Jika nilai parameter-parameter tersebut diubah, maka hasil penyelesaiannya akan berbeda. Sampai saat ini penelitian untuk permasalahan VRP masih terus dilakukan karena masih belum ada algoritma heuristik yang konsisten untuk memberikan hasil terbaik.
sumber : buku Anany Levitin
10115448
0 comments:
Posting Komentar