Башня цветных кубиков

Question

Рассмотрим набор из n кубов с цветными гранями (каждый из которых имеет свой цвет из 4 возможных - красный, синий, зеленый и желтый). Сформируйте максимально возможную башню из k кубов (k ≤ n), правильно повернутых (12 позиций куба), поэтому боковые грани башни будут иметь одинаковый цвет, используя и эволюционный алгоритм.

Что я сделал до сих пор:

Я подумал, что подойдет следующее представление: индивидом может быть массив из n целых чисел, каждое число имеет значение от 1 до 12, указывающее текущую позицию куба (входной файл содержит n строк, каждая строка показывает информацию о цвете каждой грани куба).

Затем население состоит из нескольких лиц.

Метод Crossover должен создать нового дочернего (индивидуального), содержащего информацию от его родителей (примерно половина от каждого родителя).

Теперь моя самая большая проблема связана с методами Mutate и Fitness. В методе Mutate, если вероятность мутации (скажем, 0,01), я должен изменить позицию случайного куба с другой случайной позицией (например, третий куб может изменить свою позицию (вращение) от 5 до 12). В методе «Фитнес» я подумал, что могу сравнить два на два куба от индивидуума, чтобы увидеть, имеют ли они общие лица. Если они имеют общую грань, переменная «count» будет увеличиваться с количеством общих граней, и если все 4 боковые грани будут одинаковыми для этих 2 кубов, количество будет увеличиваться с другим количеством точек. После сравнения всех соседних кубов возвращается переменная count. Наша цель - получить как можно больше смежных кубов, имеющих одинаковые боковые грани, то есть максимизировать метод пригодности.

У меня следующий вопрос: Как можно осуществить ротацию? Я имею в виду, если куб меняет свою позицию (вращение) с 3 на 10, как мы узнаем новое расположение граней? Или, если я выполняю мутацию куба, как происходит вращение этого куба, если выбрано случайное число вращения?

Я думаю, что я должен создать вектор из 6 элементов (цвета каждой грани) для каждого куба, но когда изменяется значение вращения куба, я не знаю, каким образом элементы его вектора лица должны быть переставлены. Перетасовывать их не правильно, потому что при этом две противоположные грани могут стать смежными, что означает, что вектор больше не представляет этот конкретный куб (очевидно, две противоположные грани не могут быть смежными).

Answer 1

Во-первых, я не уверен, как вы получаете 12 вращений; Я получаю ориентации 24: 4 с каждой из 6 граней внизу. Используйте стандартный D6 (шестигранный кубик) и посмотрите, сколько разных макетов вы получите.

Очевидно, первое, что вам нужно построить, это нечто (класс?), Которое точно представляет куб в любой из доступных ориентаций. Я предлагаю вам использовать простую структуру, которая может возвращать четыре грани по порядку - скажем, передний-правый-задний-левый - с учетом куба и числа вращения.

Я думаю, что вы можете эффективно представить куб как три пары противоположных сторон. Как только вы представите эту оппозицию, оставшаяся организация будет иметь произвольную нумерацию: любой действительный выбор изоморфен любому другому. Каждое вращение будет создавать чередующуюся последовательность двух противоположных пар. Например, стандарт D6 имеет противоположные пары [(1, 6), (2, 5), (3, 4)]. Первые 8 поворотов поместили бы 1 и 6 на скрытые грани (сверху и снизу), давая вам последовательность 2354 в каждом из 4 его поворотов и их реверсы.

Этот класс является одной большой подсистемой вашей проблемы; другой, генетический алгоритм, у вас, похоже, все в порядке. Сложите все свои кубики случайным образом; «Фитнес» - это число наиболее распространенных 4-х шоу (последовательность из 4-х сторон) в стеке. В начале это обычно будет 1, так как ничего не будет соответствовать.

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

Это заставляет вас двигаться?