Solution non exponentielle labyrinthe problème?
https://stackoverflow.com/questions/535859
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Étant donné un * n dimensions graphe acyclique à plusieurs têtes où chaque noeud a au plus trois enfants et trois parents, est-il un algorithme non-exponentielle pour déterminer si un chemin de longueur n existe où aucun deux noeuds partagent la même valeur et chaque valeur d'un ensemble est comptabilisé?
Fondamentalement, j'ai un labyrinthe n * n où chaque espace a une valeur aléatoire (1..n). Je dois trouver un chemin (du haut vers le bas) des n noeuds qui comprend toutes les valeurs.
En ce moment je suis en utilisant une recherche en profondeur d'abord, mais c'est T(n) = 3T(n-1) + O(1), qui est O(3^n), une solution non-idéale.
Soit confirmer mes craintes, ou me pointant dans la bonne direction serait très apprécié.
Edit:. Pour en faire un peu plus concret, voici un labyrinthe avec des solutions (résolu en utilisant la solution de profondeur d'abord)
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`
La solution
Ce problème est NP-complet, et donc on ne sait pas si oui ou non il y a une solution en temps polynomiale. (Les standards d'être réserves peut-être facile dans la pratique, etc. , tous appliquent.) Une réduction possible est de 3SAT.
Supposons que nous ayons une instance 3SAT, comme (a ∨ b ∨ c) ∧ (¬a ∨ ∨ ¬b ¬c). Je vais montrer comment utiliser « gadgets » pour construire une instance de votre problème. Avant de commencer, réécrire le problème 3SAT comme (a1 ∨ ∨ b1 c1) ∧ (¬a2 ∨ ∨ ¬b2 ¬c2) avec a1 = a2, b1 = b2 et c1 = c2; à savoir, faire de chaque occurrence d'une variable unique, mais ajoutez la condition que les différentes occurrences de la même variable doivent être égales.
Tout d'abord, nous nous assurons que vous devez choisir le numéro 0 dans la première rangée, afin que nous puissions l'utiliser plus tard comme une « sentinelle » que vous devez éviter.
0 0 0
Maintenant, nous construisons un gadget qui applique la règle a1 = a2: (Le _ underscore est ici un nouveau numéro unique dans chaque utilisation de ce gadget)
0 _ 0
a1 0 ¬a1
a2 0 ¬a2
En raison de la première ligne, vous devez éviter les 0s. Cela signifie que vous prenez soit le chemin « a1, a2 » ou le chemin « ¬a1, ¬a2 »; l'ancien correspondra à la mise en (un peu prêter à confusion) a à faux, alors que celui-ci correspondra à un réglage un true. En effet, notre gadget clause est vraiment facile alors, parce que nous écrivons simplement en bas de la clause, par exemple (Encore une fois _ ici est une nouvelle variable à chaque fois):
0 _ 0
a1 b1 b2
ou
0 _ 0
¬a1 ¬b1 ¬b2
Enfin, puisque vous avez seulement utilisé l'un des a1 et ¬a1, etc., nous vous laissons prendre ceux que vous n'avez pas utilisé librement:
0 _ 0
a1 ¬a1 0
Maintenant, cela ne fonctionne pas tout à fait, parce que l'un des a1 et ¬a1 aurait pu être utilisé dans le gadget de choix variables, tandis que l'autre aurait pu être utilisé dans une clause. Nous incluons donc un nouveau @i variable pour chaque article que vous pouvez prendre au lieu de l'une des variables. Donc, si la variable a1 apparaît à l'article 1, nous avons
0 _ 0
a1 ¬a1 @1
Voici la sortie complète d'une traduction de la clause 3SAT originale (mettant en évidence le chemin correspondant à la mise en a et b true, c à faux, et de choisir un de la première clause), avec des chiffres sur la gauche et brillant sur la droite. Les gadgets sont réorganisés (premiers gadgets clause, puis pour chaque variable, le gadget d'égalité et gadget utilisé), mais cela n'a pas d'importance, car ils sont de toute façon indépendante.
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 vous voulez que le tout soit carré, il suffit d'inclure un tas de zéros à la fin de chaque ligne.) Il est amusant de voir que peu importe comment vous résoudre ce problème, au cœur, vous résoudre ce problème 3SAT .
A la fin de mon post est un programme Perl hâtivement écrit qui génère un de vos problèmes à partir d'une entrée de la forme
a b c
-a -b -c
Le nombre de variables dans l'instance résultant de votre problème est 11C + V + 1. Donnez le programme le commutateur -r pour produire brillant au lieu de chiffres.
# 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++;
}
Autres conseils
Je suis assez sûr que cela peut être fait en temps polynomial. Je commencer avec un un ensemble vide, puis une boucle sur les rangées de haut en bas. Je vais passer tout type de code et vous montrer ce que l'état ressemblerait à chaque étape, vous devriez être en mesure de mettre en place un algorithme à partir de là. Je suis sûr que le meilleur des cas est légèrement pire que O (n ^ 2) en utilisant une variation de la largeur d'abord rechercher et garder la trace des bons chemins actuels dans un tableau.
EDIT: Si ce n'est pas encore assez rapide, vous pouvez l'améliorer en appliquant l'optimisation de Harlequin .
Par exemple:
1 2 3
3 2 1
1 2 1
0 Etat: R = 0 // Row P = {} // Set Path
// {{Path so far}, Column}
P' = {
{{1}, 0}
{{2}, 1}
{{3}, 2}
}
P = P'
État 1: R = 1 // ROW P = { {{dix} {{2}, 1} {{3}, 2} }
P' = {
{{1 3}, 0}
{{1 2}, 1}
{{2 3}, 0}
{{2 1}, 2}
{{3 2}, 1}
{{3 1}, 2}
}
État 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}
}
Résultat:
Chemin Nombre: 5
S1 1 2 3 F2
S2 2 3 1 F1
S3 3 2 1 F1
S3 3 2 1 F3
S3 3 1 2 F2
Vous pouvez ant d'optimisation des colonies. Il donne rapidement des résultats très bons qui sont très proches de la solution parfaite.
Une optimisation pour la solution Kevin Loney pourrait être à fusionner des chemins partiels qui contiennent les mêmes éléments dans la même colonne. Vous devrez noter le nombre de se confond avec le chemin si vous voulez connaître le nombre de solutions à la fin.
Exemple: Dans votre exemple 5x5, lorsque vous arrivez à la troisième ligne, la troisième colonne a trois chemins qui y mènent contenant (1 2 5) dans un certain ordre. Vous ne devez pas suivre ces derniers séparément de ce point, mais pouvez les fusionner. Si vous voulez connaître le nombre de solutions à la fin, il vous suffit d'ajuster votre structure de données de chemin, par exemple trois (1 (2 1 5)) serait à fusionner (3 (1 2 5)).
Rechercher un recherche *. Il est votre ami.
