Branch and Bound

Apa Itu Cabang Dan Terikat?

Cabang dan terikat, atau BnB, adalah paradigma desain algoritma yang memecahkan masalah optimisasi kombinatorial dan diskrit. Banyak masalah pengoptimalan, seperti penjadwalan kru, masalah aliran jaringan, dan perencanaan produksi, tidak dapat diselesaikan dalam waktu polinomial. Oleh karena itu, BnB adalah paradigma yang banyak digunakan untuk memecahkan masalah tersebut.

Anda bebas menggunakan gambar ini di situs web Anda, templat, dll., Harap berikan kami tautan atribusiBagaimana Memberikan Atribusi? Tautan Artikel menjadi Hyperlink
Misalnya: Sumber: Branch and Bound (wallstreetmojo.com)

Algoritme ini sangat bergantung pada estimasi efisiensi batas bawah dan atas cabang ruang pencarian. Ini merosot menjadi pencarian yang menyeluruh atau menyeluruh jika tidak ada batasan yang ditemukan. Metode cabang dan terikat memecahkan masalah kompleks ini dengan relatif lebih cepat. Dalam sebagian besar masalah pengoptimalan diskrit, metode BnB merupakan pilihan yang dapat diandalkan untuk memecahkan masalah tersebut.

Takeaway kunci

Algoritma cabang dan terikat memecahkan masalah optimisasi dengan kompleksitas waktu.
Itu diperkenalkan pada tahun 1960 oleh dua peneliti, Alisa Land dan Alison Diog, dari London School of Economics.
Algoritme membagi masalah optimisasi besar menjadi himpunan bagian yang lebih kecil dan lebih sederhana dan memindai solusi terbaik di antara solusi kandidat.
Algoritme mencari pohon seluruhnya sebelum sampai pada solusi terbaik. Proses ini dianggap sebagai proses yang memakan waktu, terutama untuk masalah besar atau kompleks.

Penjelasan Algoritma Branch And Bound

Cabang dan terikat adalah algoritma yang digunakan untuk memecahkan masalah optimisasi kombinatorial. Masalah ini biasanya ditambah dalam hal kompleksitas waktu dan masalah yang memerlukan eksplorasi semua permutasi dan kombinasi yang mungkin terjadi dalam skenario terburuk.

Kalkulator bercabang dan terikat biasanya digunakan untuk memecahkan masalah yang tidak dapat dipecahkan dalam waktu polinomial, seperti masalah aliran jaringan, penjadwalan kru, dan perencanaan produksi. Namun, ini dapat dipahami dengan lebih baik sebagai alat penelusuran mundur menggunakan state space tree.

Seperti namanya, BnB mengeksplorasi cabang atau node di bawah subset solusi tertentu. Node induk dianggap memiliki semua solusi yang mungkin untuk masalah tersebut. Namun, sebelum solusi kandidat untuk masalah dihitung atau disebutkan, batas atas dan bawah mengikat solusi optimal.

Metode cabang dan terikat diajukan pertama kali oleh Alisa Land dan Alison Doig dari London School of Economics pada tahun 1960 sebagai solusi pemrograman diskrit. Namun, nama “BnB” pertama kali digunakan secara resmi dalam sebuah penelitian tentang masalah salesman keliling.

Aplikasi

Algoritme BnB adalah tambahan yang sangat baik untuk gudang senjata pemecahan masalah organisasi, terutama ketika cabang dan ikatan mencatat semua kemungkinan dalam skenario terburuk. Selain itu, ini diterapkan dalam situasi di mana kombinasi tugas harus dioptimalkan. Mari kita bahas beberapa kasus di mana BnB akan menjadi pilihan yang baik:

Pengoptimalan Diskrit: Pengoptimalan diskrit adalah bagian dari pengoptimalan di mana variabel dari masalah tertentu harus dimiliki oleh kumpulan diskrit, misalnya, masalah aliran jaringan. Dalam situasi seperti ini, algoritma BnB adalah pilihan yang masuk akal.
Optimasi Kombinasi: Karena ditetapkan bahwa masalah optimisasi harus diselesaikan, optimisasi kombinasi menemukan batas maksimum dan minimum dari fungsi yang diberikan. Domain proses harus diskrit atau tidak terikat dan signifikan.

Keuntungan dan kerugian

Mari kita pahami kelebihan dan kekurangan BnB melalui poin-poin di bawah ini:

Keuntungan

Kompleksitas Waktu: Algoritme BnB tidak menjelajahi semua node di pohon. Dengan demikian, kompleksitas waktu secara signifikan lebih rendah daripada kebanyakan algoritma lainnya.
Solusi Optimal: Jika percabangan dilakukan secara wajar, algoritme dapat menemukan solusi optimal dalam periode yang wajar.
Hapus Pola: Algoritma BnB tidak mengulangi catatan untuk menjelajahi pohon untuk solusi kandidat; sebaliknya, ia mengikuti jalur minimal untuk memperoleh solusi optimal.

