Точки с плотной упаковкой в самолете?
Предположим, что у меня есть полный, неориентированный граф G с расстоянием, связанным с каждым ребром. Значение ребра (u, v), имеющего длину l, является "точками u и v не может быть ближе друг к другу, чем l". Моя цель состоит в том, чтобы заложить узлы этого графика в плоскости, чтобы ни одна из этих ограничений расстояния не была нарушена и чтобы выпуклая оболочка точек имела наименьшую общую площадь. В качестве примера предположим, что у меня есть куча электрических компонентов, которые я хочу поместить на чип, каждый из которых генерирует некоторое количество электрических помех. Если я поставил компоненты слишком близко друг к другу, они начнут мешать друг другу, делая всю систему бесполезной. Учитывая минимальные расстояния, каждая точка должна быть от точки друг друга, какой наиболее экономичный способ размещения компонентов на чипе?
Я понятия не имею, как начать думать об этом. Я также не знаю, как проблема может быть обобщена на более высокомерный случай (точки упаковки в гиперплоскость). Кто-нибудь знает о хорошем способе решения этой проблемы?
Ответы
Ответ 1
У меня есть оптимальное решение, но вам это не понравится:).
Пусть обозначают наши узлы x 0, x 1,..., x n. Пусть B = max i, j < n (dist (x i, x j)), где dist (x i, x j) - минимальное расстояние между x i и x j. Для каждого я поместите node x i в положение (0, я * B). Теперь каждый node находится, по крайней мере, от всех остальных, а выпуклая оболочка имеет площадь 0.
Реальная точка здесь заключается в том, что минимизация площади только выпуклого корпуса даст вам бессмысленное решение. Возможно, лучшей мерой будет диаметр выпуклой оболочки.
Ответ 2
Я думаю, будет сложно найти оптимальный алгоритм. Я не удивлюсь, если это окажется NP-трудной проблемой. Однако, если вам интересен практический алгоритм, который дает достойные решения, я рекомендую взглянуть на алгоритмы рисования на основе силы.
Здесь появится общая идея (появится более высокая математика). Он обобщает на любое количество измерений.
Построить функцию f
, которая присваивает значение каждому макету node - значение, которое вы хотите свести к минимуму. В вашем случае функция могла бы вычислить площадь выпуклой оболочки для данного макета + большой штраф за каждое ограничение, которое не было выполнено. Или это может быть более простая функция g
, которая разумно аппроксимирует предыдущую: короче говоря, мы хотим, чтобы g
уменьшался всякий раз, когда f
становится меньше, и наоборот. Хорошо выбрать относительно простую функцию, потому что вам нужно будет вычислить ее частные производные (относительно координат узлов).
Теперь скажем, у вас есть 100 узлов, и вы хотите выложить их в 3D. Это означает, что у вас 300 неизвестных номеров (100 узлов раз по 3 координаты для каждого node). Функция f
- это функция от R 300 до R, и в идеале мы хотим найти ее глобальным минимумом. Более реалистично достаточно достаточно глубокого локального минимума.
Известны численные алгоритмы для нахождения такого минимума, например: Conjugate gradient, BFGS. Хорошо, что вам не нужно понимать их подробно, эти алгоритмы реализованы на многих языках. Все, что вам нужно сделать, это предоставить метод вычисления f(x)
и f'(x)
для любого x
, запрошенного алгоритмом, и начальный макет x₀
.
Ответ 3
Это 2D проблема с упаковкой бинов (которая NP жестко) с дополнительными ограничениями. Я слышал, что симулированный отжиг отлично работает для проектирования схем/чипов.
Я на самом деле ищет реальные тестовые данные для большой проблемы упаковки корзины для Drools Planner.