Перечисление всех строк, соответствующих заданным ограничениям - PullRequest
Новая
       29

Перечисление всех строк, соответствующих заданным ограничениям

2 голосов
/ 23 июня 2009

Я ищу название следующего класса проблем, чтобы я мог найти в Google эффективные алгоритмы и получить дополнительную информацию.

У меня есть алфавит с тремя символами {-1, 0, 1}.

Мне нужно эффективно сгенерировать все строки длиной 24, которые в основном {0}, но содержат от нуля до восьми {1, -1} символов, распределенных в определенных шаблонах. (Шаблоны включают ограничения на количество и пары {-1}). Общее количество строк, соответствующих моим критериям, довольно скромное: около 128 000

.

Так как называется этот класс задач / алгоритмов?

Ответы [ 3 ]

3 голосов
/ 23 июня 2009

Я не уверен, что для этого есть четко определенный «класс алгоритма»; это просто упражнение в комбинаторике. Вы можете сделать генерацию в три этапа:

  1. Генерация всех 24-битных чисел с установленным 8 или менее битами (вы можете ускорить это, если предварительно вычислите некоторые таблицы поиска)
  2. Для каждого 24-битного числа с установленным n битами, повторять все n-битные числа
  3. Если k-й бит n-битного числа равен 0, то k-й установленный бит 24-битного числа печатается как -1, в противном случае он печатается как 1

Чтобы объяснить шаги 2-3 немного лучше, скажем, что у вашего 24-битного числа установлено 4 бита, и оно выглядит как 

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

Затем мы перебираем все 16 4-битных чисел от 0 0 0 0 до 1 1 1 1 и, например: 

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
1 голос
/ 23 июня 2009

Полностью отдельный ответ от моего последнего, так как рабочий код имеет тенденцию превосходить ссылки на исследовательские работы, я нашел этот код на Physics Forum и не могу взять кредит на себя, я просто исправил его он скомпилирован в g ++ и изменен на константы для поиска 8 бит в 24. Он очень быстро перечисляет все 24-битные строки с 8 битами, и их всего около 735 000. Эти «шаблоны» показывают единственные допустимые шаблоны для ваших ненулевых символов. Затем вам нужно будет взять каждый из этих 735 000 ответов и обойти знаки - / + и решить, соответствует ли каждый из них вашим критериям, но таким образом вы начинаете с 735 тысяч возможных решений вместо 200 миллиардов. 

#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;
  }
 }
1 голос
/ 23 июня 2009

Если вам нужно решить эту проблему только один раз, возможно, вы можете просто перебрать его и поместить результаты в таблицу поиска в вашем приложении. Для проверки требуется менее триллиона 24-битных последовательностей 0,1, -1.

Если, возможно, я неправильно делаю математику или вам нужно динамически решать проблему во время выполнения, я бы рассмотрел проблему как систему из 24 переменных, каждая из которых ограничена -1, 0, 1, и обозначил бы ее как 1003 * Проблема удовлетворения ограничений , при условии, что вы можете каким-то образом перечислить свои ограничения. Однако меня беспокоит то, что, поскольку вам требуется видеть все решения, а не только подмножество, вы все равно можете застрять в поисках проблемного пространства.

Этот документ кажется вам правильным: Перечисление всех решений проблем удовлетворения ограничений . Хотя у меня нет доступа к полному тексту статьи, чтобы посмотреть, поможет ли это.

Возможно, я все вместе лаю не на том дереве, но, возможно, это отправная точка

...