Elágazás és korlátozás forrásának megtekintése

Az '''elágazás és korlátozás''' ('''BB''', '''B&B''' vagy '''BnB''') [[algoritmus]]tervezési paradigma diszkrét és kombinatorikus optimalizálási problémákhoz, valamint a [[matematikai optimalizálás]]hoz szolgálnak. Az elágazás és korlátozás algoritmus a jelölt megoldások szisztematikus felsorolását foglalja magában a térmodell keresés segítségével: a jelölt megoldások halmazát úgy gondolják, hogy egy [[Fa (gráfelmélet)|gyökeres fát]] alkot, amelynek teljes része a gyökér. Az algoritmus e fa ''ágait'' vizsgálja, amelyek a megoldás halmazának részhalmazait képviselik. Az ág jelölt megoldásainak felsorolása előtt megvizsgáljuk az ''ágat'' az optimális megoldás felső és alsó becsült ''határaival'' szemben, és elvetjük, ha nem képes jobb megoldást eredményezni, mint az algoritmus által eddig megtalált legjobb megoldás. 

Az algoritmus a keresési terület ágainak alsó és felső határainak hatékony becslésén múlik. Ha nem állnak rendelkezésre határok, az algoritmus aprólékos keresésre vált. 

A módszert először Ailsa Land és Alison Doig tette közzé, miközben a [[BP|British Petroleum]]<ref name="land_doig">{{Cite news|author=A. H. Land and A. G. Doig|title=An automatic method of solving discrete programming problems|work=Econometrica|pages=497–520}}</ref> <ref>{{Cite web |url=http://www.lse.ac.uk/newsletters/pressAndInformation/staffNews/2010/20100218.htm |title=Staff News |work=www.lse.ac.uk |accessdate=2018-10-08 |archívurl=https://web.archive.org/web/20210224173541/https://www.lse.ac.uk/newsletters/pressAndInformation/staffNews/2010/20100218.htm |archívdátum=2021-02-24 |archiveurl=https://web.archive.org/web/20210224173541/https://www.lse.ac.uk/newsletters/pressAndInformation/staffNews/2010/20100218.htm |archivedate=2021-02-24 }}</ref> által 1960-ban támogatott [[London School of Economics|londoni közgazdasági iskolában]] végzett kutatást diszkrét programozás témakörben, és ez lett a leggyakrabban használt eszköz az NP-nehéz feladat optimalizálási problémák megoldására. Az "ágak és összeköttetések" név először Little ''et al.'' az [[Az utazó ügynök problémája|utazó értékesítő problémájával kezdődött]].<ref name="little">{{Cite journal|author=Little|first=John D. C.|title=An algorithm for the traveling salesman problem|journal=Operations Research|volume=11|issue=6|year=1963|pages=972–989|doi=10.1287/opre.11.6.972|url=http://dspace.mit.edu/bitstream/handle/1721.1/46828/algorithmfortrav00litt.pdf}}</ref>

== Áttekintés ==
Az elágazás és korlátozás algoritmus célja, hogy olyan {{Mvar|x}} értéket keressen, amely maximalizálja vagy minimalizálja az objektív függvénynek nevezett {{Math|''f''(''x'')}} valós értékű függvény értékét néhány {{Mvar|S}} megengedhető vagy lehetséges megoldás között. Az {{Mvar|S}} halmazt keresési területnek vagy megvalósítható régiónak nevezzük. E szakasz többi része feltételezi, hogy az {{Math|''f''(''x'')}} érték minimalizálása a cél; ez a feltételezés [[az általánosság megszorítása nélkül|a többség elvesztése nélkül]] valósul meg, mivel az {{Math|''f''(''x'')}} maximális értékét úgy találhatjuk meg, hogy megkeressük a {{Math|''g''(''x'') {{=}} −''f''(''x'')}} minimumot. A B & B algoritmus két alapelv szerint működik: 

* Rekurzív módon felosztja a keresési teret kisebb terekre, majd minimalizálja az {{Math|''f''(''x'')}}-et ezeken a kisebb tereken; ezt a felosztást ''elágazásnak'' nevezzük. 
* Az elágazás önmagában a lehetséges megoldások nyers erő számbavételét és mindegyikének tesztelését jelentené. A nyers erővel történő keresés teljesítményének javítása érdekében a B & B algoritmus minimálisan nyomon követi a ''korlátokat'', amelyeket megpróbál megtalálni, és ezeket a korlátokat használja a keresési terület „ ritkításához ”, kiküszöbölve az olyan jelölt megoldásokat, amelyek bizonyítani tudják, hogy nem tartalmaznak optimális megoldást. 

Ezeknek az alapelveknek a konkrét optimalizálási probléma konkrét algoritmussá történő alakításához valamilyen [[Adatszerkezet|adatszerkezetre van szükség,]] amely rámutat a lehetséges megoldások halmazára. Az ilyen ábrázolást a probléma egyik ''esetének'' nevezzük. Jelölje meg a példány megoldáskészletét {{Mvar|S<sub>I</sub>}}-nél A példánynak három művelettel kell rendelkeznie: 

* Az (I) ág két vagy több példányt hoz létre, amelyek mindegyike az SI egy részhalmazát képviseli. (Általában az részhalmazok el vannak választva annak megakadályozására, hogy az algoritmus ugyanazt a jelöltet megoldást kétszer megvizsgálja, de ezt szeretnénk elkerülni. Az SI közötti optimális megoldást azonban az alkészletek legalább egyikében tartalmaznia kell.<ref name="bader">{{cite encyclopedia |first1=David A. |last1=Bader |first2=William E. |last2=Hart |first3=Cynthia A. |last3=Phillips |author3-link=Cynthia A. Phillips |title=Parallel Algorithm Design for Branch and Bound |editor-first=H. J. |editor-last=Greenberg |encyclopedia=Tutorials on Emerging Methodologies and Applications in Operations Research |publisher=Kluwer Academic Press |year=2004 |url=http://www.cc.gatech.edu/~bader/papers/ParallelBranchBound.pdf |accessdate=2020-05-18 |archívurl=https://web.archive.org/web/20170813145917/http://www.cc.gatech.edu/~bader/papers/ParallelBranchBound.pdf |archívdátum=2017-08-13 }} {{Wayback|url=http://www.cc.gatech.edu/~bader/papers/ParallelBranchBound.pdf |date=20170813145917 }} {{Cite web |url=http://www.cc.gatech.edu/~bader/papers/ParallelBranchBound.pdf |title=Archivált másolat |accessdate=2020-05-18 |archiveurl=https://web.archive.org/web/20170813145917/http://www.cc.gatech.edu/~bader/papers/ParallelBranchBound.pdf |archivedate=2017-08-13 }}</ref>)
* Az ág (I) kiszámítja bármely jelölt megoldás értékének alsó határát az I által képviselt térben, azaz (I) ≤ f (x) az összes x-re SI-ben.
* Az (I) megoldás határozza meg, hogy megfelelő-e az egyetlen jelölt megoldás. (Opcionálisan, ha nem, a művelet dönthet úgy, hogy valamely megvalósítható megoldást visszaad az SI közül{{R|bader}})

Ezeket a műveleteket használva a B&B algoritmus felülről lefelé történő rekurzív keresést hajt végre az ágművelet által létrehozott példányok fáján. Az {{Mvar|I}} példány meglátogatásakor ellenőrzi, hogy az {{Math|bound(''I'')}} nagyobb-e, mint valamely más példány alsó határa, amelyet már meglátogatott; Ha így van, {{Mvar|I}} is biztonságosan lehet dobni a keresési és a rekurzió leáll. Ezt a metszéslépést általában egy olyan globális változó fenntartásával valósítják meg, amely rögzíti a legkisebb alsó határt az eddig vizsgált esetek között. 

=== Generikus változat ===
Az alábbiakban egy általános ág vázlatát és kötött algoritmust használjuk az önkényes {{Mvar|f}} függvény minimalizálására. Ahhoz, hogy ebből tényleges algoritmust kapjunk, szükség van egy {{Mvar|g}} határoló függvényre, amely kiszámítja az {{Mvar|f}} alsó határait a keresési fa csomópontjain, valamint egy probléma-specifikus elágazási szabályt. Mint ilyen, az itt bemutatott általános algoritmus magasabb rendű függvény. 

# [[Heurisztika]] segítségével keresse meg az {{Mvar|x<sub>h</sub>}} megoldást az optimalizálási problémára. Tárolja értékét, {{Math|''B'' {{=}} ''f''(''x<sub>h</sub>'')}}. (Ha nincs heurisztika, állítsa a {{Mvar|B}}-t végtelenre.) {{Mvar|B}} jelöli az eddig megtalált legjobb megoldást, és a jelölt megoldások felső határán fogja használni. 
# Inicializálja a sort, hogy egy részleges megoldást tartson a megadott probléma egyik változójával sem. 
# Hurok, amíg a sor üres: 
## Vegye ki az {{Mvar|N}} pontot a sorból. 
## Ha {{Mvar|N}} jelentése egy jelölt {{Mvar|x}} megoldást és {{Math|''f''(''x'') < ''B''}}, akkor {{Mvar|x}} a legjobb megoldás eddig. Rögzítse és állítsa be a {{Math|''B'' ← ''f''(''x'')}}. 
## Egyébként, az ''ág'' {{Mvar|N}} hogy készítsen új csomópontokat {{Mvar|N<sub>i</sub>}}-pontnak. Ezek mindegyikére: 
### Ha {{Math|''bound''(''N<sub>i</sub>'') > ''B''}}, ne tegyen semmit; mivel ezen a csomóponton az alsó határ nagyobb, mint a probléma felső határa, soha nem vezet az optimális megoldáshoz, és elvethető. 
### Egyébként, tárolja az {{Mvar|N<sub>i</sub>}}-et a sorban. 

Számos különböző [[Sor (adatszerkezet)|sor-]]adatstruktúra használható. Ez a FIFO soron alapuló megvalósítás szélesség első keresést eredményez. A [[Verem (adatszerkezet)|verem]] (LIFO sor) mélység első algoritmust eredményez. A legjobb az első ág és a kötött algoritmus olyan prioritási sor használatával érhető el, amely az alsó határon lévő csomópontokat rendezi. Példák a legelső keresési algoritmusokra, amelyek tartalmazzák ezt az előfeltételt, [[Dijkstra-algoritmus|Dijkstra algoritmusa]] és A* keresés leszármazottjának. Az első mélységű változat akkor ajánlott, ha nincs megfelelő heurisztika a kezdeti megoldás előállításához, mert gyorsan teljes megoldásokat hoz létre, és ezáltal a felső határokat.<ref>{{Hivatkozás/Könyv |last=Mehlhorn |first=Kurt |authorlink=Kurt Mehlhorn |title=Algorithms and Data Structures: The Basic Toolbox |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GenericMethods.pdf |year=2008 |publisher=Springer |page=249}}</ref> 

==== Pszeudokód ====
A fentiek [[C++|C ++-]] szerű pszeudokód megvalósítása az alábbiakban: <syntaxhighlight lang="c++" line="1">
// C++-like implementation of branch and bound, 
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
  CombinatorialProblem problem, 
  ObjectiveFunction objective_function /*f*/,
  BoundingFunction lower_bound_function /*g*/) 
{
  // Step 1 above
  double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
  CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
  problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
  CombinatorialSolution current_optimum = heuristic_solution;
  // Step 2 above
  queue<CandidateSolutionTree> candidate_queue;
  // problem-specific queue initialization
  candidate_queue = populate_candidates(problem);
  while (!candidate_queue.empty()) { // Step 3 above
    // Step 3.1
    CandidateSolutionTree node = candidate_queue.pop();
    // "node" represents N above
    if (node.represents_single_candidate()) { // Step 3.2
      if (objective_function(node.candidate()) < problem_upper_bound) {
        current_optimum = node.candidate();
        problem_upper_bound = objective_function(current_optimum);
      }
      // else, node is a single candidate which is not optimum
    }
    else { // Step 3.3: node represents a branch of candidate solutions
      // "child_branch" represents N_i above
      for (auto&& child_branch : node.candidate_nodes) {
        if (lower_bound_function(child_branch) <= problem_upper_bound) {
          candidate_queue.enqueue(child_branch); // Step 3.3.2
        }
        // otherwise, g(N_i) > B so we prune the branch; step 3.3.1
      }
    }
  }
  return current_optimum;
}
</syntaxhighlight>                

[[Fájl:AgKorlatosBackTrackv2.gif|bélyegkép|1045x1045px|Elágazás és korlátozás bemutatása lépésről-lépésre]]    

A fenti pszeudokódokra a funkciókat <code>heurisztikus megoldásnak</code> és <code>populate_candidates</code> nevezett alprogramokként meg kell adni az alkalmazandó a problémát. Az {{Mvar|''f''}} (<code>objective_function</code>) és {{Mvar|''g''}} (<code>lower_bound_function</code>) függvényobjektumokként vannak írva, és megfelelhetnek a C++ programozási nyelvben szereplő lambda kifejezéseknek, függvénymutatóknak vagy funktoroknak, többek között a felhívható objektumok között. 

=== Fejlesztések ===
Mikor <math>\mathbf{x}</math> egy vektora <math>\mathbb{R}^n</math>-nek, az ág és a kötött algoritmusok kombinálhatók intervallumelemzéssel<ref>{{Hivatkozás/Könyv |last=Moore |first=R. E. |title=Interval Analysis |year=1966 |publisher=Prentice-Hall |location=Englewood Cliff, New Jersey |isbn=0-13-476853-1}}
</ref> és a kivitelező technikákkal a globális minimum garantált körülhatárolása érdekében.<ref>
{{Hivatkozás/Könyv |last=Jaulin |first=L. |title=Applied Interval Analysis |year=2001 |publisher=Springer |location=Berlin |isbn=1-85233-219-0}}
</ref> <ref>
{{Hivatkozás/Könyv |last=Hansen |first=E.R. |title=Global Optimization using Interval Analysis |year=1992 |publisher=Marcel Dekker |location=New York}}
</ref>

== Alkalmazások ==
Ezt a megközelítést számos NP-probléma esetén alkalmazzák

* Egész számú programozás 
* Nemlineáris programozás 
* [[Az utazó ügynök problémája|Utazó eladó probléma]] (TSP)<ref name="little"/><ref>{{Hivatkozás/Könyv |last=Conway |first=Richard Walter |title=Theory of Scheduling |url=https://archive.org/details/theoryofscheduli0000conw |year=2003 |publisher=Courier Dover Publications |page=[https://archive.org/details/theoryofscheduli0000conw/page/56 56–61]}}</ref> 
* Másodlagos hozzárendelési probléma (QAP) 
* Maximális kielégítő probléma (MAX-SAT) 
* [[Legközelebbi szomszéd analízis|Legközelebbi szomszéd keresése]]<ref>{{Cite journal|author=Fukunaga|first=Keinosuke|title=A branch and bound algorithm for computing {{mvar|k}}-nearest neighbors|journal=IEEE Transactions on Computers|year=1975|pages=750–753|doi=10.1109/t-c.1975.224297}}</ref> (Keinosuke Fukunaga) 
* Flow üzlet ütemezése 
* A vágó készlet problémája 
* Hamis zaj analízis (FNA) 
* Számítógépes filogenetika 
* Állítsa be az inverziót 
* Paraméter becslés 
* 0/1 hátizsák probléma 
* Funkcióválasztás a [[Gépi tanulás|gépi tanulásban]]<ref>{{Cite journal|title=A branch and bound algorithm for feature subset selection|author=Narendra|first=Patrenahalli M.|journal=IEEE Transactions on Computers|volume=C-26|issue=9|year=1977|pages=917–922|doi=10.1109/TC.1977.1674939|url=http://www.computer.org/csdl/trans/tc/1977/09/01674939.pdf}}</ref>
* Strukturált predikció a számítógépes látásban<ref>{{Cite journal|first=Sebastian|author=Nowozin|title=Structured Learning and Prediction in Computer Vision|journal=Foundations and Trends in Computer Graphics and Vision|volume=6|issue=3–4|year=2011|pages=185–365|doi=10.1561/0600000033}}</ref> 

Az elágazó és kötött is lehet a különféle [[Heurisztika|heurisztikák]] alapja. Például lehet, hogy abba kell hagyni az elágazást, ha a felső és alsó határ közötti rés kisebb, mint egy meghatározott küszöb. Ezt akkor használják, amikor a megoldás "praktikus célokra elég jó", és jelentősen csökkentheti a szükséges számításokat. Ez a fajta megoldás különösen akkor alkalmazható, ha az alkalmazott költségfüggvény [[Zaj|''zajos'']] vagy [[Statisztika|statisztikai becslések]] eredménye, és ezért nem ismert pontosan, hanem inkább csak arról van szó, hogy egy meghatározott valószínűséggel eső értéktartományon belül helyezkedik el.

== Kapcsolat más algoritmusokkal ==
Nau ''et al.'' bemutatja az ág és a kötött általánosítását, amely szintén felveszi a [[mesterséges intelligencia]] A *, B * és [[Alfa-béta vágás|alfa-béta]] keresési algoritmusait.<ref>{{Cite journal|author=Nau|first=Dana S.|title=General branch and bound, and its relation to A∗ and AO∗|journal=Artificial Intelligence|volume=23|issue=1|year=1984|pages=29–58|url=https://www.cs.umd.edu/~nau/papers/nau1984general.pdf|doi=10.1016/0004-3702(84)90004-3}}</ref> 

== Jegyzetek ==
{{jegyzetek}}

== Fordítás ==
{{fordítás|en|Branch and bound|oldid=953131475}}

== További információk ==
* [http://sourceforge.net/projects/lipside/ LiPS] - Ingyenes, könnyen használható GUI-program, lineáris, egész és célprogramozási problémák megoldására. 
* [https://projects.coin-or.org/Cbc Cbc] - (érme vagy elágazás és kivágás) egy nyílt forráskódú vegyes egész programozási megoldó, C ++-ban írva.

[[Kategória:Lapok ellenőrizetlen fordításokkal]]
[[Kategória:Algoritmusok]]