Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Порождение перестановок, имеющих ограничения (with constraints)  [new]
exp98
Member

Откуда:
Сообщений: 1609
Тема громкая, но трудная, и я не претендую на полный охват. Начало было положено вопросом DimaT в известном некоторым топике о том, как ускорить цикл
do{ ... }while( next_permuts(....)) .

Тема естественным образом распадается на 3 варианта:
1) не влезая внутрь next_permuts()
2) влезя или используя свою
3) для чего это нужно.

Вопрос оказался интересным,особенно (2-3). Я кратко напишу потом свои думки и что нарыл. Ну и кому есть что сказать по теме топика, тоже пишите, пожалуйста.

Чтоб увернуться от помидоров, прикладываю С++ исходник - как есть, т.е. с разной грязью.
Грязь в виде лишних переменных, закомеченных строк, иногда кривых комментариев, актуальных в VBA.
Т.к. прога берёт начало аж от VBS-скрипта, отлажена в эксэл-вба, и только потом переложена на Си.
Отсутствует Си-шная оптимизация. Есть некоторая алгоритмическая оптимизация.
Это только начало.

Особенности проги.
+
Компилилось в minGW 6.
В её ядре нет места "Classицизму".
Прога формирует перестановки, используя родной next_permuts(....), к-рый порождает их в лексикографической послед-сти.
Те из них, которые удовлетворяют заложенному ограничению, выводятся в stdout.
Ограничение= правильное расположение в задаче о ферзях. Сидит в отдельной процедуре CheckPermuts2().
Запускать ЕХЕ так: main3.exe [14] [<in1] [>true14]
- "14" - единственный используемый параметр в argv[], размерность задачи, по умолчанию переменная DLINA=4
- true14 - stdout
- in1 - stdin
На win64 время для 13 - 340сек, для 14 - 5000 сек, файл текстовый 24,3 Мб
Поскольку для 15 придётся время умножить на 15, а диск на ..., то ....

Небольшой тормоз представляет периодический сброс stdout на диск.
Регулируется макросом FLUSH2DISK= 0xffffff - каждые ХХ перестановок.
При долгой работе на диске файла долго не видно. Чтобы не накручивать показометр хода процесса, заставляю принудительно писать на диск.
Так я могу мониторить время, а в тоталкоммандере и открыть файл он-лайн.

