Penjelasan Cabang dan Batas

Saya memiliki tes tentang algoritma branch and bound . Saya mengerti secara teoritis bagaimana algoritma ini bekerja tetapi saya tidak dapat menemukan contoh yang menggambarkan bagaimana algoritma ini dapat diimplementasikan secara praktis.

Saya menemukan beberapa contoh seperti ini tetapi saya masih bingung tentang itu. Saya juga mencari masalah salesman keliling dan saya tidak bisa memahaminya.

Yang saya butuhkan adalah beberapa masalah dan bagaimana masalah ini dapat diselesaikan dengan menggunakan cabang dan terikat.

Mari kita terapkan Branch and Bound ke Knapsack , semoga ini akan membuat konsepnya jelas bagi Anda.

Kami memiliki item, berlabel 1 hingga n . v i adalah nilai dari i butir th, dan w i berat. Kami mencoba memasukkannya ke dalam ransel yang dapat memuat total T , dan kami berusaha memaksimalkan jumlah nilai dari barang yang kami masukkan ke ransel.$n$$1$$n$$v_i$$i$$w_i$$T$

Pendekatan backtrack biasa adalah basis kami. Kami pertama-tama memasukkan dalam paket, dan kemudian menyelesaikan masalah untuk item n - 1 yang tersisa dengan rekursi. Kami kemudian menghapus v 1 dari paket dan menyelesaikan masalah untuk item n - 1 yang tersisa lagi, dan kami mengembalikan konfigurasi terbaik yang kami temukan.$v_1$$n-1$$v_1$$n-1$

Mundur ini adalah bagian 'Cabang' dari Cabang dan Terikat. Anda bercabang pada (dalam kasus Knapsack) dua kasus: 'item adalah bagian dari solusi' dan 'item i bukan bagian dari solusi'. Anda dapat memvisualisasikan ini sebagai pohon biner, di mana anak kiri adalah satu case dan anak kanan adalah case lainnya. Pohon ini adalah pohon pencarian (atau ruang pencarian ): kedalamannya adalah n , dan karenanya memiliki simpul O ( 2 n ) . Algoritma karena itu memiliki eksponensial waktu berjalan dalam jumlah item.$i$$i$$n$$O(2^n)$

Sekarang kita sampai pada bagian 'Bound': kita mencoba menemukan kriteria sehingga kita dapat mengatakan 'konfigurasi ini tidak pernah berhasil, jadi kita mungkin juga tidak repot menghitung ini'. Contoh dari kriteria seperti itu adalah 'berat barang yang sudah kita masukkan ke dalam ransel melebihi ': jika kita telah menambahkan, katakanlah, item n / 2 pertama ke ransel dan karena itu sudah penuh, ada tidak ada gunanya mencoba memasukkan item n / 2 + 1 hingga ke n di ransel juga, tetapi juga tidak ada gunanya mencoba menyesuaikan setiap subset dari n / 2 + 1 hingga $T$$n/2$$n/2+1$$n$$n/2+1$$n$di ransel, karena sudah penuh, jadi kami menghemat sekitar kasus. Contoh lain adalah ' bahkan jika saya memasukkan semua item yang tersisa, nilai item yang saya masukkan tidak akan melebihi konfigurasi terbaik yang saya temukan sejauh ini '.$2^{n/2}$

Kriteria ini pada dasarnya memotong bagian dari pohon pencarian: pada beberapa node, Anda mengatakan misalnya 'subtree kiri tidak akan memberi saya konfigurasi yang lebih baik, karena X', jadi Anda lupa tentang subtree itu dan Anda tidak menjelajahinya. Subtinggi kedalaman yang Anda potong dengan cara ini menghemat Anda O ( 2 d ) node, yang bisa jadi sedikit peningkatan kecepatan jika Anda beruntung.$d$$O(2^d)$

Perhatikan bahwa ini disebut ' Bounding ' karena biasanya melibatkan semacam batas bawah atau atas: untuk kriteria ' bahkan jika saya memasukkan semua item yang tersisa, nilai item yang saya masukkan tidak akan melebihi konfigurasi terbaik Saya telah menemukan sejauh ini ', nilai konfigurasi terbaik Anda sejauh ini adalah batas bawah pada konfigurasi terbaik, jadi apa pun yang tidak akan pernah berhasil melewati batas bawah ini pasti akan gagal.

Anda dapat membuat bagian 'Bounding' serumit yang Anda suka. Misalnya, masalah pemrograman bilangan bulat sering diselesaikan dengan menggunakan relaksasi: Anda mengendurkan program Anda menjadi program linier, yang dapat Anda selesaikan dalam waktu polinomial, dan kemudian Anda dapat membuang banyak kasus untuk variabel biner Anda yang toh tidak akan pernah berhasil. Anda kemudian bercabang pada opsi yang tersisa.

Perhatikan bahwa Branch dan Bound biasanya hanya memberi Anda peningkatan kecepatan dalam latihan, tetapi tidak dalam teori: sulit untuk mengatakan dengan tepat berapa banyak pohon pencarian yang dipotong menggunakan heuristik Anda. Ini dibuktikan dengan jumlah heuristik yang berbeda yang digunakan dalam praktek pada masalah seperti itu. Jika Anda kurang beruntung, pohon pencarian yang tersisa tetap besar bahkan dengan banyak ikatan.

Pertimbangkan penjadwalan , tugas menetapkan pekerjaan dengan jangka waktu dan tenggat waktu tertentu untuk mesin. Kami menganggap waktu terpisah. Banyak masalah seperti itu NP (O) -hard.

$1 \mid r_i \mid L_\max$

• pada satu mesin
• masalah dengan tanggal rilis dan kami
• $L_\max$

Versi keputusan dari masalah ini adalah NP-hard; ini bisa dilihat dengan pengurangan dari 3PARTISI .

Yang cukup menarik, jika kita mengizinkan preemption , yaitu menukar pekerjaan aktif, masalahnya dapat diselesaikan dalam waktu kuadratik dengan heuristik Terlebih Dahulu Terlebih Dahulu (pada tanggal jatuh tempo yang dimodifikasi). Sangat mudah untuk melihat bahwa solusi optimal dari varian ini tidak lebih buruk daripada solusi optimal dari masalah aslinya.

Sekarang, untuk menerapkan Branch & Bound ke masalah ini kita perlu memperbaiki beberapa parameter:

• Kami menghitung batas bawah dengan memungkinkan preemption dan menggunakan EDD.
• Kami bercabang dengan memperbaiki setiap pekerjaan yang tidak dijadwalkan sebagai pekerjaan berikutnya.
• Kami pergi ke anak dengan ikatan kecil lebih dulu.

Anda harus melakukan ini untuk setiap aplikasi B&B.

$1 \mid r_i \mid L_\max$

$\qquad \displaystyle \begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline p_i & 4 & 2 & 6 & 5 \\ r_i & 0 & 1 & 3 & 5 \\ d_i & 8 & 12 & 11 & 10 \end{array}$

$p_i$$r_i$$d_i$

Melaksanakan B&B seperti yang ditentukan di atas, ini terjadi:

_{GIF ini tidak berulang. Muat ulang di tab baru untuk melihat dari awal.}
^{[ sumber ] [ versi statis ]}

Perhatikan bahwa dari 41 node, hanya empat yang dikunjungi dengan benar dan hanya untuk sepuluh yang batas bawahnya dihitung.