Kekurangan

Memakan waktu: Berdasarkan ukuran masalah, jumlah node yang dihitung mungkin terlalu besar dalam skenario terburuk, menjadikannya proses yang memakan waktu.
Paralelisasi: Percabangan dari kemungkinan solusi menyediakan ruang untuk paralelisme spekulatif. Namun, ketika tindakan alternatif dipertimbangkan untuk tindakan tersebut, kalkulator cabang dan terikat menemukan kesulitan.

Perbedaan Antara Cabang Dan Terikat Dan Mundur

Mari kita pahami perbedaan antara BnB dan backtracking melalui tabel di bawah ini:

Dasar	Cabang dan Terikat	Mundur
Fungsi Dasar	BnB digunakan untuk memecahkan masalah pengoptimalan.	Backtracking digunakan untuk menemukan semua solusi yang mungkin untuk masalah yang diberikan
Mendekati	Itu dapat melakukan perjalanan pohon di DFS atau Breadth First Search (BFS)	Berdasarkan pendekatan Depth First Search (DFS).
Fungsi Tambahan	Melibatkan fungsi pembatas	Melibatkan fungsi kelayakan
Larutan	Algoritme tahu bahwa ia memiliki solusi optimal yang lebih baik daripada solusi sebelumnya. Oleh karena itu, ia meninggalkan pra-solusi.	Sistem menyadari bahwa ia telah membuat pilihan yang salah dan membatalkan pilihan terakhir.
Spektrum Pencarian	Itu mencari pohon sepenuhnya sebelum memberikan solusi optimal	Ini menjelajahi pohon sampai jawabannya ditemukan.

Cabang Dan Terikat vs Pemrograman Dinamis

Meskipun BnB dan pemrograman dinamis memecahkan masalah pengoptimalan yang pada akhirnya mengarah pada memaksimalkan atau meminimalkan fungsi biaya dari situasi tertentu, mereka memiliki beberapa perbedaan. Mari kita pahami melalui poin-poin di bawah ini:

Cabang Dan Terikat

Metode BnB memecahkan masalah optimasi matematis dan masalah optimasi diskrit dan kombinatorial.
Alisa Land dan Alison Doig memperkenalkannya di London School of Economics pada tahun 1960.
Solusinya diselidiki di cabang atau simpul pohon.
Sebelum solusi kandidat dihitung, batas atas dan bawah ditetapkan dan diuji untuk menemukan kemungkinan solusi terbaik.

Pemrograman Dinamis

Pemrograman dinamis adalah alat pengoptimalan matematika dan pendekatan pemrograman komputer.
Itu ditemukan oleh Richard Bellman pada 1950-an dan telah digunakan di berbagai industri sejak saat itu.
Pemrograman dinamis memecah masalah besar menjadi himpunan bagian yang lebih sederhana dan lebih kecil dalam situasi terbaik dan terburuk.
Karena BnB tidak dapat menyimpulkan semua situasi atau masalah, poin data dihilangkan atau dibongkar dengan cara ini.

Pertanyaan yang Sering Diajukan (FAQ)

Bagaimana cara memecahkan masalah cabang dan terikat?

Masalah BnB diselesaikan dengan memisahkan solusi menjadi himpunan bagian atau simpul yang lebih kecil di pohon solusi yang memberikan gambaran rinci tentang semua kemungkinan solusi. Itu dilakukan setelah menetapkan batas atas dan bawah. Ini menggunakan strategi cabang, FIFO, atau LIFO dengan biaya terendah untuk menghasilkan organisasi cabang.

Bagaimana cara menggunakan metode cabang dan terikat?

Metode BnB didasarkan pada ideologi bahwa totalitas kandidat solusi dapat dibagi menjadi node solusi yang lebih kecil. Setelah pembagian dibuat, algoritme dapat mengevaluasinya secara sistematis hingga solusi terbaik ditemukan. Proses ini memakan waktu jauh lebih sedikit daripada algoritme lain jika dilakukan melalui BnB.

Untuk apa cabang dan algoritma terikat digunakan?

Biasanya, algoritma BnB digunakan untuk memecahkan masalah optimisasi kombinatorial. Sifat dari masalah ini biasanya kompleks secara eksponensial dalam hal waktu dan membutuhkan semua kemungkinan permutasi dan kombinasi untuk dieksplorasi sebelum sampai pada solusi terbaik.

Artikel yang Direkomendasikan

Ini telah menjadi panduan untuk apa itu Branch and Bound. Di sini, kami menjelaskan aplikasi dan perbedaannya dengan backtracking dan pemrograman dinamis. Anda dapat mempelajari lebih lanjut tentang keuangan dari artikel berikut –