Combinatorial Problem

Dalam algoritma terdapat berbagai macam permasalahan salah satu nya adalah Combinatorial Problem atau Masalah Kombinatorial, yaitu permasalahan dalam matematika diskrit Ini adalah masalah yang meminta,
secara eksplisit atau implisit, untuk menemukan benda kombinatorial -seperti permutasi-, kombinasi, atau bagian-yang memenuhi kendala tertentu. Secara umum, masalah kombinatorial adalah masalah yang paling sulit dikomputasi, 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 kebanyakan masalah seperti persis dalam jumlah yang diterima waktu. Selain itu, sebagian besar ilmuwan komputer percaya bahwa algoritma tersebut tidak ada.

Berikut ini adalah contoh dari Combinatorial Problem:

1. Travelling Salesman Problem (TSP)

Travelling Salesman problem (TSP) merupakan masalah kombinasi optimasi dalam operasi penelitian dan teori ilmu komputer. Adalah suatu permasalahan dimana seorang sales harus melalui semua kota yang ditunjuk dengan jarak yang paling pendek dan setiap kota hanya boleh dilalui satu kali. TSP memiliki kemungkinan penyelesaian yang sangat banyak. Salah satu nya dengan metode optimal.

     Metode Optimal
Sejak permasalahan TSP ditemukan pada tahun 1800 oleh matematikawan Irlandia Sir William Rowan Hamilton dan matematikawan Inggris Thomas Penyngton Kirkman, pusat perhatian studi ini adalah menemukan secara pasti nilai minimum dari persoalan TSP dengan konsekuensi dibutuhkan waktu yang cukup lama untuk menyelesaikannya.

     Complete Enumeration

Metode ini akan mengenumerasi setiap kemungkinan yang terdapat dalam graf, setelah itu algoritma ini akan membandingkan lintasan mana yang paling minimum.

      Branch and Bound

Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil search trees menjadi sekecil mungkin. Sesuai namanya metode ini terdiri dari 2 langkah yaitu branch yang berarti membangun semua cabang trees yang mungkin menuju solusi. dan bound yang berarti menghitung node mana yang merupakan aktiv node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala).

2. Algoritma Pencari siklus-Floyd

Algoritma pencari-siklus Floyd adalah algoritma untuk mencari siklus dalam barisan bilangan (disebut juga sekuens). Sekuens yang dimaksud bisa berupa yang tersimpan dalam struktur data ataupun dibuat sesuai kebutuhan (berupa rumus). Algoritma ini ditemukan Robert W. Floyd pada tahun 1967[1]. Nama lainnya ialah algoritma "tortoise and the hare" (istilah ini serupa dengan "kura-kura dan kancil").

Perlu diperhatikan bahwa "Algoritma Floyd" berbeda dengan "Algoritma pencari-siklus Floyd" dari penemu yang sama.
Algoritma

Misalkan kita ingin memeriksa sebuah sekuens ai. Kita definisikan sang kura-kura sebagai:

dan sang kancil sebagai 

di mana i elemen bilangan asli. Jalankan dengan i dimulai dari 1, berlanjut ke 2, dst sampai kondisi ini terjadi

Kondisi ini akan berlaku untukdi mana s adalah siklus yang dicari.

referensi :

http://pusat-ensiklopedi-bebas-q.unkris.my.id/ind/2822-2697/Algoritma-Pencari-Siklus-Floyd_27395_unkris_pusat-ensiklopedi-bebas-q-unkris.html

informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/Makalah/MakalahStmik30.pdf

http://download.portalgaruda.org/article.php?article=120270&val=5499&title=Aplikasi%20Travelling%20Salesman%20Problem%20dengan%20Metode%20Artificial%20Bee%20Colony

Levitin, Anany. The Design and Analysis of Algorithms.