Backtracking dan Branch and Bound

Backtracking dan branch and bound adalah paradigma pencarian sistematis yang menjelajahi ruang solusi kandidat sebagai sebuah pohon, memangkas sub-pohon yang tidak dapat mengarah pada solusi yang valid atau optimal untuk membuat pencarian eksponensial menjadi dapat dikelola dalam praktiknya.

Definition

Backtracking adalah pencarian mendalam (depth-first search) dari pohon solusi kandidat parsial yang memangkas cabang pada saat kandidat parsial tidak dapat diselesaikan menjadi solusi yang valid; branch and bound melengkapinya dengan batasan numerik pada tujuan sehingga cabang-cabang yang nilai terbaiknya tidak dapat mengalahkan nilai yang sudah ada akan dibuang.

Scope

Topik ini mencakup teknik pencarian menyeluruh yang diorganisasikan di sekitar pohon pencarian: backtracking, yang meninggalkan kandidat parsial segera setelah melanggar batasan, dan branch and bound, yang menggunakan batasan pada tujuan terbaik yang dapat dicapai untuk memangkas sub-pohon dalam optimasi. Ini mencakup contoh-contoh pemenuhan batasan (N-ratu, pewarnaan graf, Sudoku) dan contoh-contoh optimasi kombinatorial (pedagang keliling, pemrograman bilangan bulat), dan membahas mengapa metode-metode ini tetap berharga untuk masalah NP-hard meskipun biaya eksponensial dalam kasus terburuk.

Core questions

• Bagaimana ruang solusi masalah dimodelkan sebagai pohon pencarian tugas parsial?
• Pemeriksaan batasan apa yang memungkinkan backtracking memangkas cabang yang tidak layak lebih awal?
• Bagaimana batas bawah dan atas dihitung untuk memangkas cabang dalam optimasi?
• Bagaimana urutan percabangan (branching) dan pembatasan (bounding) memengaruhi kinerja praktis?
• Mengapa metode-metode ini digunakan untuk masalah NP-hard meskipun ada kasus terburuk yang eksponensial?

Key concepts

• pohon pencarian
• eksplorasi mendalam
• propagasi batasan
• pemangkasan
• fungsi pembatas
• solusi inkumben
• masalah N-ratu
• relaksasi pemrograman bilangan bulat

Key theories

Pemangkasan pohon pencarian

Kedua paradigma mengorganisasikan solusi kandidat sebagai pohon yang dijelajahi secara mendalam; kebenaran berasal dari kelengkapan, sementara efisiensi berasal dari pemangkasan sub-pohon yang terbukti tidak dapat mengandung solusi yang valid atau lebih baik.

Fungsi pembatas dalam branch and bound

Branch and bound mempertahankan solusi terbaik yang ditemukan sejauh ini dan batasan (misalnya relaksasi LP) pada nilai terbaik yang dapat dicapai di setiap sub-pohon; sub-pohon dibuang ketika batasannya tidak dapat meningkatkan solusi yang sudah ada.

Clinical relevance

Branch and bound adalah tulang punggung optimasi kombinatorial eksak dalam riset operasi, termasuk pemecah pemrograman bilangan bulat dan bilangan bulat campuran yang digunakan untuk penjadwalan, perutean, dan perencanaan. Backtracking mendasari pemecah batasan, pencarian gaya SAT, pemecah teka-teki, dan parser, di mana pencarian sistematis dengan pemangkasan adalah jalur praktis menuju jawaban yang tepat.

History

Backtracking disistematisasi sebagai teknik umum pada tahun 1950-an dan 1960-an, terutama dijelaskan oleh Golomb dan Baumert. Branch and bound diperkenalkan oleh Ailsa Land dan Alison Doig pada tahun 1960 untuk pemrograman linear bilangan bulat dan sejak itu menjadi pusat optimasi kombinatorial, menggerakkan pemecah pemrograman bilangan bulat campuran modern.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

Apa perbedaan antara backtracking dan branch and bound?

Backtracking umumnya digunakan untuk masalah kelayakan dan pemenuhan batasan serta memangkas cabang yang melanggar batasan. Branch and bound menargetkan optimasi dan juga memangkas menggunakan batasan numerik, membuang setiap sub-pohon yang tujuan terbaiknya tidak dapat mengalahkan solusi terbaik yang sudah ditemukan.

Jika metode-metode ini bersifat eksponensial dalam kasus terburuk, mengapa menggunakannya?

Untuk masalah NP-hard, tidak ada algoritma eksak polinomial yang diketahui, tetapi pemangkasan yang efektif sering kali menghilangkan sebagian besar pohon pencarian pada instans nyata, sehingga pemecah branch-and-bound dan backtracking secara teratur menemukan solusi optimal yang terbukti jauh lebih cepat daripada yang disarankan oleh batasan kasus terburuknya.