Datenstruktur für kürzeste Wege

Sei ein ungewichteter ungerichteter Graph mit Ecken und Kanten. Ist es möglich, vorzuverarbeiten und eine Datenstruktur der Größe erzeugen, damit Anfragen der Form "Abstand zwischen und " in der Zeit O (n) beantwortet werden können ? $G$ $n$ $m$ $G$ $m \cdot \mathrm{polylog}(n)$ $u$ $v$

Das Problem scheint zu grundlegend, um ungelöst zu sein.

graph-theory graph-algorithms ds.data-structures Ilyaraz
quelle

Als Antwort auf Ihre abschließende Bemerkung zu „Too Basic to Unvolved“ (zu einfach, um ungelöst zu sein): Wenn die Abfrage in einer konstanten Zeit beantwortet werden muss, ist sie in der Tat gut untersucht. Der Punkt Ihrer Frage ist jedoch, dass Sie O (n) Zeit für eine Abfrage einräumen (anstelle von O (1) oder trivialem O (m)). Obwohl ich denke, dass es eine interessante Frage ist, denke ich nicht, dass die Frage von grundlegender Bedeutung ist.

Tsuyoshi Ito

@TsuyoshiIto - Ich verstehe nicht, warum die Frage ihre "fundamentale Bedeutung" verliert, wenn sie superkonstante, aber sublineare Abfragezeiten zulässt. Angenommen, ich kann das obige Problem mit der Einschränkung lösen, dass Abstandsabfragen für einige in beantwortet werden können und die Verarbeitungszeit höchstens beträgt - würde mir das nicht einen subkubischen Algorithmus für die Berechnung der kürzesten Wege geben? Ich persönlich halte dies für eine sehr interessante Frage.

O (n^{1 - ε})

$O(n^{1-\varepsilon})$

ε > 0

$\varepsilon > 0$

O (n^{3 - ε})

$O(n^{3 - \varepsilon})$

Rachit

Ich weiß nicht, ob es einen allgemeinen Weg gibt oder nicht, aber es gibt einen guten Weg in Diagrammen mit begrenzter Baumbreite. Weitere Informationen finden Sie unter Abfrage des kürzesten Pfads in Diagrammen mit begrenzter Baumbreite

Saeed,

Auch wenn , können Sie einen Baum mit dem kürzesten Pfad erstellen (von jedem Knoten ausgehend) und dann die Abfrage nach dem kürzesten Pfad (nach verwandter Wurzel) in beantworten oder auf ähnliche Weise konstruieren eine Datenstruktur mit weniger Speichergröße.

m = Ω (n^{2})

$m = \Omega(n^2)$

O (n)

$O(n)$

Saeed

Antworten:

Das ist eine sehr interessante Frage. Auf hoher Ebene fragen Sie sich, ob Sie ein Diagramm so vorverarbeiten können, dass kürzeste Pfadabfragen unabhängig von der Dichte des Diagramms werden, ohne viel zusätzlichen Platz zu benötigen - interessant, aber wie Sie sagen, ungelöst.

Wenn Sie mit ungefähren Entfernungen zufrieden sind, finden Sie hier eine Möglichkeit, eine Annäherung zu erhalten . Sei ein gewichteter ungerichteter Graph mit Knoten und Kanten. In der folgenden Abhandlung wird gezeigt, dass das Entwerfen von Datenstrukturen für Graphen mit Kanten für Abstandsabfragen nicht schwieriger ist als für Graphen, bei denen jeder Knoten einen durch begrenzten Grad aufweist : $2$ $G$ $n$ $m$ $m$ $m/n$

R. Agarwal, PB Godfrey, S. Har-Peled, Ungefähre Entfernungsabfragen und kompaktes Routing in spärlichen Diagrammen, INFOCOM 2011

Nehmen wir also an, dass ein Grad-begrenzter Graph ist. Stichprobe Knoten gleichmäßig zufällig; Nennen Sie diese Orientierungspunkte. Speichern Sie während der Vorverarbeitungsphase die Entfernung von jedem Orientierungspunktknoten zu jedem anderen Knoten im Diagramm. dies erfordert Raum. Speichern Sie für jeden Knoten den nächsten Orientierungspunktknoten . Speichern Sie das Diagramm auch in der Datenstruktur, beispielsweise als Adjazenzliste. $G$ $m/n$ $\alpha = O(m/n)$ $O(m)$ $u$ $\ell(u)$

Wenn der Abstand zwischen und abgefragt wird , wachsen Kugeln um beide Knoten - Kugel des Knotens ist definiert als die Menge von Knoten, die strikt näher an als an seinem nächsten Orientierungspunktknoten, z. B. . Es kann gezeigt werden, dass die Größe jeder Kugel erwartungsgemäß ist. Sei , wobei die Kugel des Knotens und die Menge der Nachbarn der Knoten in . Es kann gezeigt werden , dass die Größe ist , in der Erwartung. $u$ $v$ $w$ $w$ $\ell(w)$ $O(n^2/m)$ $\Gamma(u) = B(u) \cup N(B(u))$ $B(u)$ $u$ $N(B(u))$ $B(u)$ $\Gamma(u)$ $O(n)$

