Оптимальное размещение 4 слов внутри сетки произвольного размера

Постановка задачи:

Имея четыре слова, поместите их в сетку квадратов размером m x n так, чтобы площадь сетки была как можно меньше.

Слова должны идти слева направо и сверху вниз внутри сетки. Буквы могут перекрываться, но дополнительные слова образовываться не могут. Все слова должны быть связаны друг с другом в одну гигантскую цепочку.

Примеры сеток, которые можно составить из 4 слов «один, два, три и четыре». Обратите внимание, что последняя сетка является наиболее оптимизированной.

введите здесь описание изображения

Я пытаюсь выучить python и подумал, что это будет хорошее приложение, чтобы отточить свои зубы.

Любые идеи, как структурировать мои данные и алгоритмы для решения такой проблемы? Я не ищу прямого ответа, но некоторые советы, как:

Используйте эту библиотеку, или этот класс, или эту структуру данных. Или итерации, как это через доступное пространство.


python optimization algorithm constraint-satisfaction
person Auburnate    schedule 26.06.2013    source источник
comment
Что не так с ONE TWO THREE FOUR?   -  person tmyklebu    schedule 26.06.2013
comment
Отличный момент! :) Все слова должны быть связаны друг с другом в одну гигантскую цепочку.   -  person Auburnate    schedule 26.06.2013
comment
На самом деле эта проблема очень похожа на n-queens. Возможно, вы сможете использовать некоторые решения этой проблемы для вдохновения. Основным отличием является выходная сетка переменного размера для любого входа.   -  person Brian    schedule 26.06.2013

Ответы (1)


arrow_upward
2
arrow_downward

Подумайте, какой максимальный размер сетки вам понадобится? Если это слова one, two, three, four, то сетка максимального размера будет

12 x 12. Это размер сетки, в которой каждое слово расположено встык, разделяя последнюю букву предыдущего слова.

Теперь у нас есть место. Как вы вписываете слова в пространство? Попробуйте подумать о методе грубой силы. Что это повлечет за собой?

Попробуйте перебрать все возможные комбинации шаблонов. Вы можете разместить каждое слово 24 способами, а слов всего 4, так что у вас будет около 500 000 комбинаций, что не так много для современных компьютеров. Посмотрите, какие шаблоны действительно соответствуют критериям (буквы совпадают и т. д.).

Если у вас есть метод грубой силы, как вы можете его усовершенствовать?

Что касается структуры данных, вам просто нужна сетка, в которой можно хранить символы. Вы можете использовать структуру вложенного списка, массив numpy, pandas или множество других вещей. Сначала постарайтесь решить проблему просто, а потом уточняйте.

person wflynny    schedule 26.06.2013