Задача
Я пытаюсь найти решение вариации классической задачи 2D упаковки - что-то похожее на этот вопрос .
Учитывая произвольный многоугольник P и фразу W , я хочу "упаковать" буквы W в P, используя перевод, масштабирование и поворот на 90 градусов, такой что:
- буквы W обложка P в максимально возможной степени;
- буквы W обычно остаются в порядке (то есть, хотя W можно разбить на более мелкие последовательности, буквы в этой последовательности должны оставаться читаемыми).
Некоторые примеры того, чего я пытаюсь достичь:
Текущий подход
Я начал устанавливать генетический алгоритм, чтобы попытаться решить эту проблему, который использует следующий подход:
- Карты P внутри
256x256 сетки;
- Создает упрощенный ограничивающий многоугольник для каждой буквы в W ;
- Использует положение, вращение и масштаб каждой буквы как хромосому (как двоичные строки в кодировке Грея с 8 битами для каждой из x-позиции, y-позиции и масштаба и 2 бита для вращения, что приводит к хромосомам размера
26*length(W) бит);
- Использует перекрестную стратегию, которая принимает
n буквы от A и length(W) - n буквы от B ;
- Используется простая стратегия мутации, при которой вероятность того, что каждый бит будет мутирован в индивидууме, выбранном для мутации, составляет
1 / 26;
- В настоящее время оценивается пригодность на основе суммы P , охватываемой ограничивающими полигонами.
В настоящее время алгоритм работает и находит решения, хотя они пока не особо привлекательны, так как функция пригодности не учитывает перекрытие между буквами или ограничение читабельности.
Это также довольно медленно, поскольку оценка пригодности требует большого количества геометрических вычислений (я пишу алгоритм на Ruby, но использую расширение C для геометрии). Я смотрю на использование нейронной сети (или, возможно, SVM) для генерации оценок пригодности в соответствии с идеями этой статьи и этой статьи .
Вопросы
У меня есть пара вопросов о том, что я сделал до сих пор:
Во-первых, имеет ли смысл общий подход? Очевидно, что большая часть работы и времени вычислений будет заключаться в настройке функции пригодности, но прежде чем я начну понимать все эти мелочи, я хочу проверить, движусь ли я в правильном направлении, и нет другого метода, который мог бы решить эту проблему. лучше.
Как я могу сформулировать функцию пригодности для учета ограничения порядка букв / читаемости?
Есть ли какие-либо оптимизации, которые я могу внести в функцию пригодности, чтобы увеличить количество поколений, которые я могу посчитать?
Любые другие идеи или советы также будут по достоинству оценены. Я прочитал большинство существующих вопросов SO по схожим темам и прочитал ряд статей по этой теме, но не сталкивался с чем-то конкретно связанным с упаковкой текста.
Спасибо!