Алгоритм подгонки объектов в пространстве
У меня есть коллекция квадратов и прямоугольников разных размеров, которые я хочу объединить с помощью PHP в один большой квадрат / прямоугольник. Квадраты, как правило, представляют собой изображения, которые я хочу превратить в монтаж, но иногда это просто математические объекты.
Существуют ли какие-либо PHP-алгоритмы для этого и как это называется?
Обновление: после дополнительных поисков, я думаю, что я хочу, называется проблемой упаковки бункера. Тем не менее, я также хотел бы добавить определенное количество рандомизации для определенных типов проблем упаковки (таких как изображения), чтобы позволить человеческий интерес.
3 ответа
Двухмерная упаковка в бункеры - это NP-сложная задача. Однако существуют алгоритмы аппроксимации.
Посмотрите на этот код (и объяснение). Он содержит несколько алгоритмов и графический интерфейс:
У меня есть 1d алгоритм упаковки бина в php. Вы хотите искать наиболее подходящую, первую пригодность и так далее. Но это не для 2d проблемы, может быть, вы хотите найти проблему с рюкзаком?
Я думаю, что вы можете использовать алгоритм Semulated Annealing. Я использовал его, чтобы заполнить прямоугольные газетные страницы прямоугольной рекламой. Как вы сказали, вы можете начать с рандомизированного решения, а затем вы можете постепенно найти хорошее решение. Смотрите здесь http://codetuner.blogspot.com/2010/03/simulated-annealing-approach-to.html. Я использовал это, чтобы решить проблему нумерации страниц. Я думаю, что вы можете использовать его для вашего требования тоже.