Beantworten der Abfrage: Wenn , geben Sie ; sonst, wenn , gib ; sonst gib . Es ist leicht zu zeigen, dass dies eine Annäherung ist. $\Gamma(u) \cap \Gamma(v) \neq \emptyset$ $\min_{x \in \Gamma(u) \cap \Gamma(v)} \{d(u, x) + d(v, x)\}$ $d(u, \ell(u)) \leq d(v, \ell(v))$ $d(u, \ell(u)) + d(\ell(u), v)$ $d(v, \ell(v)) + d(\ell(v), u)$ $2$

In Bezug auf die Abfragezeit ist zu beachten, dass das Wachsen von Bällen -Zeit für einen Graph mit Grad-Grenze benötigt. Das Konstruieren von und gegebenen jeweiligen Bällen benötigt Zeit (da Nachbarn in der Datenstruktur gespeichert sind); und die Überprüfung, ob leer ist oder nicht, dauert ebenfalls . $O(n)$ $m/n$ $\Gamma(u)$ $\Gamma(v)$ $O(n)$ $\Gamma(u) \cap \Gamma(v)$ $O(n)$

Die obigen Grenzen sind in Erwartung; Ich denke, es ist einfach, die Konstruktion zu derandomisieren. Leider scheint diese Technik keine bessere Annäherung als . Es ist allerdings eine sehr interessante Frage ... $2$

Rachit
quelle

Die obige Technik nutzt nicht die Tatsache aus, dass Ihr Eingabediagramm ungewichtet ist. Vielleicht gibt es etwas Interessantes, das Sie tun können, indem Sie diese Tatsache ausnutzen, aber ich kann mir keine Möglichkeit vorstellen, genaue Entfernungen abzurufen. Zum Beispiel ist es möglich, die Abfragezeit auf zu reduzieren und die Distanz durch begrenzen , wobei die exakte Distanz zwischen und .

O (n^{2} / m)

$O(n^2/m)$

2 d + 1

$2d+1$

d

$d$

u

$u$

v

$v$

Rachit

Mir wurde klar, dass ich nicht verstehe, warum es sich um eine 2-Approximation handelt. Thorup-Zwick ergibt in den gleichen Situationen 3-ca.

Ilyaraz

@ilyaraz: Beachten Sie, dass das Thorup-Zwick-Schema keine Überprüfung von erfordert (und daher Anfragen in nahezu konstanter Zeit beantwortet). Siehe das oben erwähnte Papier für Stretch Proof.

Γ (u) \cap Γ (v)

$\Gamma(u) \cap \Gamma(v)$

2

$2$

Rachit

Was Sie brauchen, nennt man "Distanz-Orakel". Leider kenne ich Distanz-Orakel nicht sehr gut, so dass ich nur auf die wegweisende Arbeit von Thorup und Zwick verweisen kann:

Mikkel Thorup und Uri Zwick. Ungefähre Entfernung Orakel. STOC '01, 2001.

Hier ist ein Auszug aus dem Abstract:

Sei ein ungerichteter gewichteter Graph mit und . Sei eine ganze Zahl. Wir zeigen, dass in der erwarteten Zeit vorverarbeitet werden kann , wobei eine Datenstruktur der Größe konstruiert wird , so dass jede folgende Datenstruktur entsteht Entfernungsabfrage kann ungefähr in Zeit beantwortet werden. Die ungefähre zurückgegebene Distanz ist maximal , dh der Quotient aus der Division der geschätzten Distanz durch die tatsächliche Distanz liegt zwischen 1 und . Der Platzbedarf unseres Algorithmus ist [...] im Wesentlichen optimal. $G = (V, E)$ $|V| = n$ $|E| = m$ $k$ $G = (V, E)$ $O(kmn^{1/k})$ $O(kn^{1+1/k})$ $O(k)$ $2k - 1$ $2k - 1$

Nach ihren Ergebnissen ist das, was Sie verlangen, grundsätzlich auch für gewichtete Graphen machbar: Wenn Sie wählen, erhalten Sie ein Entfernungsorakel der Größe das in der erwarteten Zeit und das Ihre kürzesten Pfadabfragen mit beantworten kann -Dehnung in Zeit! $k=1$ $O(n^2)$ $O(mn)$ $1$ $O(1)$

Distance Orakel ist ein sehr gut erforschtes Gebiet, so dass Sie, glaube ich, weiter graben können.

Gabor Retvari
quelle

Zeitschriftenfassung: JACM 2005 .

Tsuyoshi Ito

Mit kann man naiv eine Nachschlagetabelle speichern. Daher ist dieses Papier (das mir bekannt war) hier irrelevant.

O (n^{2})

$O(n^2)$

Ilyaraz

Meinetwegen. Das Ergebnis, das Ihrer Anforderung von AFAIK am nächsten kommt, ist für Diagramme mit dem Durchschnittsgrad , die Strecken-2-Pfade mit Leerraum in der -Anfrage ergeben Zeit. (R. Agarwal, P. Godfrey und S. Har-Peled, "Ungefähre Entfernungsabfragen und kompaktes Routing in spärlichen Diagrammen", INFOCOM 2011.)

Θ (\log n)

$\Theta(\log n)$

O (n^{3 / 2})

$O(n^{3/2})$

O (\sqrt{n})

$O(\sqrt{n})$

Gabor Retvari,

Durch die Einbettung von Metriken nach Bourgain in kann ein Orakel mit dem Leerzeichen , der Abfragezeit und dem multiplikativen Fehler .

ℓ_{1}

$\ell_1$

O (n \log^{2} n)

$O(n \log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log n)

$O(\log n)$

Ilyaraz