Dal-Budama Yöntemi

From Systems analysis wiki
Jump to navigation Jump to search

Dal ve sınır yöntemi (İng. Branch and Bound, kıs. B&B veya BnB) — ayrık ve kombinatoryal optimizasyon problemlerini, özellikle NP-zor problemleri[1] çözmek için kesin algoritmalar inşa etmeye yönelik genel bir paradigmadır. Yöntem, tüm geçerli çözümler kümesinin sıralı biçimde alt kümelere ayrıldığı (dallanma) ve her bir alt küme için amaç fonksiyonunun değerine ilişkin tahminlerin (sınırlar) hesaplandığı yönlendirilmiş bir arama stratejisini temsil eder. Bu tahminler, kesinlikle optimal çözüm içermeyen alt kümelerin göz ardı edilmesini (budanmasını) sağlar ve böylece arama uzayını önemli ölçüde daraltır[2].

Yöntem ilk kez A. Land ve A. Doig tarafından 1960 yılında tam sayılı programlama problemlerini çözmek amacıyla önerilmiştir[3]. O tarihten bu yana yöneylem araştırması ve bilgisayar bilimlerinde en temel yaklaşımlardan biri hâline gelmiştir. Yöntemin temel özelliği esnekliğidir: belirli bir algoritma değil, çözülen problemin yapısına uyarlanabilen üst düzey stratejik bir şema (framework) niteliği taşır.

Yöntemin Temel Bileşenleri

Yöntemin özünde, bir arama ağacı biçiminde düzenlenmiş çözüm uzayı alt kümelerine uygulanan üç temel işlem yatar.

  • Dallanma (İng. Branching) — geçerli geçerli çözümler kümesinin Si genellikle birbirini dışlayan birkaç daha küçük alt kümeye Si1,Si2,…,Sik özyinelemeli olarak bölünmesi sürecidir. Her bir alt küme yeni bir alt probleme karşılık gelir ve arama ağacında bir alt düğüm olarak temsil edilir. Örneğin, tam sayılı programlama problemlerinde dallanma çoğunlukla LP-gevşemesi çözümünde kesirli değere sahip değişken üzerinden gerçekleştirilir.
  • Sınır tahmini' (İng. Bounding) — arama ağacının her düğümü (yani her alt problem) için amaç fonksiyonunun değerine ilişkin bir tahmin hesaplanır. Minimizasyon problemleri için bu, söz konusu alt kümedeki herhangi bir çözüm için garantili bir alt sınır olan alt sınır (lower bound) değeridir. Çoğunlukla bu tahmin, bazı karmaşık kısıtların (örneğin tam sayılık kısıtlarının) geçici olarak göz ardı edildiği basitleştirilmiş bir sürüm olan asıl alt problemin gevşemesi çözülerek elde edilir. En yaygın kullanılan LP-gevşemesidir.
  • Budama (İng. Pruning) — optimal çözümü kesinlikle içeremeyecek düğümlerin (ve bunlara karşılık gelen tüm alt ağaçların) değerlendirme dışı bırakılması sürecidir. Bir düğüm aşağıdaki durumlardan birinde budanır:
  1. Sınıra göre budama: Söz konusu düğüm için alt sınır, şu ana kadar bulunan en iyi geçerli çözümün değeri olan rekora (incumbent) göre daha iyi değildir (yani minimizasyon problemi için büyük veya eşittir).
  2. Geçerliliğe göre budama: Düğümün gevşeme çözümü asıl problem için geçerlidir (örneğin tüm değişkenler tam sayıdır). Bu çözüm mevcut rekorla karşılaştırılır ve daha iyiyse rekor güncellenir. Bu düğümden daha fazla dallanmaya gerek yoktur.
  3. Çözümsüzlüğe göre budama: Düğüme karşılık gelen alt problemin geçerli çözümü yoktur.

Genel Algoritma

