solución no exponencial en maze problema?
https://stackoverflow.com/questions/535859
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Dado un *-n tamaño de múltiples cabezas gráfico acíclico donde cada nodo tiene como máximo tres hijos y tres padres, ¿existe un algoritmo no exponencial para identificar si existe una ruta de n-longitud donde no hay dos nodos comparten el mismo valor , y cada valor de un conjunto se tiene en cuenta?
Básicamente, tengo una n laberinto n *, donde cada espacio tiene un valor aleatorio (1..n). Necesito encontrar un camino (desde la parte superior a la parte inferior) de n nodos, que incluye 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.
Ya sea que confirma mis temores, o yo que apunta en la dirección correcta sería muy apreciada.
Edit:. Para hacer esto un poco más concreto, aquí es un laberinto con soluciones (solucionado utilizando 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`
Solución
Este problema es NP-completo, por lo que no se sabe si existe o no una solución en tiempo polinómico. (Las salvedades estándar de posiblemente ser fácil en la práctica, etc. , todas se aplican.) Una posible reducción es de 3SAT.
Supongamos que tenemos un ejemplo 3SAT, tal como (a ∨ b ∨ c) ∧ (¬ A ∨ ¬B ∨ ¬C). Voy a mostrar cómo utilizar "aparatos" para construir una instancia de su problema. Antes de comenzar, reescribir el problema 3SAT como (a1 b1 ∨ ∨ c1) ∧ (¬a2 ∨ ∨ ¬b2 ¬c2) junto con a1 = a2, b1 = b2, c1 y c2 =; es decir, hacer que cada aparición de una única variable, pero a continuación, añadir la condición de que diferentes ocurrencias de la misma variable deben ser iguales.
En primer lugar, nos aseguramos de que usted debe escoger el número 0 en la primera fila, por lo que podemos utilizarlo más tarde como un "centinela" que se debe evitar.
0 0 0
Ahora, construimos un aparato que hace cumplir la regla a1 = a2: (El subrayado _ aquí es un nuevo número único en cada uso de este gadget)
0 _ 0
a1 0 ¬a1
a2 0 ¬a2
Debido a la primera fila, se debe evitar los 0s. Esto significa que o bien toma el camino "a1, a2" o el camino "¬a1, ¬a2"; el primero se corresponden a (ligeramente confusamente) el establecimiento de una a falso, mientras que el segundo corresponderá a una configuración de una a verdadero. Esto se debe a nuestra herramienta de cláusula es muy fácil, entonces, porque simplemente escribimos la cláusula, por ejemplo, (De nuevo _ aquí es una nueva variable cada vez):
0 _ 0
a1 b1 b2
o
0 _ 0
¬a1 ¬b1 ¬b2
Por último, ya que sólo se ha utilizado una de a1 y ¬a1, etc., que le permiten tomar las que no haya utilizado libremente:
0 _ 0
a1 ¬a1 0
Ahora, esto no funciona del todo, porque uno de A1 y ¬a1 podría haber sido utilizado en el gadget elección variables, mientras que el otro podría haber sido utilizado en una cláusula. Así, se incluye una nueva variable para cada @i cláusula que se puede tomar en lugar de una de las variables. Así que si A1 variable aparece en la cláusula 1, tenemos
0 _ 0
a1 ¬a1 @1
Aquí está la salida completa de una traducción de la cláusula original de 3SAT (destacando la trayectoria correspondiente a la configuración a y b en true, c a falso, y recoger una de la primera cláusula), con los números de la izquierda y de brillo en la derecho. Los aparatos están reordenadas (primeros aparatos cláusula, a continuación, para cada variable, el gadget gadget de igualdad y entonces no se utiliza), 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 lo que hay que ser cuadrado, basta con incluir un montón de ceros al final de cada línea.) Es divertido ver que no importa cómo se resuelve esto, en el fondo, que se está resolviendo ese problema 3SAT .
Al final de mi post es un programa escrito apresuradamente-Perl que genera uno de sus problemas desde una entrada de la forma
a b c
-a -b -c
El número de variables en la instancia como resultado de su problema es 11C + V + 1. Dar al programa el interruptor -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++;
}
Otros consejos
Estoy bastante seguro de esto se puede hacer en tiempo polinómico. Me gustaría empezar con un conjunto vacío y luego recorrer las filas de arriba a abajo. Voy a omitir cualquier tipo de código y mostrar lo que el estado se vería en cada paso que debe ser capaz de armar un algoritmo de allí. Estoy seguro de que el mejor de los casos es ligeramente peor que O (n ^ 2) usando una variación de búsqueda en anchura y hacer el seguimiento de las buenas vías de corriente en una tabla.
EDIT: Si esto todavía no es lo suficientemente rápido como se puede mejorar mediante la aplicación de Arlequín optimización .
Por ejemplo:
1 2 3
3 2 1
1 2 1
Estado 0: R = 0 // Fila P = {} // trayectoria del sistema
// {{Path so far}, Column}
P' = {
{{1}, 0}
{{2}, 1}
{{3}, 2}
}
P = P'
Estado 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}
}
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:
Conde 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
Puede probar el colonia de hormigas optimización . Se produce rápidamente muy buenos resultados que están muy cerca de la solución perfecta.
Una solución para la optimización de Kevin Loney podría ser la de combinar caminos parciales que contienen los mismos elementos en la misma columna. Usted tendría que tener en cuenta el número de fusiones con la ruta si desea saber el número de soluciones al final.
Ejemplo: En su ejemplo 5x5, cuando llegue a la tercera fila, la tercera columna tiene tres caminos que conducen a ella que contiene (1 2 5) en algún orden. Usted no tiene que seguir estas separado de este punto, pero puede combinarlos. Si desea conocer el número de soluciones al final, sólo hay que ajustar la estructura de datos de trayectoria, por ejemplo, tres (1 (1 2 5)) sería fusionar a (3 (1 2 5)).
Busque un búsqueda *. Es su amigo.
