Ich habe ein gerichtetes Diagramm (N, A) , wobei jeder Knoten n[i] einen Wert v[i] und einen Schwellenwert t[i] hat. Für jeden Pfeil (n[i], n[j]) gilt die Invariante v[i] <= v[j] . Ich muss die folgenden Operationen effizient implementieren:
increaseThreshold(i, x) : Setze t[i] = max(t[i], x) . Das ist trivial und nur der Vollständigkeit halber. increaseValue(i, x) : Setze v[i] = max(v[i], x) und erhöhe andere Werte nach Bedarf, so dass die obige Invariante gilt. evaluate(i) : return true wenn v[i] < t[i]
Die einfachste Implementierung würde v[i] , t[i] und die ausgehenden Pfeile für jeden Knoten speichern. Auf increaseValue(i, x) würde der Wert entlang aller ausgehenden Pfeilen propagiert (mit einer Menge "offener" Knoten wie viele andere Graphalgorithmen). Wenn v[i] für jeden Knoten gespeichert ist, ist evaluate(i) trivial.
Da increaseValue viel häufiger ist als die anderen Operationen, scheint dieser eifrige Ansatz verschwenderisch zu sein. Ich frage mich also, ob eine Lazy-Propagierung, bei der v[i] nach Bedarf neu berechnet wird, effizienter sein könnte. Dafür würde ich w[i] als Maximum aller x von increaseValue(i, x) beibehalten und compute v[j] im laufenden Betrieb berechnen, wenn evaluate(j) es benötigt. Er kann als Maximum von w[i] über alle Knoten n[i] berechnet werden, aus dem ein Pfad zu n[j] besteht. Eigentlich, sobald ich das v[j] >= t[j] kenne,
Der genaue Wert v[j] spielt keine Rolle und ich kann die Berechnung stoppen.
Leider ist dieser faule Algorithmus sehr ineffizient, also lohnt es sich nicht, auch wenn increaseValue häufiger als evaluate ist.
Ich stelle mir vor, ein "teilweise fauler" Algorithmus könnte besser sein, aber das ist nur meine Intuition und ich kann damit keine Fortschritte machen.
Ist das irgendwie ein bekanntes Problem? Irgendeine andere Idee?
Wie wäre es mit dem Zurückhalten der Fortpflanzung des Inkrements, bis Sie es auswerten müssen? Mit incrementValue wird nur der Wert aktualisiert, der Knoten als "dreckig" markiert und einer Gruppe von unreinen Knoten hinzugefügt.
Wenn Sie auswerten müssen, propagieren Sie die Inkremente für alle geänderten Knoten, beginnend mit dem größten neuen Wert. Dies sollte das Weiterleiten mehrerer Inkremente für denselben Knoten und potentielle Knoten auf Pfaden speichern (die möglicherweise unterwegs validiert werden)?
Ich habe eine einfache Idee für den "teilweise faulen" Algorithmus (keine Lösung, nur eine Idee).
Nennen wir die "einfachste Implementierung" aus meiner Frage den sagen Algorithmus, da jeder Knoten seinen Nachfolgern sagt, was zu tun ist. Lassen Sie uns den "lazy algorithm" in asking Algorithmus umbenennen, da jeder Knoten seine Vorgänger fragt, ob etwas zu tun ist.
Die Pfeile können unterteilt werden in sagen und Fragen . Alle erklärenden Pfeile werden nach increase verarbeitet, während die fragenden Pfeile bis evaluate warten. Ich denke, diese Partitionierung kann nicht beliebig sein: Für zwei beliebige Pfeile (n[i], n[j]) und (n[j], n[k]) kann ich mir nicht vorstellen, wie ich vorgehen soll, wenn erstere fragt und letzteres sagt, also muss dieser Fall verboten sein.
Dies kann sehr hilfreich sein, wenn es viele Knoten mit nur eingehenden Pfeilen gibt, die evaluate d selten bekommen, was der Fall zu sein scheint.
Es kann wahrscheinlich mit der Idee aus der anderen Antwort kombiniert werden.
Tags und Links algorithm graph-algorithm directed-graph