Enumerando todas as cadeias de reuniões restrições dadas

Question

Eu estou procurando o nome da seguinte classe de problema, para que eu possa google para algoritmos eficazes e mais informações.

Eu tenho um alfabeto com três personagens {-1, 0, 1}.

eu preciso gerar eficazmente todas as cadeias de comprimento 24, que são na maior parte {0} mas têm desde zero a oito {1, -1} caracteres distribuídos em determinados padrões. (Os padrões envolvem restrições sobre o número e emparelhamentos de {-1}). As cordas Número total que atendem os meus critérios são bastante modestos: cerca de 128.000

.

Então, qual é o nome para esta classe de problema / algoritmo?

Answer 1

Eu não estou certo que há uma "classe algoritmo" bem definido para este presente; é apenas um exercício de análise combinatória. Você pode fazer a geração em três etapas:

1. Gerar todos os números de 24 bits com 8 ou menos bits definidos (você pode ser capaz de acelerar o processo um pouco se você precompute algumas tabelas de pesquisa)
2. Para cada número de 24 bits com n bits definida, iterar todos os números de n bits
3. Se o bit de ordem k do número de n bits é 0, então o conjunto de bits de ordem k do número 24-bit impresso como -1, caso contrário, imprime como um

Para explicar as etapas 2-3 um pouco melhor dizer seu número de 24 bits tem 4 bits definido e se parece com

0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

Então, nós iterar sobre todos os 16 números de 4 bits de 0 0 0 0 para 1 1 1 1, e, por exemplo:

0 0 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0
0 1 1 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0 -1 0 0 0 0
0 1 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1 -1 0 0 0 0 0 -1 0 0 0 0
1 1 1 1 gives the string  0 0 0  1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0  1 0 0 0 0

Answer 2

Se você só precisa resolver isso de uma vez, talvez você forçá-lo poderia apenas bruta e colocar os resultados em uma tabela de pesquisa na sua aplicação. Há menos de um trilião de 24 sequências de bit 0,1, -1 para verificar.

Se talvez eu estou fazendo a minha matemática errado ou que você precisa para resolver dinamicamente o problema em tempo de execução, eu consideraria o problema como um sistema de 24 variáveis ??cada limitado a -1, 0, 1 e abordá-lo como um < a href = "http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel = "nofollow noreferrer"> restrição satisfação Problema , supondo que você pode enumerar suas restrições de alguma forma. Minha preocupação, no entanto, é que, desde que você precisa ver todas soluções e não apenas um subconjunto, você ainda pode ser preso exaustivamente buscando o espaço do problema.

Este documento parece o seu direito beco: enumerar todas as soluções para restrição problemas de satisfação . Apesar de eu não ter acesso ao texto completo do papel para ver se isso ajuda.

I podem ser latindo para a árvore errada todos juntos, mas talvez este é um ponto de partida

Answer 3

Uma resposta completamente separado do meu passado, como código de trabalho tende a ligações trunfo para trabalhos de pesquisa, eu encontrei este código em Física Forum e não pode levar o crédito por isso, eu apenas fixa-lo para que ele compilado sob g ++ e mudou a constantes para olhar para 8 bits em 24. ele enumera muito rapidamente todos os 24 mordeu cordas com 8 bits, e existem apenas cerca de 735.000 deles. Esses 'modelos' mostrar os padrões válidos para seus personagens diferentes de zero. Você teria então tem que tomar cada uma dessas 735.000 respostas e jogar em torno dos -. Sinais / + e decidir se cada um se encontra com você critérios, mas desta forma você está começando do 735k soluções possíveis em vez de 200 bilhões

#include <stdio.h>

 int main()
 {
 int size = 24;
 int pop = 8;

 int n = ((1 << pop) - 1) << (size - pop);

 while(true) {
    printf( "%x\n",n);

    int lowest = n & -n;

     if(lowest > 1) {
        n = n ^ lowest ^ (lowest >> 1);
        continue;
     }

     int high = n & (n + lowest);
     if(high == 0) break;

     int low = n ^ high;

     low = (low << 2) + 3;

     while((low & high) == 0) low <<= 1;
     n = high ^ low;
  }
 }