Das Pfadberechnung bei erzwungenen eindeutigen Knotenattributen - Welchen Algorithmus sollte ich verwenden?

Question

Aktualisierung 2011-12-28: Hier ist ein Blog-Beitrag mit einer weniger vagen Beschreibung des Problems, das ich lösen wollte, meiner Arbeit daran und meiner aktuellen Lösung: Beobachten, wie jedes MLB-Team ein Spiel spielt

---

Ich versuche, eine Art eigenartige Pfadfindungs-Herausforderung zu lösen. Ich habe einen azyklischen gerichteten Graphen, und jede Kante hat einen Distanzwert. Und ich möchte den kürzesten Weg finden. Einfach, oder? Nun, es gibt ein paar Gründe, warum ich nicht einfach Dijkstras oder A* verwenden kann.

1. Es ist mir überhaupt nicht wichtig, was der Startknoten meines Pfades ist, noch der Endknoten. Ich benötige einen Pfad, der genau 10 Knoten enthält. Aber:
2. Jeder Knoten hat ein Attribut, sagen wir mal, es ist die Farbe. Jeder Knoten hat eine von 20 verschiedenen möglichen Farben.
3. Der Pfad, den ich zu finden versuche, ist der kürzeste Pfad mit genau 10 Knoten, wobei jeder Knoten eine andere Farbe hat. Ich möchte nicht, dass irgendein Knoten in meinem Pfad die gleiche Farbe wie ein anderer Knoten hat.
4. Es wäre schön, meinen Pfad dazu zwingen zu können, einen Wert für eines der Attribute zu haben ("mindestens ein Knoten muss blau sein", zum Beispiel), aber das ist nicht wirklich notwendig.

Das hier ist ein vereinfachtes Beispiel. Mein vollständiger Datensatz hat tatsächlich drei verschiedene Attribute für jeden Knoten, die alle einzigartig sein müssen, und ich habe 2k+ Knoten, von denen jeder durchschnittlich 35 ausgehende Kanten hat. Da ein perfekter "kürzester Pfad" exponential oder faktoriell sein kann, ist eine erschöpfende Suche wirklich keine Option. Wonach ich wirklich suche, ist eine Approximation eines "guten Pfades", der das Kriterium unter #3 erfüllt.

Kann mir jemand einen Algorithmus nennen, den ich verwenden könnte (auch modifiziert)?

---

Einige Statistiken zu meinem vollständigen Datensatz:

• Gesamte Knoten: 2430
• Gesamte Kanten: 86524
• Knoten ohne eingehende Kanten: 19
• Knoten ohne ausgehende Kanten: 32
• Die meisten ausgehenden Kanten: 42
• Durchschnittliche Kanten pro Knoten: 35,6 (in beide Richtungen)
• Aufgrund der Natur der Daten weiß ich, dass der Graph azyklisch ist
• Und im vollständigen Datensatz suche ich nach einem Pfad der Länge 15, nicht 10

Answer 1

Wenn die Anzahl der möglichen Werte niedrig ist, können Sie den Floyd-Algorithmus mit einer leichten Modifikation verwenden: Für jeden Pfad speichern Sie eine Bitmap, die die bereits besuchten unterschiedlichen Werte darstellt. (In Ihrem Fall wird die Bitmap pro Pfad 20 Bits breit sein).

Dann, wenn Sie den Längenvergleich durchführen, verknüpfen Sie auch Ihre Bitmaps mit UND, um zu überprüfen, ob es sich um einen gültigen Pfad handelt, und wenn ja, verknüpfen Sie sie mit ODER und speichern das als neue Bitmap für den Pfad.

Answer 2

Es ist der Fall, wenn die Frage tatsächlich den größten Teil der Antwort enthält.

Führen Sie eine breitensuche von allen Wurzelknoten aus durch. Wenn die Anzahl der parallel durchsuchten Pfade eine bestimmte Grenze überschreitet, lassen Sie die längsten Pfade fallen. Die Pfadlänge kann gewichtet werden: Letzte Kanten können das Gewicht 10 haben, Kanten, die vor 9 Sprüngen passiert wurden - Gewicht 1. Es ist auch möglich, eine geringere Gewichtung für alle Pfade zuzuweisen, die das bevorzugte Attribut haben oder Pfade, die durch die schwach verbundenen Knoten führen. Speichern Sie die letzten 10 Knoten im Pfad in der Hash-Tabelle, um Dopplungen zu vermeiden. Und speichern Sie irgendwo die minimale Summe der letzten 9 Kantengrößen zusammen mit dem kürzesten Pfad.

Answer 3

Hast du es mit einem geradlinigen Ansatz versucht und bist gescheitert? Aus deiner Beschreibung des Problems sehe ich keinen Grund, warum ein einfacher gieriger Algorithmus wie die Tiefensuche durchaus ausreichen könnte:

