Nicht-exponentielle Lösung Problem Labyrinth?
https://stackoverflow.com/questions/535859
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Bei einem gegebenen * n-sized mehrköpfigen azyklischen Graphen, wobei jeder Knoten höchstens drei Kinder und drei Eltern hat, gibt es einen nicht-exponentiellen Algorithmus zu erkennen, ob ein n-Länge Pfad vorhanden ist, wo keine zwei Knoten den gleichen Wert teilen und jeder Wert eines Satzes berücksichtigt wird?
Grundsätzlich habe ich eine n * n maze wobei jeder Raum einen zufälligen Wert (1..n). Ich brauche einen Weg zu finden (von oben nach unten) von n Knoten, die jeden Wert enthält.
Im Moment verwende ich eine Tiefensuche, aber das ist T(n) = 3T(n-1) + O(1), die O(3^n) ist, eine nicht-ideale Lösung.
Entweder bestätigt meine Befürchtungen, oder zeigen Sie mir in die richtige Richtung sehr geschätzt wird.
Edit:. Etwas konkreteres dies zu machen, hier ist ein Labyrinth mit Lösungen (gelöst mit der depth-first-Lö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`
Lösung
Dieses Problem ist NP-vollständig, und so ist es nicht bekannt, ob es eine Polynom Zeitlösung. (Die Standard-Maßgaben von möglicherweise in der Praxis ist einfach, etc. , die alle gelten.) Eine mögliche Reduktion von 3SAT ist.
Angenommen, wir eine 3SAT-Instanz haben, wie zum Beispiel (a ∨ b ∨ c) ∧ (¬A ∨ ∨ ¬B ¬c). Ich werde zeigen, wie „Gadgets“ verwenden, um eine Instanz des Problems zu bauen. Bevor wir beginnen, die neu zu schreiben 3SAT Problem wie (a1 b1 ∨ ∨ c1) ∧ (¬a2 ∨ ¬b2 ∨ ¬c2) zusammen mit a1 = a2, b1 = b2 und c1 = c2; Das heißt, jedes Vorkommen einer Variablen einzigartig machen, aber dann die Bedingung hinzu, dass unterschiedliche Ausprägungen der gleichen Variablen gleich sein müssen.
Zuerst stellen wir sicher, dass Sie die Nummer 0 in der ersten Reihe holen 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, müssen Sie die 0er vermeiden. Dies bedeutet, dass Sie entweder den Pfad „a1, a2“ oder den Pfad „¬a1, ¬a2“; Erstere wird, entsprechen (leicht verwechselbar) eine Einstellung auf falsch, während die letztere auf eine Einstellung a true entspricht. Dies liegt daran, unsere Klausel Gadget ist wirklich einfach dann, weil wir einfach die Klausel aufschreiben, z.B. (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 lassen Sie diejenigen, nehmen Sie nicht frei genutzt haben:
0 _ 0
a1 ¬a1 0
Nun, dies funktioniert nicht ganz, weil einer von a1 und ¬a1 könnte in der Variablen Wahl Gadget verwendet wurde, während die andere in einer Klausel verwendet worden sein könnten. Also, wir sind eine neue Variable @i für jede Klausel, die Sie anstelle von einer der Variablen erfolgen kann. 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 der Pfad entspricht a und b wahr, c auf false zu setzen und eine von der ersten Klausel Kommissionierung) mit Zahlen auf der linken Seite und Glanz auf die richtig. Die Geräte sind neu geordnet (erste Klausel Gadgets, dann für jede Variable, die Gleichheit Gadget und dann ungenutzt Gadget), aber das spielt keine Rolle, da sie ohnehin 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, ist nur ein paar Nullen am Ende jeder Zeile.) Es macht Spaß zu sehen, dass, egal wie Sie dieses Problem lösen, am Herzen liegt, Sie zu lösen, dass 3SAT Problem .
Am Ende meines Posts ist ein hastig geschriebenes Perl-Programm, das eine Ihrer Probleme aus einem Eingang der Form erzeugt
a b c
-a -b -c
Die Anzahl der Variablen in der resultierenden Instanz des Problems ist 11C + V + 1. Geben Sie das Programm die -r Schalter zu erzeugen, statt Zahlen Glanz.
# 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++;
}
Andere Tipps
Ich bin mir ziemlich sicher, dass dies in Polynomialzeit erfolgen. Ich würde mit einem eine leere Menge beginnen und dann die Schleife durch die Reihen von oben nach unten. Ich werde jede Art von Code überspringen und zeigen Ihnen, was der Staat bei jedem Schritt aussehen würde Sie sollten zusammen einen Algorithmus von dort aus setzen können. Ich bin mir ziemlich sicher, dass der beste Fall ist etwas schlechter als O (n ^ 2) eine Variation der Breite unter Verwendung eines erste Spur der aktuellen guten Wege in einer Tabelle suchen und zu halten.
EDIT: Wenn dies immer noch nicht schnell genug ist, dass Sie es durch die Anwendung verbessern Harlekin Optimierung .
Beispiel:
1 2 3
3 2 1 |
1 2 1
Der Zustand 0: R = 0 // Row P = {} // Pfad Set
// {{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}
}
Der 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:
Pfad-Zähler: 5
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
Sie können versuchen, die Ameisenart Optimierung . Es wurde schnell liefert sehr gute Ergebnisse, die sehr nah an der perfekten Lösung.
Eine Optimierung für Kevin Loney Lösung sein könnte fusionieren Teilpfade, die die gleichen Elemente in der gleichen Spalte enthalten. Sie müßten die Anzahl der Verschmelzungen mit dem Pfad beachten, wenn Sie die Anzahl der Lösungen am Ende wissen wollen.
Beispiel: In Ihrem 5x5 Wenn Sie beispielsweise in der dritten Reihe ankommen, die dritte Spalte hat drei Wege, die dazu führen, dass (1 2 5) in einer bestimmten Reihenfolge enthalten. Sie müssen diese nicht getrennt von diesem Punkt folgen, sondern können sie verschmelzen. Wenn Sie die Anzahl der Lösungen am Ende wissen wollen, müssen Sie nur noch Ihre Weg-Datenstruktur anpassen, zum Beispiel drei (1 (1 2 5)) würde fusionieren bis (3 (1 2 5)).
A * Suche nachschlagen. Es ist dein Freund.
