Исследуя одну задачу оптимизации, столкнулся с проблемой симметричности конфигураций при прямом переборе вариантов. Схожая проблема возникает в некоторых решениях задачи о восьми ферзях. Исследуя центральную симметрию прямоугольной сетки, я обнаружил Немного о симметрии
Центральная симметрия или симметрия с центром в точке — это преобразование пространства, переводящее точку X в точку X’ так, что центр симметрии будет центром отрезка XX’. Фигура называется симметричной относительно точки A, если для каждой точки фигуры симметричная ей точка относительно точки A также принадлежит этой фигуре.
Если же мы говорим о центральной симметрии сетки, состоящей из клеток, то тут речь будет идти не о точках, а о клетках сетки. Например, после центрально-симметричного преобразования шахматной доски клетка A1 станет на место H8, A2 — на H7, а B1 — на G8.
В этой статье мы будем использовать прямоугольную сетку. Как и прямоугольник, такая сетка имеет две оси симметрии и один центр, но сконцентрируемся только на центральной симметрии.
Суть вопроса
Имеется сетка размером 3 на 6 клеток. Также в наличии список из 14 компонент, любой из которых может быть поставлен в любую клетку, причем возможны повторы. Количество вариантов заполнения такой сетки с повторами равно 1418, естественно было бы неплохо их уменьшить в два раза, отбросив варианты заполнения, которые являются центрально-симметричными к уже проверенным. Для простоты вывода пусть компонентами будут числами от 0 до 13 включительно. Список из 18 компонент генерируется функцией product из пакета itertools (если быть точным, то функция возвращает кортеж-итератор, который, подобно одометру, на каждой итерации меняет правостоящий элемент). Этим списком по столбикам и заполняется сетка.
Задача: Исключить варианты заполнения сетки, центрально-симметричные уже проверенным вариантам.
Реализация
Пронумеруем клетки по столбикам, начиная с левого верхнего угла, от 0 до 17. Попытаемся для каждой конфигурации найти номер симметричной ей относительно центра. Нумерация конфигураций, как обычно, с нуля.
Конфигурация 0 (все ячейки с нулями) очевидно симметрична сама себе: 0 -> 0.
Конфигурация 1. Клетка 17 получает 1, остальные с нулями. Симметричной к ней будет конфигурация, в которой в клетке 0 стоит «1», остальные с нулями. Клетка 17 пройдет 14 своих значений (от 0 до 13) за первые 14 итераций. Клетка 16 тоже за 14, но на каждую ее конфигурацию приходится 14 итераций клетки 17, т.е. за 142, и т.д. Следовательно, клетка 0 наберет 1 на 1417 итерации.
Конфигурация 2. Клетка №17 получает 2, остальные с нулями. Симметричной к ней будет конфигурация 2?1417, в которой в клетке 0 стоит 2, остальные нули.
Конфигурация 3 -> Конфигурация 3?1417
Конфигурация 4 -> Конфигурация 4?1417 и т.д. до 13 -> 13?1417.
Следуя этой логике, стоит записать номер варианта, симметричного первому, как 1?1417, а симметричного нулевому — как 0?1417.
Уже имеем некоторый список номеров конфигураций, симметричных друг другу:
- 0 и 0?1417
- 1 и 1?1417
- 2 и 2?1417
и т.д. до 13.
Конфигурация 14. 1 находится в предпоследней клетке, остальные нули. Симметричной к ней является 1?1416.
Конфигурация 15. Единицы в двух последних клетка, остальные нули. Симметричная к ней, когда 1 в первых двух ячейках, остальные нули. 1 становится в ячейку №0 на итерации 1417, а еще через 1416 1 появится и в клетке №1, следовательно искомая конфигурация будет под номером 1416 + 1417.
Конфигурация 16. Элемент «А» в ячейке №16, «B» — в ячейке №17. Симметричная к ней, очевидно 1416 + 2?1417.
…
Конфигурация 27 -> 1?1416 + 13?1417.
Конфигурация 28 -> 2?1416.
Конфигурация 29 -> 2?1416 + 1417.
Эта история продолжается до итерации 195, которая симметрична 13?1416 + 13?1417. В итерации 196 в ячейку №15 ставится 1, остальные пусты. Симметрична к ней итерация 1415.
В итерации 197 единица ставится еще и в ячейку №17, потому симметрична к ней — 1415 + 1417, и т.д.
Общий закон симметрии конфигураций сетки будет таким:
Тут мне показалась знакомой формула слева. Это формула перевода числа из системы счисления с произвольным основанием в десятичную. И, соответственно
Нетрудно заметить, что в правой части записано число из левой части в обратном порядке — если в левой части мы «пишем» число справа налево, то в левой — теми же цифрами, но слева направо. Проще говоря, число справа — это «перевертыш» числа слева, причем оба записаны в системе счисления с основанием 14 и имеют длину 18.
Критерий и алгоритм валидации
Если номер конфигурации длинной в количество клеток и записанный в системе счисления с основанием, равным количеству элементов, меньше собственного номера-«перевертыша», то конфигурация симметричная данной еще не встречалась. Если же они (номера) равны, то имеем дело с палиндромом, который встречается только один раз и, следовательно, подлежит проверке.
Сам алгоритм валидации такой:
- Перевести номер конфигурации в систему счисления с основанием, равным количеству элементов
- Записать число-«перевертыш» длиной 18
- Если «перевертыш» больше номера конфигурации, то симуляции этой конфигурации и симметричной к ней еще не проводились; если нет, то проводилась симуляция конфигурации, симметричной этой, следовательно — пропустить.
def validate(number, radix, length):
fingers = '0123456789abcdefghijklmnopqrstuvwxyz'
n = number
# перевод в систему счисления с основанием radix без разворота
turn = ''
while n > 0:
turn += fingers[n % radix]
n = n // radix
# добавим недостающие нули до нужной длинны
turn += '0' * (length - len(turn))
return number <= int(turn, radix)
Заключение
Очевидно, этот алгоритм применим не только для определения центральной симметрии двумерной сетки, но и сетки в произвольном измерении, потому что любую такую конфигурацию возможно свести к списку, или списком заполнить сетку, например, построчно.
Сам алгоритм довольно тяжелый, что вызывает вопрос о применимости его на практике. Но в случае, когда проверка каждой конфигурации стоит еще больше вычислительных ресурсов, то, возможно, стоит его использовать.
Комментарии (16)
LoadRunner
28.06.2016 14:44Если не стоит задача писать универсальный алгоритм, и есть начальные условия — поле 6х3, 14 возможных компонент, то почему бы в алгоритме перебора вариантов просто не сделать 18 списков, из которых вычёркиваются лишние варианты по мере подбора?
Может, немного непонятно высказываюсь.
Представим, что мы перебрали все комбинации, где первая компонента стоит в первой ячейке, а содержимое остальных ячеек менялось.
Теперь представим, что мы получили симметрию всех этих комбинаций — тогда наша первая компонента всегда будет занимать один из углов сетки.
И вот если представить сетку как ряд, а порядковые номера компонентов как цифры, то любая наша комбинация — это число.
Тогда алгоритм перебора сводится к простому перебору всех чисел подряд, составленных из наших цифр. Точнее, это уже будет не перебор, а проверка каждого числа на то, что до него нет симметричных ему чисел. И реализуется примерно так:
1. Формируем число банальным перебором — то есть в первый разряд пишем первую цифру, во второй — снова первую и так далее.
2. На каждом этапе такого подбора делаем проверку — какая цифра находится в симметричном разряде? Тут требуется пояснение. Симметричные разряды — это разряды, которые на сетке симметричны друг другу. например, 1, 3, 16 и 18. И между ними есть старшинство. Поскольку наш перебор идёт по возрастанию, то дополнительно учитывается старшинство разряда в его группе симметрии. Для 3 разряда проверяется цифра только в 1 разряде.
3. Если цифра в симметричном разряде меньше или равна — всё нормально, идём дальше. Если же цифра больше, то значит мы наткнулись на симметричную комбинацию и нам нет смысла продолжать подбор и надо откатываться к предыдущему шагу — инкрементируем цифру предыдущего разряда, делаем проверку, переходим к подбору следующего разряда нашего числа.
Теперь на конкретном примере:
1. Мы перебрали все варианты, начинающиеся с 1.
2. Дошли до варианта 211…
3. Перебор на этом шаге останавливается — мы нашли целый пласт комбинаций, который симметричен комбинациям 112…
А их мы уже все перебрали. Тогда откатываемся назад и проверяем 212. И вот тут у нас уже равенство в симметричных разрядах — комбинация начинается как симметричная сама себе, что допустимо и подбор идёт дальше.
Хорошо, что сетка прямоугольная — в квадратной сетке помимо зеркального отражения появляется поворот на 90 градусов.
fowler
29.06.2016 20:03Касательно 18 списков: Ваш вариант — это неплохое начало не только для центральной, но и для осевых симметрий прямоугольной сетки.
>>… помимо зеркального отражения…
Позволю себе поправить: зеркальное отражение — это осевая симметрия.LoadRunner
29.06.2016 21:42Да, я не особо силён в терминах, из-за чего мне сложно было объяснить свою мысль.
Суть сводится к тому, чтобы на основе имеющихся константных входных параметрах построить такие критерии отбора, которые отсеивают огромное число комбинаций, на которых экономится время, и при этом сама проверка условий не занимает много ресурсов.
Я в саму игру не играл, но там нет заведомо известных сочетаний компонент, которые дают проигрыш, а не выигрыш? Тогда можно в подборе использовать не перебор среди всех и как раз и использовать «списки».
EndUser
29.06.2016 00:39А если сразу генерировать цифровые последовательности так, чтобы левая ячейка была гарантированно «меньше» правой?
pav5000
29.06.2016 09:46Что в результате получилось? Industrial craft ведь, насколько могу понять по картинкам? Какая там оптимальная конфигурация реактора?
fowler
29.06.2016 19:43Расчеты еще не закончены, но некоторые результаты есть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
Trif
03.07.2016 12:04Спасибо за статью :) у меня схожая задачка. Я нарёк её «компостер»: в дополнении к вашей симметрии отсекаю также и «клонов», образующихся в результате всех поворотов и отражений (у меня сетка квадратная) — всего 11. Это как, сколько уникальных рисунков можно прокомпосировать на квадратном талоне, у которого не обозначены даже лицевая/тыльная сторона.
Приятно было прочесть, что кто-то ещё применяет тот же метод «больше-меньше».
Sirion
Алгоритм несколько неоптимален. И совсем, вопиюще прямо-таки неоптимально его использование на каждом шаге перебора.
fowler
Как бы вы его улучшили?
Sirion
Если сам алгоритм, то нам достаточно первой несимметричной пары цифр, чтобы понять, больше или меньше это число, чем оно же обращённое. Соответственно, во всех случаях, кроме палиндромов, нам не нужно вычислять все цифры, достаточно начать с пары «первая-последняя» и двигаться к центру, пока не найдём расхождение. Не могу сейчас сходу сказать точно, но по идее это должно улучшить среднее время работы алгоритма до логарифмического.
Если полный перебор, то логичнее сделать так: перебрать все возможные левые половины числа. Для каждой левой половины сначала взять правую половину, равную левой отражённой, затем увеличивать её (или уменьшать, всё равно). Такой способ гарантирует, что среди чисел, склеенных из этих двух половин, никогда не встретится пара различных симметричных.
fowler
Спасибо. Я думал о таком сравнении векторов, но это было бы в ущерб наглядности.
А по поводу второй части комментария: не хотелось выдумывать новый алгоритм генерации входящей сетки при наличии приемлемого варианта с доработкой напильником. К тому же каждая конфигурация сетки обсчитывается для конечной задачи гараздо дольше, потому не видел смысла экономить на мелочах.
Deosis
Я бы не стал передавать конфигурацию в виде номера, все равно при обработке понадобится переводить в 14-ричную СС. Передаем вектор длины 18 и экономим на преобразовании.
Скорее всего менять вектор будет быстрее, чем строить его заново каждый раз.
fowler
Да действительно. В статье переводы с 14-ричной СС и обратно показаны для наглядности критерия симметрии.
А вектор и так меняется итератором из itertools.product, а не строится заново.