Combinatorial problem

Dari perspektif yang lebih abstrak, TSP dan GCP adalah contoh dari masalah kombinatorial. Ini adalah masalah yang meminta secara eksplisit atau implisit untuk menemukan benda seperti kombinatorial sebagai permutasi, kombinasi, atau bagian yang memenuhi kendala tertentu. Sebuah objek kombinatorial yang diinginkan juga mungkin diperlukan untuk memiliki beberapa properti tambahan seperti sebagai nilai maksimum atau biaya minimum.

Secara umum, masalah kombinatorial adalah masalah yang paling sulit dalam komputasi, baik dari sudut pandang teoritis dan praktis. kesulitan mereka berasal dari 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. Selain itu, sebagian besar ilmuwan komputer percaya bahwa algoritma tersebut tidak ada. Dugaan ini telah terbukti atau tidak terbukti, dan itu tetap menjadi isu yang belum terselesaikan yang paling penting dalam ilmu komputer teoritis.

Beberapa masalah kombinasi dapat diselesaikan dengan algoritma efisien, tetapi mereka harus dipertimbangkan pengecualian beruntung aturan.

Atau dapat disimpulkan :

• ·         Problem: menemukan suatu objek kombinatorik–seperti permutasi, kombinasi, atau subset – yang memenuhi batasan-batasan tertentu dan memiliki properti yang diinginkan
• ·         Problem-problem paling sulit :

o   Sejumlah objek kombinatorik tertentu tumbuh dengan cepat seiring peningkatan ukuran problem

o   Tidak diketahui algoritma eksak untuk menyelesaikan problem tersebut dalam waktu yang diinginkan

• ·         Dari perspektif yang lebih abstrak, TSP & GCP merupakan salah satu contoh permasalahan kombinatorik