• Wähle einen Startknoten aus.
• Überprüfe die direkten Nachbarn, ob es Knoten gibt, die zum Pfad hinzugefügt werden können. Erweitere den Pfad mit einem von ihnen und wiederhole den Prozess für diesen Knoten.
• Scheiterst du, geh zurück zum letzten erfolgreichen Zustand und versuche es mit einem neuen Nachbarn.
• Wenn dir die Nachbarn ausgehen, kann dieser Knoten nicht der Startknoten eines Pfades sein. Probiere es mit einem anderen.
• Wenn du 10 Knoten hast, bist du fertig.

Gute Heuristiken für die Auswahl eines Startknotens sind schwer zu geben, ohne Kenntnisse darüber, wie die Attribute verteilt sind, aber es ist möglich, dass es vorteilhaft ist, zuerst Knoten mit hohem Grad zu wählen.

Answer 4

Es sieht so aus, als wäre eine gierige Tiefensuche Ihre beste Wahl. Mit einer vernünftigen Verteilung von Attributwerten denke ich, dass das Finden einer einzigen gültigen Sequenz in erwarteter konstanter Zeit E[O(1)] liegt. Ich könnte das wahrscheinlich beweisen, aber es könnte einige Zeit dauern. Der Beweis würde die Annahme verwenden, dass es eine nicht-null Wahrscheinlichkeit gibt, dass bei jedem Schritt ein gültiges nächstes Segment der Sequenz gefunden werden könnte.

Die gierige Suche würde in den Backtracking übergehen, sobald die eindeutige Attributwertbeschränkung verletzt wird. Die Suche endet, wenn ein Pfad von 15 Segmenten gefunden wird. Wenn wir meine Vermutung akzeptieren, dass jede Sequenz in E[O(1)] gefunden werden kann, dann geht es nur darum, wie viele parallele Suchvorgänge durchgeführt werden sollen.

Answer 5

Für diejenigen, die experimentieren möchten, hier ist ein (postgres) SQL-Skript, um einige gefälschte Daten zu generieren.

SET search_path='tmp';

-- TABELLE nodes CASCADE löschen;
CREATE TABLE nodes
    ( num INTEGER NOT NULL PRIMARY KEY
    , color INTEGER
    -- Redundante Felder, um {Anfang,Ende} von Pfaden zu kennzeichnen
    , is_root boolean DEFAULT false
    , is_terminal boolean DEFAULT false
    );

-- TABELLE edges CASCADE löschen;
CREATE TABLE edges
    ( numfrom INTEGER NOT NULL REFERENCES nodes(num)
    , numto INTEGER NOT NULL REFERENCES nodes(num)
    , cost INTEGER NOT NULL DEFAULT 0
    );

-- Einige Knoten generieren, Farbe zufällig festlegen
INSERT INTO nodes (num)
SELECT n
FROM generate_series(1,2430) n
WHERE 1=1
    ;
UPDATE nodes SET COLOR= 1+TRUNC(20*random() );

-- (teilweises) kartesisches Produkt von Knoten*Knoten. Die Reihenfolge garantiert einen DAG.
INSERT INTO edges(numfrom,numto,cost)
SELECT n1.num ,n2.num, 0
FROM nodes n1 ,nodes n2
WHERE n1.num < n2.num
AND random() < 0.029
    ;

UPDATE edges SET cost = 1+ 1000 * random();

ALTER TABLE edges
    ADD PRIMARY KEY (numfrom,numto)
    ;

ALTER TABLE edges
    ADD UNIQUE (numto,numfrom)
    ;

UPDATE nodes no SET is_root = true
WHERE NOT EXISTS (
    SELECT * FROM edges ed
    WHERE ed.numfrom = no.num
    );
UPDATE nodes no SET is_terminal = true
WHERE NOT EXISTS (
    SELECT * FROM edges ed
    WHERE ed.numto = no.num
    );

SELECT COUNT(*) AS nnode FROM nodes;
SELECT COUNT(*) AS nedge FROM edges;
SELECT color, COUNT(*) AS cnt FROM nodes GROUP BY color ORDER BY color;

SELECT COUNT(*) AS nterm FROM nodes no WHERE is_terminal = true;

SELECT COUNT(*) AS nroot FROM nodes no WHERE is_root = true;

WITH zzz AS    (
    SELECT numto, COUNT(*) AS fanin
    FROM edges
    GROUP BY numto
    )
SELECT zzz.fanin , COUNT(*) AS cnt
FROM zzz
GROUP BY zzz.fanin
ORDER BY zzz.fanin
    ;

WITH zzz AS    (
    SELECT numfrom, COUNT(*) AS fanout
    FROM edges
    GROUP BY numfrom
    )
SELECT zzz.fanout , COUNT(*) AS cnt
FROM zzz
GROUP BY zzz.fanout
ORDER BY zzz.fanout
    ;

COPY nodes(num,color,is_root,is_terminal)
TO '/tmp/nodes.dmp';

COPY edges(numfrom,numto, cost)
TO '/tmp/edges.dmp';