У меня есть множество неравенств, которые я должен решить.
Эти неравенства связаны с упаковкой кругов, где у меня N кругов, и все они взаимосвязаны между остальными кругами.
Какие функции я мог бы использовать для решения этой проблемы?
Я попытался использовать решение в MATLAB, но это не работает с неравенствами.
Например. учитывая 3 круга, число неравенств равно (N * (N-1)) / 2, поэтому с 3 кругами у меня есть 3 уравнения.
Назовем их A, B и C, с радиусами 200, 300 и 400 соответственно.
С A, B и C у меня есть 3 различных неравенства:
dist(a,b) >= 200+300
dist(b,c) >= 300+400
dist(c,a) >= 200+400
Где
dist(p1,p2) = sqrt((p1.x - p2.x)^2 + (p1.y - p2.y)^2)
Я хотел бы получить p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, такие как их расстояния, наиболее близкие к правой части неравенств.
С 3 кругами проблем нет, потому что это всегда будет решение, которое удовлетворяет и минимизирует неравенства, но проблема возникает, когда у меня много кругов, т.е. 10 кружков.
Цели в этом случае:
dist(a,b) = 200+300
dist(b,c) = 300+400
dist(a,c) = 200+400
Теперь я покажу вам, какова моя идея решить эту проблему:
syms x1 x2 x3 x4 x5 y1 y2 y3 y4 y5
//What I want to get
unknowns = [ x1 x2 x3 x4 x5 y1 y2 y3 y4 y5]
//Equations that must be satisfied
eqns(1) = sqrt((x1-x2)^2 + (y1-y2)^2) >= 300; // dist(1,2)>=300
eqns(2) = sqrt((x1-x3)^2 + (y1-y3)^2) >= 400; // dist(1,3)>=400
eqns(3) = sqrt((x1-x4)^2 + (y1-y4)^2) >= 350; // dist(1,4)>=350
eqns(4) = sqrt((x1-x5)^2 + (y1-y5)^2) >= 200; // dist(1,5)>=200
eqns(5) = sqrt((x3-x2)^2 + (y3-y2)^2) >= 320; // dist(2,3)>=320
eqns(6) = sqrt((x4-x2)^2 + (y4-y2)^2) >= 300; // dist(2,4)>=300
eqns(7) = sqrt((x5-x2)^2 + (y5-y2)^2) >= 330; // dist(2,5)>=330
eqns(8) = sqrt((x3-x4)^2 + (y3-y4)^2) >= 130; // dist(3,4)>=230
eqns(9) = sqrt((x3-x5)^2 + (y3-y5)^2) >= 120; // dist(3,5)>=400
eqns(10) = sqrt((x5-x4)^2 + (y5-y4)^2) >= 100; // dist(4,5)>=130
// My objective functions I want to optimize
objs(1) = sqrt((x1-x2)^2 + (y1-y2)^2) == 300; // dist(1,2)=300
objs(2) = sqrt((x1-x3)^2 + (y1-y3)^2) == 400; // dist(1,3)=400
objs(3) = sqrt((x1-x4)^2 + (y1-y4)^2) == 350; // dist(1,4)=350
objs(4) = sqrt((x1-x5)^2 + (y1-y5)^2) == 200; // dist(1,5)=200
objs(5) = sqrt((x3-x2)^2 + (y3-y2)^2) == 320; // dist(2,3)=320
objs(6) = sqrt((x4-x2)^2 + (y4-y2)^2) == 300; // dist(2,4)=300
objs(7) = sqrt((x5-x2)^2 + (y5-y2)^2) == 330; // dist(2,5)=330
objs(8) = sqrt((x3-x4)^2 + (y3-y4)^2) == 130; // dist(3,4)=230
objs(9) = sqrt((x3-x5)^2 + (y3-y5)^2) == 120; // dist(3,5)=400
objs(10) = sqrt((x5-x4)^2 + (y5-y4)^2) == 100; // dist(4,5)=130
// And now.. what can I use??
//Solve doesn't work...
solve(eqns, unknowns, IgnoreAnalyticConstraints)
Я ожидаю, что результат удовлетворяет всем уравнениям одновременно, и расстояние между каждой парой окружностей ближе всего к желаемому, но НИКОГДА не меньше его.
Вот графический пример:
Если у меня есть этот вход,
Ввод с 6 концевыми узлами
Вывод должен быть примерно таким, где соблюдаются расстояния между каждой парой терминальных узлов:
Исправлено отображение 6 кругов
Это проблема упаковки кругов с ограничениями, потому что все круги должны быть настолько близки между ними, насколько они нарисованы на входе
Эвристика должна быть такой:
1.- Добавить первый круг
2.- Добавить второй круг, который связан с первым и удовлетворяет требуемому расстоянию
3.- Добавьте третий круг, который связан с первым и вторым и удовлетворяет требуемым расстояниям
4.- ....
Может быть, я мог бы попробовать также с помощью грубой силы? Я не уверен
Большое спасибо