Lévita algoritmus - a

előző ◈ a következő

Nyilatkozat a problémát

1. lehetőség Dana hálózat autópályák összeköti a várost a moszkvai régióban. Egyes utak egyoldalú. Keresse meg a legrövidebb útvonal Moszkvából a város minden területen a város (ha csak akkor tudjuk mozgatni az utakon).







2. lehetőség Számos közötti járatok a város a világon, minden ismert költség. A költségek egy járatot a B nem lehet egyenlő a költsége a járatot B A. Keresse meg a legkisebb költség útvonal (esetleg változik) Koppenhágából Barnaul.

A hivatalos meghatározás

Dan súlyozása irányított [1] egy grafikon, anélkül, hurkok és ívek negatív tömeg [2]. Keresse meg a legrövidebb utat a csúcs az összes többi a gráf.

elnevezések

  • - egy sor gráf csúcsainak
  • - Sok élek
  • - tömeg (hossza) a borda
  • - a felső, a távolság keres, azaz a kiindulási csúcs.
  • - a jelenlegi hossza a legrövidebb utat a tetejétől a felső
  • - a csúcs előző tetején a legrövidebb út a tetejétől.
  • - vertex távolságot a már kiszámított (de talán nem teljesen);
  • - vertex távolságot amelynek kiszámítása;
  • - vertex távolságot még nem számított.
  • - számot tárolja a készülék, amelyhez a vertex i.

typedef pár borda; typedef vektor > Graph;

const int inf = 1000 * 1000 * 1000;

Legyen egy tömb D [1..n] tartalmazza az aktuális legrövidebb úthosszak. Kezdetben üres tömböt D értékek a „végtelen”, kivéve a D [s] = 0. Az adagolás befejezése után az algoritmus, ez a tömb tartalmaz végleges legrövidebb távolság.

Hagyja tömb P [1..n] tartalmazza az aktuális ősök. Csakúgy, mint egy tömb D tömb P fokozatosan változik során az algoritmus és a végén megkapja a végső értékeket.

Kezdetben az összes csomópont helyezzük több M2, kivéve a csúcsok V0, amely bekerül a beállított M1.

Minden lépésnél az algoritmus, veszünk csúcsa több M1 (felérünk elem a sorból). Legyen V - a kiválasztott csúcs. Mi lefordítani ezt a csúcson a különböző M0. Ezután megtekintheti az összes élek áradó hogy csúcs. Legyen T - ez a második végén ez a borda (azaz, nem egyenlő V), és az L - a hossza ezen a szélen.







  • Ha a T tartozik M2, akkor T átvisszük egy sor M1 végén a sorban. DT egyenlőre van beállítva DV + L.
  • Ha a T tartozik M1, akkor próbáljuk javítani a értéke DT: DT = min (DT, DV + L). Apex T nem mozog a sorban.
  • Ha a T tartozik M0, és ha lehetséges javítani DT (DT> DV + L), DT javul, és a tetején a T visszatér a beállított M1, helyezi el a tetején a sorban.

Természetesen minden frissítés tömb D frissíteni kell, és az értéket a tömb P.

A komplexitás az algoritmus

Az idő az algoritmus. A gyakorlatban azonban az algoritmus bebizonyította magának nagyon jól: munkája során a becslések szerint (kísérleti értékelés).

Összehasonlítás Dijkstra és Levitt

Összehasonlítva a módszer Dijkstra eljárás Levitt játszik az a tény, hogy egyes csomópontok feldolgozni újra, és nyer egy egyszerű algoritmus a befogadás és kizárás a csúcsok halmaza az M1. Kísérletek azt mutatják, hogy a grafikonok a „geometriai” származás, azaz grafikonok, amelyek alapján a közlekedési hálózatok és a valós távolságok, Lev módszer a leggyorsabb. Ő nyer, és a mérete a programban.

Lev módszer az is az előnye a módszer Dijkstra, hogy azt alkalmazni abban az esetben negatív hosszúságú íveket (azaz „ívhossz” - ez csak egy név, amely ad nekünk hasznos egyesületek valóság). Ha feltételezzük, hogy az értékek l (u) nem feltétlenül pozitív, megoldást a problémára a legrövidebb út sokkal bonyolultabb.

Az első nehézség az, hogy az egyszerű szabályt elveszett Dijkstra módszer határozza meg a végső kiszámított távolság egy adott ív. Ez a nehézség, mint később látni fogjuk, a költségeket, bár némi veszteség módszer hatékonyságát (szükséges ellenőrizni az összes ív, ami ezt a vertex).

A második komoly probléma: a negatív hossz a grafikonon lehet áramkörök negatív hosszának összegét az íveket (úgynevezett alakos „negatív”). Hozzátéve, hogy a negatív utat áramkör csökkenti az értékét a célfüggvény, és minél több negatív hurok fordulóban hozzátesszük, a „jobb”. Megszabadulni a végtelen csökkenő minimum egyszerűen nem lehetséges, de van két kiút a nehéz helyzetben (persze, a választás a kimenet nem tőlünk függ, hanem egy gyakorlati problémát meg kell oldani).

  • Kikapcsolja a kapcsoló áramkörök az utat, vagyis csak úgy egyszerű módon, de a tilalmat teszi a feladat nagyon nehéz.
  • Abban az esetben tekinthető negatív kontúrok, hogy a probléma nincs megoldás, és a probléma megoldása korlátozott lesz abban az esetben, ha nincs negatív kontúrok. Ebben az esetben Levitt módszer megadja a kívánt optimális megoldás, de némi módosítással, hogy „fogás” negatív kontúrok.
  • Bellman algoritmus - Ford - megoldani ugyanazt a problémát, ha a gráf élei tartalmazhat negatív súly
  • Floyd algoritmusa - Uorshella - megtalálja a legrövidebb távolság között az összes pár csúcsot
  • Johnson algoritmusa
  • Dijkstra-algoritmus - megoldani ugyanazt a problémát más módon.

jegyzetek

  1. ↑ Itt egy speciális esete egy irányított gráf irányítatlan és keverő ( „részlegesen irányított”) oszlopokat.
  2. ↑ A grafikonok negatív alkalmazott súlyok általános algoritmus - Dijkstra algoritmus potenciálok

irodalom




Kapcsolódó cikkek

előző ◈ a következő