algorithm - examples - ¿Solución no exponencial al problema del laberinto?

o n !)

Question

Dado un gráfico acíclico multidireccional de tamaño n * en el que cada nodo tiene como máximo tres hijos y tres padres, ¿existe un algoritmo no exponencial para identificar si existe una ruta de longitud n donde dos nodos comparten el mismo valor y cada se cuenta el valor de un conjunto?

Básicamente, tengo un laberinto n * n donde cada espacio tiene un valor aleatorio (1..n). Necesito encontrar un camino (de arriba hacia abajo) de n nodos que incluya cada valor.

En este momento estoy usando una búsqueda en profundidad, pero eso es T(n) = 3T(n-1) + O(1) , que es O(3^n) , una solución no ideal.

Confirmar mis temores o señalarme en la dirección correcta sería muy apreciado.

Editar: para hacer esto un poco más concreto, aquí hay un laberinto con soluciones (resuelto usando la solución de profundidad primero).

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

Busque A * buscar. Es tu amigo

Answer 2

Puedes probar la optimización de colonia de hormigas . Rápidamente produce muy buenos resultados que están muy cerca de la solución perfecta.

Answer 3

Este problema es NP-completo, por lo que no se sabe si existe o no una solución de tiempo polinomial. (Las condiciones estándar de posiblemente ser fácil en la práctica, etc. , se aplican todas). Una posible reducción es de 3SAT.

Supongamos que tenemos una instancia 3SAT, como (a ∨ b ∨ c) ∧ (¬ a ∨ ¬b ∨ ¬c). Mostraré cómo usar "gadgets" para construir una instancia de su problema. Antes de comenzar, vuelva a escribir el problema 3SAT como (a1 ∨ b1 ∨ c1) ∧ (¬ a2 ∨ ¬2 b2 ∨ c2) junto con a1 = a2, b1 = b2, y c1 = c2; es decir, haga que cada aparición de una variable sea única, pero luego agregue la condición de que las diferentes ocurrencias de la misma variable deben ser iguales.

Primero, nos aseguramos de que debe elegir el número 0 en la primera fila, para que podamos usarlo más adelante como un "centinela" que debe evitar.

 0 0 0

Ahora, creamos un gadget que refuerza la regla a1 = a2: (El guión bajo _ aquí hay un nuevo número único en cada uso de este gadget)

 0 _ 0
a1 0 ¬a1
a2 0 ¬a2

Debido a la primera fila, debes evitar los 0. Esto significa que toma la ruta "a1, a2" o la ruta "¬a1, ¬a2"; el primero corresponderá (de forma ligeramente confusa) al establecer a a falso, mientras que el último corresponderá a un ajuste a a verdadero. Esto se debe a que nuestro gadget cláusula es realmente fácil, porque simplemente escribimos la cláusula, por ejemplo (una vez más, aquí hay una nueva variable cada vez):

 0 _ 0
a1 b1 b2

o

 0 _ 0
¬a1 ¬b1 ¬b2

Finalmente, como solo ha usado uno de a1 y ¬a1, etc., le permitimos tomar los que no ha usado libremente:

 0 _ 0
a1 ¬a1 0

Ahora, esto no funciona, porque uno de a1 y ¬a1 podría haber sido utilizado en el gadget de elección de variable, mientras que el otro podría haber sido utilizado en una cláusula. Entonces, incluimos una nueva variable @i para cada cláusula que puede tomar en lugar de una de las variables. Entonces, si la variable a1 aparece en la cláusula 1, tenemos

 0 _ 0
a1 ¬a1 @1

Aquí está el resultado completo de una traducción de la cláusula original 3SAT (resaltando la ruta correspondiente a establecer ayb en verdadero, c en falso, y eligiendo a desde la primera cláusula), con números a la izquierda y brillo a la derecha. Los gadgets se vuelven a pedir (gadgets de la primera cláusula, luego para cada variable, el gadget de igualdad y el gadget no utilizado), pero esto no importa ya que son independientes de todos modos.

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 <

(Si quieres que todo sea cuadrado, solo incluye un montón de ceros al final de cada línea.) Es divertido ver que no importa cómo resuelves esto, en el fondo, estás resolviendo ese problema 3SAT.

Al final de mi publicación hay un programa Perl escrito apresuradamente que genera uno de sus problemas a partir de una entrada del formulario

a b c
-a -b -c

El número de variables en la instancia resultante de su problema es 11C + V + 1 . Proporcione al programa el -r para producir brillo en lugar de números.

# 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 4

Estoy bastante seguro de que esto se puede hacer en tiempo polinomial. Empezaría con un conjunto vacío y luego recorrería las filas de arriba a abajo. Voy a omitir cualquier tipo de código y mostrarle cómo se vería el estado en cada paso, así que debería poder armar un algoritmo desde allí. Estoy bastante seguro de que el mejor de los casos es ligeramente peor que O (n ^ 2) usando una variación de la primera búsqueda de amplitud y haciendo un seguimiento de los buenos caminos actuales en una tabla.

EDIT: si esto todavía no es lo suficientemente rápido, puedes mejorarlo aplicando la optimización de Harlequin .

Por ejemplo:

1 2 3
3 2 1
1 2 1

Estado 0: R = 0 // Fila P = {} // Conjunto de ruta

// {{Path so far}, Column}
P'' = {
{{1}, 0}
{{2}, 1}
{{3}, 2}
}
P = P''

Estado 1: R = 1 // FILA 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}
}

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

Resultado:
Recuento de ruta: 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 5

Una optimización para la solución de Kevin Loney podría ser fusionar caminos parciales que contienen los mismos elementos en la misma columna. Debería tener en cuenta el número de fusiones con la ruta si desea saber la cantidad de soluciones al final.

Ejemplo: en su ejemplo de 5x5, cuando llega a la tercera fila, la tercera columna tiene tres rutas que llevan a ella (1 2 5) en algún orden. No tiene que seguir estos pasos por separado desde este punto, pero puede combinarlos. Si desea saber la cantidad de soluciones al final, solo tiene que ajustar la estructura de datos de su ruta, por ejemplo, tres (1 (1 2 5)) se fusionarían a (3 (1 2 5)).