Algoritma Branch and Bound

Algoritma Branch & Bound merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status.  Artinya, antrian yang digunakan, dan node diproses dengan urutan first-in-first-out. Jika kriteria biaya tersedia, node harus diperluas berikutnya (cabang) satu dengan biaya terbaik didalam antrian.

Biaya Berbasis Pohon Traversal

Sebuah fungsi dapat dianggap sebagai pembuat pohon, jika diberi simpul X dan indeks i menghasilkan anak i pertama dari node.

Fungsi berikut menghasilkan sebuah pohon biner lengkap dari 11 node.

Fungsi rekursif digunakan untuk menurunkan permutasi adalah contoh lain dari fungsi yang dapat digunakan untuk menghasilkan pohon.

Selain untuk pembuat fungsi pohon, kita juga membutuhkan fungsi biaya untuk memutuskan dalam rangka apa untuk melintasi node ketika mencari solusi. Algoritma berlangsung dengan cara berikut.

• Initialization: Akar pohon dinyatakan masih hidup.
• Visit: Kriteria biaya memutuskan mana dari node hidup untuk proses selanjutnya.
• Replacement: Node yang dipilih akan dihapus dari set node hidup, dan anak-anak dimasukkan ke dalam set. Anak-anak ditentukan oleh pembuat fungsi pohon.
• Iteration: Kunjungan dan langkah-langkah penggantian diulang sampai tidak ada node hidup yang tersisa.

Dalam kasus backtracking kriteria biaya mengasumsikan fungsi last-in-first-out (LIFO), yang dapat direalisasikan dengan memori stack. Sebuah kriteria biaya first-in-first-out menyiratkan algoritma branch and bound, dan dapat terwujud dengan memori antrian. Sebuah generalisasi terhadap kriteria biaya adalah dasar untuk algoritma branch and bound, dan memori antrian dapat digunakan untuk mewujudkan fungsi.

Bersambung...