Процедура, описанная в начале
void my_atexit() { /*Paused to look at results ...*/
имеет цель, указанную в комментарии: перед выходом остановиться и посмотреть конечный резалт. По ENTERу заканчивавем.
Если на stdin подать файл "in1" (любой, лучше пустой файл в текущем с ЕХЕ каталоге),то прога закончит без остановки в конце.

И, как отмечал, не удивляйтесь VBAшным "For-Step-Next" и т.д., а загляните в начало, где они описаны как макросы.

Продолжение последует, но не сразу.

К сообщению приложен файл (main3.cpp - 14Kb) cкачать
10 дек 18, 19:47    [21759522]     Ответить | Цитировать Сообщить модератору
 Re: Порождение перестановок, имеющих ограничения (with constraints)  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
exp98,

а зачем отделять ограничения от процесса генерации?
10 дек 18, 20:29    [21759568]     Ответить | Цитировать Сообщить модератору
 Re: Порождение перестановок, имеющих ограничения (with constraints)  [new]
exp98
Member

Откуда:
Сообщений: 1609
Мне кажется, что это может пригодиться в реальных задачах.
В данном случае - для использования конкретного встроенного и "вылизанного" генератора в исследовательских целях.

Забегая вперёд: если нужен не N!, то использовать варианты вроде (А) х (В) х(С),
где В/C/или оба имеют нужные свойства, а ||A|| = N!
11 дек 18, 12:34    [21760114]     Ответить | Цитировать Сообщить модератору
 Re: Порождение перестановок, имеющих ограничения (with constraints)  [new]
exp98
Member

Откуда:
Сообщений: 1609
Возможно я повторяю кого-либо.
Кзалось бы как ускорить перебор, не меняя функцию?
Но если нужна только их часть, обладающая общим свойством, то можно.
Имелось желание свести построение N-перестановок к декартовому поизведению К-перестановок, где К меньше N. Как писал выше, типа (Pn)=(Pn-k) х (Pk) и (Pk) - с нужными свойствами.

Это не означает рекурсивные вызовы.
- готовится (Pk) при n=k с той лишь разницей, что значения не в [1-k], а в [1-n]. И это не перестановки,а размещения (An,k). И они имеют заданное свойство в своей части
- затем каждая из них склеивается с (Pn-k) и проверяется на свойство.

Я просто посмотрел это на проге из начаала темы для к=3 и 4. Небольшая обвёртка, даже заведомо неоптимаизированная дал прибавку. Ускорение понятно, что за счёт сокращения общего кол-ва. Время работы ~ объёму перебора.
Было
13 - 340сек, для 14 - 5000 сек,
Стало
13 - 130сек, для 14 - 2000 сек
Нууу, 15 предположительно за ночь прогонится.

Непонятно, имеет ли смысл дробить мельче, чем k= n/2 ?
В случае свойства = "расстановка фишек" ?
В случае подбора пароля ?
14 дек 18, 18:40    [21764351]     Ответить | Цитировать Сообщить модератору
 Re: Порождение перестановок, имеющих ограничения (with constraints)  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2643
exp98
Мне кажется, что это может пригодиться в реальных задачах.
В данном случае - для использования конкретного встроенного и "вылизанного" генератора в исследовательских целях.

Забегая вперёд: если нужен не N!, то использовать варианты вроде (А) х (В) х(С),
где В/C/или оба имеют нужные свойства, а ||A|| = N!


Почему вас не устраивает классический перебор с возвратом? Или существующие подходы к решению constraint satisfaction problem, где уже в постановке задачи вводят ограничения на каждую переменную
16 дек 18, 17:34    [21765408]     Ответить | Цитировать Сообщить модератору
 Re: Порождение перестановок, имеющих ограничения (with constraints)  [new]
exp98
Member

Откуда:
Сообщений: 1609
Потому что Вы про пункт (2), а я про п.(1) - т.е. не влезая внутрь готовой функции.
И потом, разве плохой метод ускорения? И я не настаиваю, что знаю всё на свете. И просто интерсно сравнить.

Хотел немного оправдаться. Выше я сравнивал варианты (Pn-k)x(An,k) при k=4, к тому же записью в файл.
Сравнил для k=5, без печати:
12/5, w/o print, time= 0.390001 s, Total= 84934080, 218 m/c
13/5, w/o print, time= 5.694010 s, Total= 1253952000, 220 m/c
14/5, w/o print, time= 88.311755 s, Total= 19620195840, 222 m/c

12/0, w/o print, time= 2.308804 s, Total= 479001600, 207.5 m/c
13/0, w/o print, time= 29,858453 s, Total= 6227020800, 208.5 m/c
14/0, w/o print, time= 414.898329 s, Total= 87178291200, 210 m/c

12,13,14 - размерность n
12/5 при k=5
12/0 при k=0,т.е. для (Pn)
Total - длина перебора
m/c - вычисленная производительность млн/сек
16 дек 18, 20:45    [21765513]     Ответить | Цитировать Сообщить модератору
 Re: Порождение перестановок, имеющих ограничения (with constraints)  [new]
Мудроглюков
Member

Откуда:
Сообщений: 8314
exp98
Мне кажется, что это может пригодиться в реальных задачах.
В данном случае - для использования конкретного встроенного и "вылизанного" генератора в исследовательских целях.

Забегая вперёд: если нужен не N!, то использовать варианты вроде (А) х (В) х(С),
где В/C/или оба имеют нужные свойства, а ||A|| = N!


Так использование ограничений в процессе генерации и позволяет сократить перебор (в общем виде это называется "метод ветвей и границ"),
НО в каждой задаче свои ограничения - вот и нужен не столько встроенны генератор,
сколько общий фрейм генератора, чтобы на разных этапах формирования очередного варианта была возможность добавлять ограничения, отсекающие непригодные варианты.
7 мар 19, 20:52    [21827720]     Ответить | Цитировать Сообщить модератору
 Re: Порождение перестановок, имеющих ограничения (with constraints)  [new]
exp98
Member

Откуда:
Сообщений: 1609
Я тоже думалл, что нужен (типа qsort). Почему-то его не видно - это раз. А так получилось проверить идею "квазибэктрекинга".
Второе - вопрос тогда, что будет быстрее работать: бэктрекинг, заточенный под задачу или этот универсальный? или тот, встроенный, или квази. Если "под задачу", то очевидно, что его самому реализовывать.
7 мар 19, 21:07    [21827726]     Ответить | Цитировать Сообщить модератору
 Re: Порождение перестановок, имеющих ограничения (with constraints)  [new]
exp98
Member

Откуда:
Сообщений: 1609
Чесгря успел забыть про тему, увы.
Я почитал про сплетение групп и полугрупп, как раз чтобы получать заданные св-ва либо, или если другими методами, то для реализации быстро вычисляемыми операциями.
Но за 3 подхода не смог полностью уяснить, что я делал - это тоже сплетение или нет. И огорчило, что не нашёл более детальных разработок про это.
7 мар 19, 21:31    [21827736]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить