COIN-OR::LEMON - Graph Library

Changes between Version 1 and Version 2 of Negatív körök keresése


Ignore:
Timestamp:
04/30/14 00:52:29 (5 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Negatív körök keresése

    v1 v2  
    55== Háttér ==
    66
    7 A legrövidebb utak kereséséhez szorosan kapcsolódó probléma annak eldöntése, hogy létezik-e negatív összköltségű irányított kör egy élsúlyozott gráfban. Ha ilyen kör nem létezik, akkor bármely két pont között létezik minimális költségű séta, amelyet a Bellman-Ford-algoritmussal meg is kereshetünk. Más megközelítésben azt mondhatjuk, hogy ilyenkor létezik megenegedett potenciálfüggvény: minden ''u'' csúcshoz hozzárendelhetünk egy d(''u'') potenciált, amelyre teljesül, hogy minden (''u'', ''v'') élen a c(''u'',''v'') + d(''u'') - d(''v'') redukált költség nemnegatív (vagyis d(''u'') + c(''u'',''v'') >= d(''v'')). Egy ilyen potenciálfüggvény ismeretében a legröviebb utak keresését hatékonyan tudjuk megoldani Dijkstra algoritmusával (a redukált költségeket használva).
     7A legrövidebb utak kereséséhez szorosan kapcsolódó probléma annak eldöntése, hogy létezik-e negatív összköltségű irányított kör egy élsúlyozott gráfban. Ha ilyen kör nem létezik, akkor bármely két pont között létezik minimális költségű séta, amelyet a Bellman-Ford-algoritmussal meg is kereshetünk. Más megközelítésben azt mondhatjuk, hogy ilyenkor létezik megengedett potenciálfüggvény: minden ''u'' csúcshoz hozzárendelhetünk egy d(''u'') potenciált, amelyre teljesül, hogy minden (''u'', ''v'') élen a c(''u'',''v'') + d(''u'') - d(''v'') redukált költség nemnegatív (vagyis d(''u'') + c(''u'',''v'') >= d(''v'')). Egy ilyen potenciálfüggvény ismeretében a legröviebb utak keresését hatékonyan tudjuk megoldani Dijkstra algoritmusával (a redukált költségeket használva).
    88
    99Egy érdekes és fontos feladat tehát annak eldöntése, hogy egy irányított, élsúlyozott gráf tartalmaz-e negatív kört. Olyan algoritmusokat keresünk, amelyek megadnak egy negatív kört, ha ilyen létezik, egyébként pedig egy megengedett potenciálfüggvényt. A klasszikus Bellman-Ford algoritmus alkalmas ezen probléma megoldására, de a gyakorlatban sokszor nem elég hatékony. Ugyanakkor számos hasonló, de a gyakorlatban jobban teljesítő algoritmus is született.