Дано: граф, напоминающий карту дорог, с той лишь разницей, что относительное положение вершин-городов на плоскости роли не играет. Требуется: перемещая вершины на плоскости, построить изображение этого графа с наименьшей суммарной длинной дорог и с наименьшим количеством их пересечений. Ткните, плиз, в алгоритм решения или в научное название этой проблемы. Гуглем искал - не нашёл, похоже я просто не знаю правильных ключевых слов.

-- Update 1

Дискуссия показала, что требуется минимизировать следующую функцию:

W = ( (I0 - I(g))^2 + (L0 - L(g))^2 )^1/2,

I(g) - количество пересечений рёбер графа g
L(g) - суммарная длинна рёбер графа g
I0 = 0 - идеальное-нулевое количество пересечений
L0 = |Eg| * L1 - идеальная суммарная длина рёбер
L1 - единичная длина ребра

Вопрос о том, как это сделать остаётся открытым. 

-- Update 2

Реальный граф имеет около 850 вершин и 3000 рёбер. Каждая вершина связана, в среднем, с 5-ю другими. Максимальное число связей 103 и минимальное 1.

BDD Path Length Minimization ?

M maxim1000

решения о закрытии тем принимают (ко)модераторы, не нужно вводить людей в заблуждение...

Тут вас надо тыкнуть в Базисные знания.


НЕЛЬЗЯ минимизировать ОДНОВРЕМЕННО по ДВУМ  КРИТЕРИЯМ





вывод: в вашей постановке задеча не решабельна.
топик закрыт. Поясню, в данной постановке задача нерешаема, посему дальнейшее обсуждение исходной задачи будет профанацией. Соответсвенно надо или менять постановку задачи или закрывать топик. 

То что вам предложили выше не может быть решением ВАШЕЙ задачи

Это сообщение отредактировал(а) esperant0 - 22.11.2007, 15:39

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

,

пожалуйста, поясните. Что есть критерий? Функционал? = Нельзя минимизировать функционал?

stab, не знаю, вкурсе ты или нет, но есть готовая библиотека для визуализации графов. Graphviz называется. http://www.graphviz.org/Documentation.php Там у них есть ссылочка с названием Theory. 
Может быть поможет...

Cтоп. Я не говорил что вы дали решение. 

Вы дали ссылку, а условие автора не имеет решение. Каков смысл в ссылке? Никакого.

Добавлено через 2 минуты и 7 секунд

Пожалуйса.


Пусть f(x)  количество пересечений
g(x) длина ребер
s(t) набор огранечений задачи тогда


{
  f(x)  -> min
  g(x) -> min

  constraints :

}

 В общем случае нерешаема. Это известный факт.

Добавлено через 3 минуты и 12 секунд

Вряд ли это библиотека решает нерешаемую задачу. Разве что математика противоречива

нельзя одновременно минимизировать два функции. (В общем случае)

marcusmae, это скорее интелу надо эту ссылочку заслать. хотя интересно 

SaDFromSpb, спасибо, глянул. для планарных графов работает, для остальных - тихий ужас.

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



Присоединённый файл ( Кол-во скачиваний: 23 )
 graphs.gif 4,93 Kb

esperant0, на счёт минимизации вы сильно ошибаетесь. если есть оценочная функция от всех рёбер графа, то как она считается - дело десятое. например, как произведение кол-ва пересечений и суммарной длинны рёбер или выдаёт вектор из двух этих значений. главное чтобы существовала возможность сопоставления по принципу больше-меньше. но хотелось бы обойтись без перебора всех возможных размещений вершин на плоскости.


где можно об этом почитать?

Нет я хочу сказать что невозможно минимизировать одновременно две функции.Не верите


Вот вам задача

2x -> min

-x - > min


10>x>-10

-------------------------


Минимум одной ф-ии в точке 10 минимум второй в точке -10.

А вот в какой точке минимум одновременно двух ф-й да не в какой.

------------

Где это написано. А в свое время рассказывал это в курсе исследования операций поищите

Добавлено через 6 минут и 22 секунды

Минимизировать одновременно две фунции нельзя. ( в общем случае)


Можно минимизировать сумму этих ф-ий, но одновременно две функции минимизировать нельзя.


---------------------------

Пример:

завод

цель 1) минимизировать  количество работников
         2) минимизировать минус прибыль фирмы.


Минимизировать количество работников это никого не нанимать

Максимизировать прибыль это нанять бесконечное число работников.

