solução não-exponencial para labirinto problema?
https://stackoverflow.com/questions/535859
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Dado um * n-sized gráfico acíclico onde cada nó tem no máximo três filhos e três pais, existe um algoritmo não-exponencial para identificar se um caminho n-length existe onde há dois nós compartilham o mesmo valor dirigiu-multi , e cada valor de um conjunto é contabilizado?
Basicamente, eu tenho um n * n labirinto onde cada espaço tem um valor aleatório (1..n). Eu preciso encontrar um caminho (do topo para a base) de n nós que inclui todos os valores.
Agora eu estou usando uma busca em profundidade, mas isso é T(n) = 3T(n-1) + O(1), que é O(3^n), uma solução não-ideal.
De qualquer confirmando meus medos, ou me apontar na direção certa seria muito apreciada.
Edit:. Para fazer isso um pouco mais concreto, aqui é um labirinto com soluções (resolvido usando a solução em profundidade)
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`
Solução
Este problema é NP-completo, e por isso não se sabe se há ou não uma solução em tempo polinomial. (As ressalvas padrão de possivelmente ser fácil, na prática, etc. , todos se aplicam.) Uma possível redução é de 3SAT.
Suponha que temos uma instância de 3SAT, tais como (a ? b ? c) ? (¬ ? ¬b ? ¬c). Vou mostrar como usar "gadgets" para construir uma instância do seu problema. Antes de começar, reescrever o problema 3SAT como (a1 b1 ? ? c1) ? (¬a2 ? ¬b2 ? ¬c2) em conjunto com A1 = A2, B1 = B2, C1 e C2 =; isto é, fazer com que cada ocorrência de uma única variável, mas, em seguida, adicionar a condição de que diferentes ocorrências da mesma variável devem ser iguais.
Em primeiro lugar, certifique-se que você deve escolher o número 0 na primeira fila, para que possamos usá-lo posteriormente como uma "sentinela" que você deve evitar.
0 0 0
Agora, vamos construir um gadget que reforça a a1 = regra a2: (A _ sublinhado aqui é um novo número único em cada uso deste gadget)
0 _ 0
a1 0 ¬a1
a2 0 ¬a2
Por causa da primeira linha, você deve evitar os 0s. Isso significa que você quer tomar o caminho "a1, a2" ou o caminho "¬a1, ¬a2"; o ex correspondem à vontade (ligeiramente confusa) definindo um a falsa, enquanto que o último correspondem vontade para uma configuração para uma verdadeira. Isto é porque a nossa engenhoca cláusula é realmente fácil, então, porque nós simplesmente escrever a cláusula, por exemplo, (Novamente _ aqui é uma nova variável de cada vez):
0 _ 0
a1 b1 b2
ou
0 _ 0
¬a1 ¬b1 ¬b2
Finalmente, uma vez que você usou apenas um dos a1 e ¬a1, etc., nós deixá-lo aproveitar as que você não tenha usado livremente:
0 _ 0
a1 ¬a1 0
Agora, isso não funciona muito bem, porque um de a1 e ¬a1 poderia ter sido usado no gadget escolha variável, enquanto o outro poderia ter sido usado em uma cláusula. Assim, incluímos uma nova @i variável para cada cláusula que você pode levar em vez de uma das variáveis. Então, se a1 variável aparece na cláusula 1, temos
0 _ 0
a1 ¬a1 @1
Aqui está a saída completa de uma tradução da cláusula originais 3SAT (com destaque para o caminho correspondente à fixação de um e b para true, c como falsa, e escolher um a partir da primeira cláusula), com números na esquerda e brilho na certo. Os aparelhos são re-ordenada (primeiros aparelhos cláusula, em seguida, para cada variável, o gadget igualdade e dispositivo então não utilizado), mas isso não importa, uma vez que está de qualquer maneira independente.
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 você quiser a coisa toda para ser quadrado, basta incluir um monte de zeros no final de cada linha.) É divertido ver que não importa como você resolver isso, no fundo, você está resolvendo o problema 3SAT .
No final do meu post é um programa Perl apressadamente escrito que gera um de seus problemas de uma entrada da forma
a b c
-a -b -c
O número de variáveis ??na instância resultante do seu problema é 11C + V + 1. Dar ao programa o interruptor -r para produzir brilho em vez 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++;
}
Outras dicas
Eu tenho certeza que isso pode ser feito em tempo polinomial. Eu ia começar com um um conjunto vazio e laço, em seguida, através da parte superior linhas para baixo. Eu vou pular qualquer tipo de código e mostrar o que o estado seria semelhante em cada passo que você deve ser capaz de montar um algoritmo de lá. Tenho certeza de que o melhor caso é ligeiramente pior do que O (n ^ 2) usando uma variação de busca em largura e manter o controle dos caminhos atuais bons em uma tabela.
EDIT: Se isso ainda não é rápido o suficiente, você pode melhorá-lo através da aplicação de o Harlequin otimização .
Por exemplo:
1 2 3
3 2 1 |
1 2 1
State 0: R = 0 // Row P = {} // Path Set
// {{Path so far}, Column}
P' = {
{{1}, 0}
{{2}, 1}
{{3}, 2}
}
P = P'
State 1: R = 1 // FILEIRA 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 caminho: 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
Você pode tentar o ant colony optimization . Ela produz rapidamente resultados muito bons que estão muito perto da solução perfeita.
Uma otimização para o Kevin Loney solução poderia ser a de mesclar caminhos parciais que contêm os mesmos elementos na mesma coluna. Você teria que anote o número de fusões com o caminho se você quer saber o número de soluções no final.
Exemplo: No seu exemplo 5x5, quando chegam à terceira linha, a terceira coluna tem três caminhos que conduzem a ela que contém (1 2 5) em alguma ordem. Você não tem que seguir estes separadamente a partir deste ponto, mas pode juntá-las. Se você quer saber o número de soluções no final, você apenas tem que ajustar a sua estrutura de dados caminho, por exemplo, três (1 (1 2 5)) iriam fundir-se com (3 (2 1 5)).
Olhe para cima A * pesquisa. Ele é seu amigo.
