---
title: "Dal-Budama Yöntemi"
source: "https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi"
wiki: "systems-analysis.info/int"
article: "Dal-Budama_Yöntemi"
language: "tr"
categories:
  - "Category:Operations research"
  - "Category:Turkish"
revision_id: 1417
wiki_created_at: 2026-09-06T22:48:26Z
wiki_modified_at: 2026-09-06T22:48:26Z
downloaded_at: 2026-09-07T22:45:59Z
---

# Dal-Budama Yöntemi

**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<sup>[\[1\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-en-wiki-bnb-1)</sup> çö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<sup>[\[2\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-ru-wiki-bnb-2)</sup>.

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<sup>[\[3\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-land-doig-1960-3)</sup>. 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 $S_{i}$ genellikle birbirini dışlayan birkaç daha küçük alt kümeye $S_{i1},S_{i2},\ldots,S_{ik}$ ö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 \geq 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\leftarrow 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<sup>[\[4\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-conitzer-duke-4)</sup>.
- **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<sup>[\[5\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-maudet-danoy-2024-5)</sup>.

## Ö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 $x_{j}$ üzerinden gerçekleşir ve $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ ile $x_{j} \geq \lceil x_{j}^{\ast}\rceil$ 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<sup>[\[6\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-little-1963-6)</sup>.

## İ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

<sup>[\[1\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-en-wiki-bnb-1)</sup> <sup>[\[2\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-ru-wiki-bnb-2)</sup> <sup>[\[3\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-land-doig-1960-3)</sup> <sup>[\[4\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-conitzer-duke-4)</sup> <sup>[\[5\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-maudet-danoy-2024-5)</sup> <sup>[\[6\]](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_note-little-1963-6)</sup> \</references\>

1.  <span id="cite_note-en-wiki-bnb-1">↑ <sup>[1.0](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-en-wiki-bnb_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-en-wiki-bnb_1-1)</sup> Wikipedia contributors. (2025). Branch and bound. In *Wikipedia, The Free Encyclopedia*. Retrieved 2025-10-26, from <a href="https://en.wikipedia.org/wiki/Branch_and_bound" class="external free" rel="nofollow">https://en.wikipedia.org/wiki/Branch_and_bound</a></span>
2.  <span id="cite_note-ru-wiki-bnb-2">↑ <sup>[2.0](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-ru-wiki-bnb_2-0)</sup> <sup>[2.1](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-ru-wiki-bnb_2-1)</sup> Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from <a href="https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ" class="external free" rel="nofollow">https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ</a></span>
3.  <span id="cite_note-land-doig-1960-3">↑ <sup>[3.0](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-land-doig-1960_3-0)</sup> <sup>[3.1](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-land-doig-1960_3-1)</sup> 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: <a href="https://www.jstor.org/stable/1910129" class="external free" rel="nofollow">https://www.jstor.org/stable/1910129</a></span>
4.  <span id="cite_note-conitzer-duke-4">↑ <sup>[4.0](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-conitzer-duke_4-0)</sup> <sup>[4.1](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-conitzer-duke_4-1)</sup> Conitzer, V. (2008). *Solving (mixed) integer programs using branch and bound*. Duke University, Department of Computer Science. URL: <a href="https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf" class="external free" rel="nofollow">https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf</a></span>
5.  <span id="cite_note-maudet-danoy-2024-5">↑ <sup>[5.0](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-maudet-danoy-2024_5-0)</sup> <sup>[5.1](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-maudet-danoy-2024_5-1)</sup> 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: <a href="https://arxiv.org/abs/2412.09444" class="external free" rel="nofollow">https://arxiv.org/abs/2412.09444</a></span>
6.  <span id="cite_note-little-1963-6">↑ <sup>[6.0](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-little-1963_6-0)</sup> <sup>[6.1](https://systems-analysis.info/int/Dal-Budama_Y%C3%B6ntemi#cite_ref-little-1963_6-1)</sup> 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: <a href="https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf" class="external free" rel="nofollow">https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf</a></span>