-------------

Как же минимизировать одновременно две функции? 

(пример не формальный но суть ясна_

esperant0, 
ээээ...а вы не путаете минимум функции с критерием минимизации..

вы не минимум функций вычисляете, а ищите как можно меньшее значение функции...
в том примере есть множество допустимых решений от -10 до 10...

в соответствии с этими решениями можно вычислять значения функций f1 и f2, которые вы хотите минимизировать (не найти минимум, а минимизировать)
Поскольку у вас 2 критерия - надо оценивать по ним обоим...
например при x = 1 получается (f1,f2)=(2,-1)
при x = 2 получается (f1,f2)=(4,-2)...по сравнению со значениями функции при  (x == 1) это значение сравнивать нельзя, поскольку f2 улучшилась, а f1 ухудшилась с нашей точки зрения (для нас лучше та, что меньше, потому что критерий на минимум)...вот так и проверяешь...
если ты можешь сравнить, что у тебя при каком-то x и f1 улучшилась, и f2 улучшилась по сравнению со значением в какой-то точке xo - значит точка xo в ответ не входит, поскольку нашли точку лучше

берёте и по отдельности каждую минимизируете. если надо одновременно, значит функции являются параметрами для целевой, которую и надо минимизировать.

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

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

Добавлено через 6 минут и 9 секунд
.. динамическое программирование тоже мимо, т.к. задача не сводится к подзадачам, точнее они могут влиять на результаты уже решённых подзадач.

Я понял вашу идею. Но она не верна. Ибо, отношения порядка однозначно неопределено для пар.

Автор в своем условииопределил отношение порядка? Нет

Добавлено через 2 минуты и 33 секунды

Я дал вам конкретный пример с х. Решите его.


Поймите конь здесь не причем. Математика вещь упрямая и не терпит невежества. Т.е вы можете отвергать математику. Толку будет мало.


Еще раз. Одновременно минимизировать две ф-ии нельзя. 
Пока вы с этим не согласны, вы не согласны с математикой. Тогда что вы хотите? псевдонаучное решение?

Добавлено через 4 минуты и 27 секунд
Упрощю вам задачу. Минимизируйте следующее две ф-ии


х   -> minimum
-x -> minimum


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

на грани гениальности



и при этом очень пафосно

То есть, я сомневаюсь, что приведённые Вами примеры хоть сколько-нибудь переносимы на задачу, которую описал stab. С чего вы вообще взяли, что это - минимизация на функциях? Почему нельзя построить функционал и искать, скажем, седловые точки? Впрочем последний вопрос уже по постановке задачи, и пока она не будет точной и корректной, всё это будет бесполезными разговорами. Поставить задачу - это же уже полрешения  

Это сообщение отредактировал(а) marcusmae - 22.11.2007, 22:32

esperant0, мне понятно, что два вас неразрешимой задачей является подстановка подходящей функции вместо слова "и" в фразе "с наименьшей суммарной длинной дорог и с наименьшим количеством их пересечений". как разберётесь с этой архи-наисложнейшей неформализуемой задачей, возвращайтесь, пожалуйста, и доложите о результатах, это очень важно.

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

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

а вместо "и" можно, действительно, ставить разные функции (на вскидку - сложение или умножение уже могут дать разный результат, не говоря уже о том, что сложение может быть с коэффициентами, а умножение - с разными степенями), и я бы не сказал, что на данный момент очевидно, какую взять

Конечно задача. Вы правы. Но менять условие задачи имеет право лишь автор. Иначе мы рискуем решить не ту задачу

я же приводил выше эту функцию:


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

Перебор для непрерывных ф-ий требует континума шагов.

esperant0, можно узлы к дискретной сетке привязать, только при 1000 узлов (в реальной задаче около 850) и при минимум 1000 возможных размещений для каждого, получается 1000^1000 размещений. это уже за пределами возможностей.

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

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

появилась похожая тема о визуализации графов: http://forum.vingrad.ru/forum/topic-183717.html
критерий там несколько проще - просто минимизировать количество пересечений рёбер
так что, думаю, здесь можно продолжить обсуждать усложнённый критерий, и к чему он приводит, а все вопросы, касающиеся простой минимизации пересечений обсуждать там

это я к тому, что с одной стороны темы объединять не хочется, т.к. всё-таки задачи и решения отличаются, но, с другой стороны, участникам темы может быть информация, отражённая в той теме...