Ich möchte Dinic-Algorithmus mit dynamischem Baum anwenden. Aber ich finde sehr wenige Quellen. vor allem über den dynamischen Baum. Es wäre toll, wenn es eine gute Quelle mit detaillierten erklärt oder einige einfache Quellen Code, der dynamische Baum verwendet.Dynamische Baumdatenstruktur für verbesserten Dinic-Algorithmus
Irgendjemand auf so etwas stoßen? Vielen Dank im Voraus
Die Grundidee für die Verbesserung ist die Vermeidung von vorzeitigen Pessimierung in Dinic-Algorithmus. Im Gegensatz zu Preflow/Push-Algorithmen sucht der Dinic-Algorithmus nach Wegen im Restflussdiagramm. Sobald ein solcher Fluss adressiert ist, behandelt der modifizierte Algorithmus, anstatt eine neue Suche zu starten, die Pfade, die bei der vorherigen Suche gefunden wurden.
Sie finden here eine sehr gut lesbare Einleitung, einschließlich einer Implementierung der Datenstruktur selbst. here ist ein ausführlicher Vortrag. Schließlich ist A Data Structure for Dynamic Trees (by Sleator and Tarjan) das ursprüngliche Papier, das sich auf die Implementierung der Datenstruktur selbst konzentriert.
Eigentlich habe ich zuerst zwei Quellen schnell gelesen und habe nicht viel verstanden. Aber ich verstehe Dinics Algorithmus. Vielleicht ist mein Problem ein dynamischer Baum, den ich überhaupt nicht kenne. Scheint so, als wären das die besten verfügbaren Ressourcen, lass mich langsam wieder darüber gehen. Vielen Dank! :) – arslan
@alim Dann überprüfen Sie die dritte. Ich denke, es ist derjenige, den du willst. –
Es ist gut, Links beschreibende Titel zu geben (der dritte ist eine Datenstruktur für dynamische Bäume, Daniel D. SLEATOR UND ROBERT ENDRE TARJAN), so dass Google, wenn Links unvermeidlich verrotten, helfen kann, diese Dinge wieder zu finden. In der Zwischenzeit habe ich diese Links zum Wayback-Rechner hinzugefügt. (http://web.archive.org/web/*/http://www.arl.wustl.edu/~jst/cse/542/text/sec19.pdf, zum Beispiel) – jbapple