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

Question

Предположим, что у меня есть полный неориентированный граф G с расстоянием, связанным с каждым ребром. Значение ребра (u, v), имеющего длину l, равно «точки u и v не могут быть ближе друг к другу, чем l». Моя цель состоит в том, чтобы расположить узлы этого графа на плоскости так, чтобы ни одно из этих ограничений расстояния не нарушалось и чтобы выпуклая оболочка точек имела наименьшую общую площадь. В качестве примера, предположим, что у меня есть набор электрических компонентов, которые я хочу разместить на чипе, каждый из которых создает некоторое количество электрических помех. Если я расположу компоненты слишком близко друг к другу, они начнут мешать друг другу, делая всю систему бесполезной. Учитывая минимальные расстояния, которые каждая точка должна располагать друг от друга, каков наиболее экономичный способ размещения компонентов на микросхеме?

Я понятия не имею, как вообще начать думать об этом. Я также не знаю, как проблема может быть обобщена на случай многомерности (упаковка точек в гиперплоскость). Кто-нибудь знает хороший способ решения этой проблемы?

Answer 1

У меня есть оптимальное решение, но оно вам не понравится:).

Давайте обозначим наши узлы x ₀ , x ₁ ,..., х _н .Пусть B = max _{i, j (dist (x i , x j )), где dist (x i ,x j ) - минимальное расстояние между x i и x j .Для каждого i поместите узел x i в положение (0, i * B).Теперь каждый узел находится как минимум на расстоянии B от всех остальных, а выпуклая оболочка имеет площадь 0.}

Реальная точка зрения здесь заключается в том, что минимизация площади одной только выпуклой оболочки даст вам бессмысленное решение.Возможно, лучшей мерой будет диаметр выпуклой оболочки.

Answer 2

Я думаю, будет трудно найти оптимальный алгоритм.Я не удивлюсь, если это окажется NP-трудной проблемой.Однако, если вы заинтересованы в практическом алгоритме, который дает достойные решения, я рекомендую взглянуть на алгоритмы рисования графов на основе силы .

Вот общая идея (немного выше математика. будет появляться).Он обобщает на любое количество измерений.

Создайте функцию f, которая присваивает значение каждому разметке узла - значение, которое вы хотите минимизировать.В вашем случае функция могла бы вычислить площадь выпуклой оболочки для данного макета + большой штраф за каждое несоблюдение ограничения.Или это может быть более простая функция g, которая разумно приближается к предыдущей: короче говоря, мы хотим, чтобы g уменьшался всякий раз, когда f уменьшается, и наоборот.Хорошо выбрать относительно простую функцию, потому что вам нужно будет вычислить ее частные производные (по координатам узлов).

Теперь предположим, что у вас есть 100 узлов, и вы хотите их разложитьв 3D.Это означает, что у вас есть 300 неизвестных чисел (100 узлов на 3 координаты для каждого узла).Функция f является функцией от R ³⁰⁰ до R , и в идеале мы хотим найти ее глобальный минимум.Более реалистично будет достаточно глубокого локального минимума.

Хорошо известны численные алгоритмы для нахождения такого минимума, например: Сопряженный градиент , BFGS .Хорошо, что вам не нужно разбираться в них подробно, эти алгоритмы реализованы на многих языках.Все, что вам нужно сделать, это предоставить метод вычисления f(x) и f'(x) для любого x, запрошенного алгоритмом, и начальную компоновку x₀.

Answer 3

Это 2D проблема упаковки бункера (что NP сложнее) с дополнительными ограничениями. Я слышал, что имитация отжига очень хорошо работает для схемотехники / микросхем.

Я на самом деле ищу реальные тестовые данные о проблеме упаковки большого мусорного ведра для Планировщик слюн .