Minimizasyon problemi için dal ve sınır yönteminin genelleştirilmiş algoritması aşağıdaki adımlarla açıklanabilir:

  1. Başlatma: Bir başlangıç geçerli çözümü bulun (örneğin sezgisel yöntemle) ve onun değerini başlangıç üst sınırı (rekor) olarak ayarlayın U. Kök düğümü (asıl problemi) içeren aktif düğümler kuyruğunu Q oluşturun.
  2. Ana döngü: Kuyruk Q boş olmadığı sürece:
    • Arama stratejisine (örneğin derinlik öncelikli arama veya en iyi tahmine göre arama) uygun olarak kuyruktan Q bir düğüm seçin.
    • Bu düğüm için gevşemeyi çözerek alt sınırı L elde edin.
    • L≥U koşulunu sağlıyorsa düğümü budayın.
    • Gevşeme çözümü asıl problem için geçerliyse rekoru güncelleyin: U←L.
    • Düğüm budanmamışsa ve çözüm geçerli değilse, onu alt düğümlere bölerek dallanma gerçekleştirin ve bunları kuyruğa Q ekleyin.
  3. Sonlandırma: Kuyruk Q boş hâle geldiğinde algoritma sona erer. Rekor U değerine karşılık gelen bulunan çözüm global olarak optimaldir.

Temel Özellikler ve Teoremler

  • Doğruluk ve yakınsama: Geçerli çözümler kümesi sonluysa ve dallanma prosedürü yakınsak ise (yani özyinelemeli bölme sırasında alt kümeler noktalara "büzülüyorsa"), algoritma sonlu sayıda adımda global optimal çözümü bulmayı garanti eder[4].
  • Arama stratejisi: Algoritmanın verimliliği, dallanma için bir sonraki düğümü seçme stratejisine (örneğin derinlik öncelikli arama, genişlik öncelikli arama, en iyi tahmine göre arama) ve dallanma değişkeninin seçimine büyük ölçüde bağlıdır. Modern çözücüler çoğunlukla hibrit stratejiler kullanır[5].

Örnekler

  • Tam sayılı programlama problemi: Yöntemin klasik uygulamasıdır. Gevşeme olarak doğrusal programlama kullanılır. Dallanma, kesirli değişken xj üzerinden gerçekleşir ve xj≤⌊xj*⌋ ile xj≥⌈xj*⌉ ek kısıtlarına sahip iki alt problem oluşturulur.
  • Gezgin satıcı problemi: Çözüm uzayı, grafikteki tüm olası Hamilton döngülerinden oluşur. Dallanma kenarlara göre yapılabilir (bir kenarı rotaya dahil et/dışla). Alt sınır olarak atama problemi veya minimum yayılan ağaç oluşturma gibi daha basit problemlerin çözümleri kullanılabilir[6].

İlgili Kavramlar ve Uygulamalar

  • Dal ve kesim yöntemi (Branch-and-Cut): B&B'yi kesme düzlemleri yöntemiyle birleştiren hibrit bir yöntemdir. Arama ağacının her düğümünde gevşeme çözümünün yanı sıra alt sınırı güçlendiren ek eşitsizlikler (kesimler) üretilir; bu da dalların daha verimli budanmasını sağlar.
  • Geri izleme (Backtracking): Dal ve sınır yöntemi, bu algoritmanın optimizasyon problemleri için bir genellemesi olarak değerlendirilebilir.
  • Alfa-beta budama: Oyun ağaçlarında kesinlikle kayıp doğuran dalları budamak amacıyla kullanılan kavramsal bir analoji.

Ayrıca bakınız

  • Tam sayılı programlama
  • Kombinatoryal optimizasyon
  • Gezgin satıcı problemi
  • NP-zor problem
  • Simpleks yöntemi

Notlar

[1] [2] [3] [4] [5] [6] </references>

  1. ↑ 1.0 1.1 Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
  2. ↑ 2.0 2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ 3.0 3.1 Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
  4. ↑ 4.0 4.1 Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
  5. ↑ 5.0 5.1 Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
  6. ↑ 6.0 6.1 Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf
Retrieved from "https://systems-analysis.ru/int/index.php?title=Dal-Budama_Yöntemi&oldid=27829"