Nicht-exponentielle Lösung für Labyrinth-Problem?

Question

Angesichts eines * n-großen mehrköpfigen azyklischen Graphen, in dem jeder Knoten höchstens drei Kinder und drei Eltern hat, gibt es einen nicht-exponentiellen Algorithmus, um zu identifizieren, ob ein n-Längen-Pfad existiert, wo zwei Knoten den gleichen Wert teilen. und jeder Wert eines Satzes wird berücksichtigt?

Grundsätzlich habe ich ein n * n Labyrinth, wo jeder Raum einen zufälligen Wert (1..n) hat. Ich muss einen Pfad (von oben nach unten) von n Knoten finden, der jeden Wert enthält.

Momentan verwende ich eine Tiefensuche, aber das ist T(n) = 3T(n-1) + O(1), was O(3^n) ist, eine nicht ideale Lösung.

Entweder bestätige ich meine Ängste, oder sie weisen mich in die richtige Richtung.

Edit: Um dies ein wenig konkreter zu machen, hier ist ein Labyrinth mit Lösungen (gelöst mit der Tiefenlösung).

 1 2 5 5 4 
1 5 1 3 5 
4 1 2 3 2 
5 5 4 4 3 
4 2 1 2 4 
S3, 5, 1, 3, 4, 2, F4 
S3, 5, 1, 3, 4, 2, F2 
S3, 5, 1, 3, 4, 2, F4 
S3, 5, 3, 2, 4, 1, F3 
S3, 5, 3, 2, 4, 1, F3 
S3, 5, 3, 2, 4, 1, F3 
S4, 5, 3, 2, 4, 1, F3 
S4, 5, 3, 2, 4, 1, F3 
S4, 5, 3, 2, 4, 1, F3 
S4, 5, 1, 3, 4, 2, F4 
S4, 5, 1, 3, 4, 2, F2 
S4, 5, 1, 3, 4, 2, F4 
S5, 4, 3, 2, 5, 1, F3 
13 total paths`

Answer 1

Dieses Problem ist NP-vollständig, und daher ist nicht bekannt, ob es eine polynomielle Lösung gibt oder nicht. (Die Standardvorgaben von möglicherweise in der Praxis einfach sein, usw., alle treffen zu.) Eine mögliche Reduzierung ist von 3SAT.

Angenommen, wir haben eine 3SAT-Instanz, z. B. (a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c). Ich werde zeigen, wie man "Gadgets" verwendet, um eine Instanz Ihres Problems zu erstellen. Bevor wir beginnen, schreiben Sie das 3SAT-Problem wie folgt um (a1 ∨ b1 ∨ c1) ∧ (¬a2 ∨ ¬b2 ∨ ¬c2) zusammen mit a1 = a2, b1 = b2 und c1 = c2; Das heißt, jedes Vorkommen einer Variablen muss eindeutig sein, aber dann muss die Bedingung hinzugefügt werden, dass unterschiedliche Vorkommen derselben Variablen gleich sein müssen.

Zuerst stellen wir sicher, dass Sie die Zahl 0 in der ersten Zeile auswählen müssen, damit wir sie später als "Sentinel" verwenden können, die Sie vermeiden müssen.

0 0 0 

Jetzt bauen wir ein Gadget, das die a1 = a2 Regel erzwingt: (Der Unterstrich _ hier ist eine neue eindeutige Nummer in jedem Gebrauch dieses Gadget)

0 _ 0 
a1 0 ¬a1 
a2 0 ¬a2 

Aufgrund der ersten Reihe , Sie müssen die 0s vermeiden. Das heißt, Sie nehmen entweder den Pfad "a1, a2" oder den Pfad "a1, a2"; ersteres wird (etwas verwirrend) entsprechen, indem a auf falsch gesetzt wird, während letzteres einer Einstellung a zu wahr entspricht. Dies liegt daran, dass unser Klausel-Gadget dann wirklich einfach ist, weil wir einfach die Klausel aufschreiben, z. (Wieder _ hier ist eine neue Variable jedes Mal):

0 _ 0 
a1 b1 b2 

oder

0 _ 0 
¬a1 ¬b1 ¬b2 

Schließlich, da Sie nur eine von a1 und ¬a1 verwendet haben, usw., wir können Sie das nehmen

0 _ 0 
a1 ¬a1 0 

Nun, dies funktioniert nicht ganz, weil einer von a1 und ¬a1 könnte verwendet wurde, in der variablen Wahl Gadget, während der andere könnte verwendet wurde, in ein: diejenigen, die Sie haben nicht frei genutzt Klausel. Daher fügen wir eine neue Variable @i für jede Klausel ein, die Sie anstelle einer der Variablen verwenden können. Also, wenn Variable a1 in Klausel 1 erscheint, haben wir

0 _ 0 
a1 ¬a1 @1 

Hier ist die komplette Ausgabe einer Übersetzung der ursprünglichen 3SAT-Klausel (Hervorhebung des Pfades entsprechen a und b wahr, c auf false zu setzen und eine Kommissionierung aus dem ersten Satz), mit Zahlen auf der linken Seite und Glanz auf der rechten Seite.Die Gadgets werden neu angeordnet (Gadgets für die erste Klausel, dann für jede Variable, das Gadget "Gleichheit" und das nicht verwendete Gadget). Dies ist jedoch egal, da sie unabhängig sind.

0  0 < 0    .  . < .  
0  8 < 0    .  _ < .  
2 < 4  6    a1 < b1  c1  
0  16 < 0    .  _  .  
11  13  15 <   -a2  -b2  -c2<  
0  17 < 0    .  _ < .  
2  0  3 <   a1  .  -a1<  
10  0  11 <   a2  .  -a2<  
0  18 < 0    .  _ < .  
2  3  1 <   a1  -a1  @1 <  
0  19 < 0    .  _  .  
10 < 11  9    a2 < -a2  @2  
0  20 < 0    .  _ < .  
4  0  5 <   b1  .  -b1<  
12  0  13 <   b2  .  -b2<  
0  21 < 0    .  _ < .  
4 < 5  1    b1 < -b1  @1  
0  22 < 0    .  _ < .  
12 < 13  9    b2 < -b2  @2  
0  23 < 0    .  _ < .  
6 < 0  7    c1 < .  -c1  
14 < 0  15    c2 < .  -c2  
0  24 < 0    .  _ < .  
6  7 < 1    c1  -c1< @1  
0  25 < 0    .  _ < .  
14  15  9 <   c2  -c2  @2 <  

(Wenn Sie die ganze Sache sein Platz will, sind nur ein paar Nullen am Ende jeder Zeile.) Es macht Spaß, dass, egal, um zu sehen, wie Sie dieses Problem lösen, am Herzen, du bist Lösung dieses 3SAT-Problems.

Am Ende meines Posts ist ein hastig geschriebenes Perl-Programm, das eine Ihrer Probleme von einem Eingang des Formulars

a b c 
-a -b -c 

Die Anzahl der Variablen in der resultierenden Instanz des Problems 11C + V + 1 ist erzeugt. Geben Sie dem Programm den -r Schalter, um Glanz statt Zahlen zu erzeugen.

# Set useful output defaults 
$, = "\t"; $\ = "\n"; 

# Process readability option and force sentinel 
my $r = "0"; 
if($ARGV[0] =~ /-r/) { shift; $r = "."; } 
print $r, $r, $r; 

# Clause gadgets 
my(%v, %c, $m, $c); 
$m = 1; 
while(<>) { 
    my(@v, @m); 
    $c = $m++; 
    chomp; @v = split; 
    for my $v (@v) { 
     push @{$v{strip($v)}}, -1; # hack, argh! 
     push @m, ($r ? $v.@{$v{strip($v)}} : $m + neg($v)); 
     $c{($r ? (strip($v).@{$v{strip($v)}}) : $m)} = $c; 
     $v{strip($v)}->[-1] = ($r ? (strip($v).@{$v{strip($v)}}) : $m); 
     $m += 2 unless $r; 
    } 
    print $r, newv(), $r; 
    print @m; 
} 

# Variable gadget 
for my $v (sort keys %v) { 
    # Force equal 
    print $r, newv(), $r; 
    for my $n (@{$v{$v}}) { 
     print $n, $r, ($r ? "-".$n : $n+1); 
    } 

    # Unused 
    for my $n (@{$v{$v}}) { 
     print $r, newv(), $r; 
     print $n, ($r ? "-".$n : $n+1), ($r ? "\@".$c{$n} : $c{$n}); 
    } 
} 

# Strip leading - 
sub strip { 
    my($v) = @_; 
    return substr $v, neg($v); 
} 

# Is this variable negative? 
sub neg { 
    my($v) = @_; 
    return "-" eq substr($v, 0, 1); 
} 

# New, unused variable 
sub newv { 
    return "_" if $r; 
    return $m++; 
} 

Answer 2

Ich bin mir ziemlich sicher, dass dies in polynomieller Zeit getan werden kann. Ich würde mit einem leeren Satz beginnen und dann die Zeilen von oben nach unten durchlaufen. Ich werde jede Art von Code überspringen und Ihnen zeigen, wie der Zustand aussehen würde, bei jedem Schritt sollten Sie in der Lage sein, einen Algorithmus von dort aus zusammenzustellen. Ich bin mir ziemlich sicher, dass der beste Fall etwas schlechter ist als O (n^2), indem man eine Variation der Breite der ersten Suche verwendet und die aktuellen guten Pfade in einer Tabelle verfolgt.

EDIT: Wenn dies noch nicht schnell genug ist, können Sie es verbessern, indem Sie Harlequin's optimization anwenden.

Beispiel:

Zustand 0: R = 0 // Row P = {} // Wegmenge

// {{Path so far}, Column} 

P' = { 
    {{1}, 0} 
    {{2}, 1} 
    {{3}, 2} 
} 

P = P' 

Zustand 1: R = 1 // ROW P = { {{1}, 0} {{2}, 1} {{3}, 2} }

P' = { 
    {{1 3}, 0} 
    {{1 2}, 1} 
    {{2 3}, 0} 
    {{2 1}, 2} 
    {{3 2}, 1} 
    {{3 1}, 2} 
} 

Zustand 2: R = 2 P = { {{1 3}, 0} {{1 2 }, 1} {{2 3}, 0} {{2 1}, 2} {{3 2}, 1} {{3 1}, 2} }

P' = { 
    {{1 3 2}, 1} 
    {{2 3 1}, 0} 
    {{3 2 1}, 0} 
    {{3 2 1}, 2} 
    {{3 1 2}, 1} 
} 

Ergebnis :
Pfadanzahl: S1 1 3 2 F2
S2 2 3 1 F1
S3 3 2 1 F1
S3 3 2 1 F3
S3 3 1 2 F2

Answer 3

A * -Suche nachzuschlagen. Es ist dein Freund.

Answer 4

Sie können versuchen, die ant colony optimization. Es liefert schnell sehr gute Ergebnisse, die der perfekten Lösung sehr nahe kommen.

Answer 5

Eine Optimierung für Kevin Loney's solution könnte sein, Teilpfade zusammenzuführen, die dieselben Elemente in derselben Spalte enthalten. Sie müssen die Anzahl der Zusammenführungen mit dem Pfad notieren, wenn Sie die Anzahl der Lösungen am Ende wissen möchten.

Beispiel: In Ihrem 5x5 Beispiel, wenn Sie in der dritten Zeile ankommen, hat die dritte Spalte drei Pfade, die (1 2 5) in einer bestimmten Reihenfolge enthalten. Sie müssen diese nicht separat von diesem Punkt aus verfolgen, sondern können sie zusammenführen. Wenn Sie die Anzahl der Lösungen am Ende wissen möchten, müssen Sie nur Ihre Pfaddatenstruktur anpassen, z. drei (1 (1 2 5)) würden zu (3 (1 2 5)) verschmelzen.