Comments 16
Алгоритм несколько неоптимален. И совсем, вопиюще прямо-таки неоптимально его использование на каждом шаге перебора.
Как бы вы его улучшили?
Если сам алгоритм, то нам достаточно первой несимметричной пары цифр, чтобы понять, больше или меньше это число, чем оно же обращённое. Соответственно, во всех случаях, кроме палиндромов, нам не нужно вычислять все цифры, достаточно начать с пары «первая-последняя» и двигаться к центру, пока не найдём расхождение. Не могу сейчас сходу сказать точно, но по идее это должно улучшить среднее время работы алгоритма до логарифмического.
Если полный перебор, то логичнее сделать так: перебрать все возможные левые половины числа. Для каждой левой половины сначала взять правую половину, равную левой отражённой, затем увеличивать её (или уменьшать, всё равно). Такой способ гарантирует, что среди чисел, склеенных из этих двух половин, никогда не встретится пара различных симметричных.
Если полный перебор, то логичнее сделать так: перебрать все возможные левые половины числа. Для каждой левой половины сначала взять правую половину, равную левой отражённой, затем увеличивать её (или уменьшать, всё равно). Такой способ гарантирует, что среди чисел, склеенных из этих двух половин, никогда не встретится пара различных симметричных.
Спасибо. Я думал о таком сравнении векторов, но это было бы в ущерб наглядности.
А по поводу второй части комментария: не хотелось выдумывать новый алгоритм генерации входящей сетки при наличии приемлемого варианта с доработкой напильником. К тому же каждая конфигурация сетки обсчитывается для конечной задачи гараздо дольше, потому не видел смысла экономить на мелочах.
А по поводу второй части комментария: не хотелось выдумывать новый алгоритм генерации входящей сетки при наличии приемлемого варианта с доработкой напильником. К тому же каждая конфигурация сетки обсчитывается для конечной задачи гараздо дольше, потому не видел смысла экономить на мелочах.
Я бы не стал передавать конфигурацию в виде номера, все равно при обработке понадобится переводить в 14-ричную СС. Передаем вектор длины 18 и экономим на преобразовании.
Скорее всего менять вектор будет быстрее, чем строить его заново каждый раз.
Скорее всего менять вектор будет быстрее, чем строить его заново каждый раз.
Если не стоит задача писать универсальный алгоритм, и есть начальные условия — поле 6х3, 14 возможных компонент, то почему бы в алгоритме перебора вариантов просто не сделать 18 списков, из которых вычёркиваются лишние варианты по мере подбора?
Может, немного непонятно высказываюсь.
Представим, что мы перебрали все комбинации, где первая компонента стоит в первой ячейке, а содержимое остальных ячеек менялось.
Теперь представим, что мы получили симметрию всех этих комбинаций — тогда наша первая компонента всегда будет занимать один из углов сетки.
И вот если представить сетку как ряд, а порядковые номера компонентов как цифры, то любая наша комбинация — это число.
Тогда алгоритм перебора сводится к простому перебору всех чисел подряд, составленных из наших цифр. Точнее, это уже будет не перебор, а проверка каждого числа на то, что до него нет симметричных ему чисел. И реализуется примерно так:
1. Формируем число банальным перебором — то есть в первый разряд пишем первую цифру, во второй — снова первую и так далее.
2. На каждом этапе такого подбора делаем проверку — какая цифра находится в симметричном разряде? Тут требуется пояснение. Симметричные разряды — это разряды, которые на сетке симметричны друг другу. например, 1, 3, 16 и 18. И между ними есть старшинство. Поскольку наш перебор идёт по возрастанию, то дополнительно учитывается старшинство разряда в его группе симметрии. Для 3 разряда проверяется цифра только в 1 разряде.
3. Если цифра в симметричном разряде меньше или равна — всё нормально, идём дальше. Если же цифра больше, то значит мы наткнулись на симметричную комбинацию и нам нет смысла продолжать подбор и надо откатываться к предыдущему шагу — инкрементируем цифру предыдущего разряда, делаем проверку, переходим к подбору следующего разряда нашего числа.
Теперь на конкретном примере:
1. Мы перебрали все варианты, начинающиеся с 1.
2. Дошли до варианта 211…
3. Перебор на этом шаге останавливается — мы нашли целый пласт комбинаций, который симметричен комбинациям 112…
А их мы уже все перебрали. Тогда откатываемся назад и проверяем 212. И вот тут у нас уже равенство в симметричных разрядах — комбинация начинается как симметричная сама себе, что допустимо и подбор идёт дальше.
Хорошо, что сетка прямоугольная — в квадратной сетке помимо зеркального отражения появляется поворот на 90 градусов.
Может, немного непонятно высказываюсь.
Представим, что мы перебрали все комбинации, где первая компонента стоит в первой ячейке, а содержимое остальных ячеек менялось.
Теперь представим, что мы получили симметрию всех этих комбинаций — тогда наша первая компонента всегда будет занимать один из углов сетки.
И вот если представить сетку как ряд, а порядковые номера компонентов как цифры, то любая наша комбинация — это число.
Тогда алгоритм перебора сводится к простому перебору всех чисел подряд, составленных из наших цифр. Точнее, это уже будет не перебор, а проверка каждого числа на то, что до него нет симметричных ему чисел. И реализуется примерно так:
1. Формируем число банальным перебором — то есть в первый разряд пишем первую цифру, во второй — снова первую и так далее.
2. На каждом этапе такого подбора делаем проверку — какая цифра находится в симметричном разряде? Тут требуется пояснение. Симметричные разряды — это разряды, которые на сетке симметричны друг другу. например, 1, 3, 16 и 18. И между ними есть старшинство. Поскольку наш перебор идёт по возрастанию, то дополнительно учитывается старшинство разряда в его группе симметрии. Для 3 разряда проверяется цифра только в 1 разряде.
3. Если цифра в симметричном разряде меньше или равна — всё нормально, идём дальше. Если же цифра больше, то значит мы наткнулись на симметричную комбинацию и нам нет смысла продолжать подбор и надо откатываться к предыдущему шагу — инкрементируем цифру предыдущего разряда, делаем проверку, переходим к подбору следующего разряда нашего числа.
Теперь на конкретном примере:
1. Мы перебрали все варианты, начинающиеся с 1.
2. Дошли до варианта 211…
3. Перебор на этом шаге останавливается — мы нашли целый пласт комбинаций, который симметричен комбинациям 112…
А их мы уже все перебрали. Тогда откатываемся назад и проверяем 212. И вот тут у нас уже равенство в симметричных разрядах — комбинация начинается как симметричная сама себе, что допустимо и подбор идёт дальше.
Хорошо, что сетка прямоугольная — в квадратной сетке помимо зеркального отражения появляется поворот на 90 градусов.
Касательно 18 списков: Ваш вариант — это неплохое начало не только для центральной, но и для осевых симметрий прямоугольной сетки.
>>… помимо зеркального отражения…
Позволю себе поправить: зеркальное отражение — это осевая симметрия.
>>… помимо зеркального отражения…
Позволю себе поправить: зеркальное отражение — это осевая симметрия.
Да, я не особо силён в терминах, из-за чего мне сложно было объяснить свою мысль.
Суть сводится к тому, чтобы на основе имеющихся константных входных параметрах построить такие критерии отбора, которые отсеивают огромное число комбинаций, на которых экономится время, и при этом сама проверка условий не занимает много ресурсов.
Я в саму игру не играл, но там нет заведомо известных сочетаний компонент, которые дают проигрыш, а не выигрыш? Тогда можно в подборе использовать не перебор среди всех и как раз и использовать «списки».
Суть сводится к тому, чтобы на основе имеющихся константных входных параметрах построить такие критерии отбора, которые отсеивают огромное число комбинаций, на которых экономится время, и при этом сама проверка условий не занимает много ресурсов.
Я в саму игру не играл, но там нет заведомо известных сочетаний компонент, которые дают проигрыш, а не выигрыш? Тогда можно в подборе использовать не перебор среди всех и как раз и использовать «списки».
>> Количество вариантов заполнения такой сетки с повторами равно 14^18
а не 18^14?
а не 18^14?
А если сразу генерировать цифровые последовательности так, чтобы левая ячейка была гарантированно «меньше» правой?
Что в результате получилось? Industrial craft ведь, насколько могу понять по картинкам? Какая там оптимальная конфигурация реактора?
Расчеты еще не закончены, но некоторые результаты есть
Best efficiency: 3.000000
__________________
____TR____________
____U1____________
____TR____________
____CV____________
____OV____________
Total EU output: 15.00 EU/t average.
Efficiency: 3.00 average.
Best EU output: 25
____U1____________
____AV____________
__________________
____U2____________
____CV____________
____OV____________
Total EU output: 25.00 EU/t average.
Efficiency: 1.67 average.
Легенда:
U1, U2 — Fuel Rod, Dual Fuel Rod
TR — Thick Neutron Reflector
AV — Advanced Heat Vent
CV — Component Heat Vent
OV — Overclocked Heat Vent
__________________
____TR____________
____U1____________
____TR____________
____CV____________
____OV____________
Total EU output: 15.00 EU/t average.
Efficiency: 3.00 average.
Best EU output: 25
____U1____________
____AV____________
__________________
____U2____________
____CV____________
____OV____________
Total EU output: 25.00 EU/t average.
Efficiency: 1.67 average.
Легенда:
U1, U2 — Fuel Rod, Dual Fuel Rod
TR — Thick Neutron Reflector
AV — Advanced Heat Vent
CV — Component Heat Vent
OV — Overclocked Heat Vent
Это за 10-14 ночей работы. Может и попадались после них лучшие варианты, но я намеренно вставил нижнюю планку эффективности 3.00 и выхода 60 EU/t, потому что такая конфигурация известна. Она на КПДВ, кстати.
Последняя расчитанная конфигурация № 1720407652. Ее результат: остановлена из-за большой генерации тепла (548 HU/s)
Спасибо за статью :) у меня схожая задачка. Я нарёк её «компостер»: в дополнении к вашей симметрии отсекаю также и «клонов», образующихся в результате всех поворотов и отражений (у меня сетка квадратная) — всего 11. Это как, сколько уникальных рисунков можно прокомпосировать на квадратном талоне, у которого не обозначены даже лицевая/тыльная сторона.
Приятно было прочесть, что кто-то ещё применяет тот же метод «больше-меньше».
Приятно было прочесть, что кто-то ещё применяет тот же метод «больше-меньше».
Sign up to leave a comment.
Центральная симметрия сетки