Optimasi : Susunan seperti apakah yang paling optimal?

Selain mendaftarkan dan menghitung, permasalahan yang cukup dominan dalam kombinatorika adalah permasalahan optimasi.

Permasalahan yang termasuk kategori ini adalah permasalahan yang menuntut kita untuk memikirkan strategi yang paling optimal untuk mencapai tujuan tertentu.

Dalam kaitan dengan kombinatorika, strategi yang dimaksud adalah susunan objek dalam batasan tertentu yang menghasilkan output minimum atau maksimum sesuai tujuan masalahnya.

Travelling salesman

Jauh sebelum adanya teknologi toko daring (misalnya Tokopedia) seperti hari ini, penjualan suatu produk dilakukan dengan mengunjungi kota-kota yang berbeda.

Tentunya perjalanan mengunjungi banyak kota tidaklah murah. Karena itu seorang penjual harus mengatur urutan perjalanannya dari satu tempat ke tempat lain hingga kembali ke tempat semula, agar biaya yang dikeluarkan bisa ditekan sesedikit mungkin.

Bayangkan kamu perlu mengirimkan barang melalui jalur darat ke kota-kota berikut ini:

• Palangkaraya
• Banjarmasin
• Pontianak
• Balikpapan
• Samarinda
• Singkawang

Kamu berangkat dari Palangkaraya, dan harus kembali ke kota tersebut pada akhirnya.

Agar biaya perjalanan yang dikeluarkan sesedikit mungkin, tentunya kamu harus memperhitungkan urutan yang se-efisien mungkin. Dilihat berdasarkan peta Kalimantan berikut ini, tentunya urutan di atas sangatlah tidak efisien, karena kamu perlu bolak-balik dari Barat ke Timur dan seterusnya.

Bandingkan jika urutannya diganti menjadi Palangkaraya - Banjarmasin - Balikpapan - Samarinda - Singkawang - Pontianak - kembali ke Palangkaraya.

Tentunya rute seperti ini akan lebih murah karena jarak yang ditempuh akan lebih sedikit.

Namun kamu juga perlu mempertimbangkan bahwa perjalanan darat hampir tidak mungkin dilakukan dalam garis lurus, sehingga perhitungan biaya masing-masing jalur perlu mempertimbangkan jarak yang sesungguhnya dari jalan yang berkelok-kelok, kemacetan, serta kesulitan dan risiko melalui jalur tersebut.

Sampai di sini, sepertinya persoalan semacam ini cukup mudah untuk diselesaikan, bukan? Betul, karena yang akan dikunjungi hanya 5 kota (1 kota yaitu Palangkaraya sudah pasti menjadi tempat berangkat dan pulang). Seandainya kamu mau mendaftar setiap jalur yang mungkin dibuat, kamu cukup membuat hanya (ehm... hanya...) 120 kemungkinan saja.

Namun persoalan dalam dunia nyata biasanya mencakup jauh lebih banyak kota. Misalnya 100. Jumlah kemungkinan rute menjadi sebegini banyak:

Bilangan tersebut dapat ditulis sebagai 9\times 10^{155}. Sebagai perbandingan, jumlah atom dalam galaksi kita adalah sekitar 2\times 10^{67}. Maka cara mendaftar kemungkinan satu per satu menjadi tidak mungkin dilakukan.

Kita memerlukan algoritma tertentu yang dapat mengurangi jumlah kemungkinan yang harus diperiksa agar kita dapat memperoleh jalur paling optimal atau setidaknya mendekati optimal.

Berikutnya: Merasakan kombinatorika