Dinic algoritme

Dinitz's algoritme is een sterk polynoom algoritme voor het berekenen van de maximale stroom in een stroom netwerk, bedacht in 1970 door Israëlische informaticus Yefim Dinitz. Het algoritme draait in de tijd en is vergelijkbaar met de Edmonds-Karp algoritme dat loopt in de tijd, dat gebruikt verbeteringsmiddel kortste paden. De introductie van de concepten van het niveau grafiek en blokkeren stroom staat Dinic algoritme om zijn prestaties te bereiken.

Definitie

Laten een netwerk met de capaciteit en de stroom van de rand respectievelijk.

  •  anders.
  • Algoritme

    Dinic's algoritme

    • Stel voor elk.
    • Construct uit van. Indien stoppen en output.
    • Zoek een blokkerende stroming in.
    • Vergroten stroom door en ga terug naar stap 2.

    Analyse

    Aangetoond kan worden dat het aantal randen in elke blokkerende stroom toeneemt met ten minste 1 per keer en er zijn dus hoogstens blokkering stroomt in het algoritme, waarbij het aantal hoekpunten in het netwerk. Het niveau grafiek kan worden geconstrueerd door Breedte-first search tijd en een blokkerende stroming in elk niveau grafiek is te vinden in de tijd. Vandaar dat de looptijd van Dinic's algoritme is.

    Met een gegevensstructuur genaamd dynamische bomen, kan de looptijd van het vinden van een blokkerende stroom per fase verlaagd tot en derhalve bedraagt ​​Dinic algoritme kan worden verbeterd.

    Bijzondere gevallen

    In netwerken met unit capaciteit, een veel sterkere tijdgebonden houdt. Elke blokkerende stroom kan worden gevonden in de tijd, en kan worden aangetoond dat het aantal fasen niet overschrijdt en. Zo loopt het algoritme in de tijd.

    In netwerken die tijdens de oplossing van de bipartiete matching probleem, wordt het aantal fasen van begrensde derhalve leidt tot de tijdgebonden. Het resulterende algoritme wordt ook wel Hopcroft-Karp algoritme. Meer in het algemeen, deze grens geldt voor alle eenheden netwerk een netwerk waarin elk hoekpunt, behalve bron en sink, ofwel een enkele inbrengingsrand capaciteit één of enkele uitgaande rand van capaciteit ene en andere capaciteiten arbitraire gehele getallen.

    Voorbeeld

    De volgende is een simulatie van de Dinic algoritme. In het niveau grafiek, de hoekpunten met labels in het rood zijn de waarden. De paden blauwe vormen een blokkering flow.

    Geschiedenis

    Dinic algoritme werd gepubliceerd in 1970 door de voormalige Russische Wetenschapper Yefim A. Dinitz, die tegenwoordig lid van de afdeling Computer Science aan de Ben-Gurion Universiteit van de Negev, eerder dan de Edmonds-Karp algoritme, dat werd gepubliceerd in 1972, maar was eerder ontdekt. Zij toonden aan dat onafhankelijk van de plaats-Fulkerson algoritme, als iedere verhogen pad is de kortste, de lengte van het verbeteringsmiddel paden niet afneemt.

    (0)
    (0)
    Commentaren - 0
    Geen commentaar

    Voeg een reactie

    smile smile smile smile smile smile smile smile
    smile smile smile smile smile smile smile smile
    smile smile smile smile smile smile smile smile
    smile smile smile smile
    Tekens over: 3000
    captcha