Точки с плотной упаковкой в ​​самолете?

Предположим, что у меня есть полный, неориентированный граф 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₀.