Soluzione non esponenziale al problema del labirinto?

Question

Dato un grafico aciclico a più teste di dimensione n dove ogni nodo ha al massimo tre figli e tre genitori, esiste un algoritmo non esponenziale per identificare se esiste un percorso di lunghezza n dove due nodi non condividono lo stesso valore, e ogni valore di un set è rappresentato?

Fondamentalmente, ho un labirinto n * n in cui ogni spazio ha un valore casuale (1..n). Devo trovare un percorso (dall'alto verso il basso) di n nodi che includa ogni valore.

In questo momento sto utilizzando una ricerca in profondità, ma è T(n) = 3T(n-1) + O(1), che è O(3^n), una soluzione non ideale.

O confermando le mie paure, o indicandomi nella giusta direzione, sarebbe molto apprezzato.

Modifica: per rendere questo un po 'più concreto, ecco un labirinto con soluzioni (risolto utilizzando la soluzione di profondità).

 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

Questo problema è NP-completo e quindi non è noto se esista o meno una soluzione di tempo polinomiale. (Le condizioni standard per essere facili in pratica, ecc., sono tutte valide.) Una possibile riduzione è da 3SAT.

Supponiamo di avere un'istanza 3SAT, ad esempio (a ∨ b ∨ c) ∧ (¬a ∨ ¬ b ∨ ¬c). Mostrerò come usare "gadget" per costruire un'istanza del tuo problema. Prima di iniziare, riscrivi il problema 3SAT come (a1 ∨ b1 ∨ c1) ∧ (¬a2 ∨ ¬ b2 ∨ ¬c2) insieme a a1 = a2, b1 = b2 e c1 = c2; cioè, rende ogni evento di una variabile univoco, ma poi aggiungi la condizione che le diverse occorrenze della stessa variabile devono essere uguali.

Innanzitutto, ci assicuriamo che sia necessario selezionare il numero 0 nella prima riga, in modo da poterlo utilizzare in seguito come "sentinella" da evitare.

0 0 0 

Ora, costruiamo un gadget che fa rispettare la regola a1 = a2: (La sottolineatura _ ecco un nuovo numero unico in ogni utilizzo di questo gadget)

0 _ 0 
a1 0 ¬a1 
a2 0 ¬a2 

A causa della prima fila , devi evitare gli 0. Questo significa che prendi il percorso "a1, a2" o il percorso "¬a1, ¬a2"; il primo corrisponderà a (un po 'confusamente) l'impostazione di a a falso, mentre il secondo corrisponderà a un'impostazione a a vero. Questo perché il nostro gadget della clausola è davvero facile allora, semplicemente annotando la clausola, ad es. (Di nuovo _ qui è una nuova variabile ogni volta):

0 _ 0 
a1 b1 b2 

o

0 _ 0 
¬a1 ¬b1 ¬b2 

Infine, dal momento che hai utilizzato solo uno di A1 e ¬a1, ecc, lasciamo che si prende il quelli che non hanno utilizzato liberamente:

0 _ 0 
a1 ¬a1 0 

Ora, questo non funziona del tutto, perché uno di A1 e ¬a1 potrebbe essere stato utilizzato nel gadget scelta variabile, mentre l'altro avrebbe potuto essere utilizzato in un clausola. Pertanto, includiamo una nuova variabile @i per ciascuna clausola che è possibile utilizzare al posto di una delle variabili. Quindi se a1 variabile appare al punto 1, abbiamo

0 _ 0 
a1 ¬a1 @1 

Ecco l'output completo di una traduzione della clausola originale 3SAT (evidenziando il percorso corrispondente ad impostare un e b true, c false, e raccogliendo una dalla prima clausola), con numeri a sinistra e gloss a destra.I gadget vengono riordinati (gadget della prima clausola, quindi per ogni variabile, il gadget di uguaglianza e quindi gadget inutilizzati), ma ciò non importa in quanto sono comunque indipendenti.

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 <  

(Se si desidera che il tutto ad essere quadrata, è sufficiente includere un mucchio di zeri alla fine di ogni riga.) E 'divertente vedere che non importa quanto a risolvere questo, in fondo, sei risolvere il problema 3SAT.

Alla fine del mio post è un programma Perl frettolosamente scritto che genera uno dei tuoi problemi da un ingresso del modulo

a b c 
-a -b -c 

Il numero di variabili nell'istanza risultante del vostro problema è 11C + V + 1. Assegna al programma l'opzione -r per produrre lucentezza anziché numeri.

# 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

Sono abbastanza sicuro che questo può essere fatto in tempo polinomiale. Vorrei iniziare con un set vuoto e quindi passare attraverso le righe dall'alto in basso. Salterò qualsiasi tipo di codice e ti mostrerò come sarà lo stato in ogni fase in cui dovresti essere in grado di mettere insieme un algoritmo da lì. Sono piuttosto sicuro che il caso migliore sia leggermente peggiore di O (n^2) usando una variazione di ampiezza per la prima ricerca e tenendo traccia degli attuali buoni percorsi in una tabella.

MODIFICA: Se questo non è ancora abbastanza veloce, è possibile migliorarlo applicando Harlequin's optimization.

Per esempio:

Stato 0: R = 0 // fila P = {} // percorso impostato

// {{Path so far}, Column} 

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

P = P' 

stato 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} 
} 

Stato 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} 
} 

Risultato :
Numero di percorsi: 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

Answer 3

Consulti Una ricerca *. È tuo amico

Answer 4

È possibile provare il ant colony optimization. Produce rapidamente risultati molto buoni che sono molto vicini alla soluzione perfetta.

Answer 5

Un'ottimizzazione per Kevin Loney's solution potrebbe essere quella di unire percorsi parziali che contengono gli stessi elementi nella stessa colonna. Dovresti notare il numero di unioni con il percorso se vuoi conoscere il numero di soluzioni alla fine.

Esempio: nell'esempio 5x5, quando si arriva alla terza riga, la terza colonna ha tre percorsi che portano ad essa (1 2 5) in un certo ordine. Non devi seguire questi separatamente da questo punto, ma puoi unirli. Se vuoi conoscere il numero di soluzioni alla fine, devi solo regolare la struttura dei dati del tuo percorso, ad es. tre (1 (1 2 5)) si fonderebbero in (3 (1 2 5)).