Masalah Kombinasional

Masalah Kombinasional

Pengertian Kombinasional

Kombinasional adalah salah satu cabang dari matematika dalam bidang ilmu matetmatika diskrit yang bertujuan untuk menghitung jumlah penyusunan objek-objek tanpa mengenumerasi kemungkinan susunannya.

jadi dapat disimpulkan, Combinatorial problem merupakan suatu permasalahan matematis untuk menyusun, mengelompokkan, mengurutkan, atau memilih sejumlah objek diskrit tertentu. Dan sampai saat ini, combinatorial problem masih menjadi salah satu masalah yang paling sulit dalam komputasi baik itu dari teori maupun prakteknya. Maka dari itu Combinatorial 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.

Kesulitan dari masalah Kombinasional antara lain :

Sejumlah objek combinatoric tertentu berkembang seiring dengan meningkatnya ukuran masalah.
Tidak diketahui algoritma pasti yang dapat digunakan untuk menyelesaikan permasalahan masalah kombinasional

Tipe Masalah Kombinasional :

Masalah : Menemukan suatu objek combinatoric seperti permutasi, kombinasi atau subset yang memenuhi batasan tertentu dan memiliki properti yang diinginkan.
Masalah yang sulit :
- Sejumlah objek combinatorikctertentu tumbuh dengan cepat seiring peningkatan ukuran masalah.
- Tidak diketahui algoritma eksak untuk menyelesaikan masalah tersebut.

beberapa permasalahan combinatorial problem dapat diselesaikan menggunakan algoritma yang efisien, akan tetapi tetap harus mengikuti aturan-aturannya. Berikut ini adalah beberapa contoh kasus dari combinatorial problem :

Vehicle Routing Problem (VRP), merupakan sebuah cakupan masalah yang didalamnya terdapat sebuah problem dimana ada sejumlah rute untuk sejumlah kendaraan yang berada pada satu blok atau lebih yang harus ditentukan jumlahnya supaya tersebar secara geografis sehingga dapat melayani konsumen-konsumen yang tersebar. VRP memiliki tujuan yaitu mengantarkan barang pada konsumen dengan biaya minimum melalui rute-rute kendaraan yang keluar-masuk blok. VRP merupakan sebuah pemrograman integer yang termasuk dalam kategori NP-hard problem, yang berarti usaha komputasi yang digunakan akan semakin sulit seiring meningkatnya ruang lingkup masalah. Untuk Masalah-masalah seperti ini, biasanya dicari adalah aproksimasi solusi masalah yang terdekat, karena solusi tersebut dapat dicari dengan cepat dan akurat. Biasanya masalah seperti ini dapat terselesaikan dengan melakukan pengamatan pada ruang lingkup masalah.
Travelling Salesman Problem (TSP), Merupakan masalah kombinasi optimasi dalam menemukan tour yang terpendek. TSP adalah problem untuk menentukan urutan kota yang harus dilalui salesman, setiap kota hanya boleh dilalui satu kali dalam setiap perjalanannya, dimana jarak antara kota satu dengan kota yang lainnya sudah diketahui. Salesman tersebut harus meminimalisir biaya dan dan jarak yang harus di tempuh dalam perjalanan tersebut.

Pengertian Kombinasional

Referensi

Share this