Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
bossyara
0 / 0 / 0
Регистрация: 18.03.2015
Сообщений: 7
#1

Алгоритм визуализации сети с наложениями - Алгоритмы

01.03.2016, 21:23. Просмотров 232. Ответов 4
Метки нет (Все метки)

Нужен алгоритм, для лучшей визуализации некоторой схемы, путем разложения линий (каждая из которых на самом деле состоит из нескольких линий и соответствует определенной подсети).
При этом накладывается условия о минимальном кол-во пересечений. Таким образом необходимо, развести линии, на небольшое расстояние друг от друга (чтоб визуально можно было выделить полностью каждую подсеть в отдельности).
Алгоритм визуализации сети с наложениями
Пример на рис.1 показан пример с тремя сетями (желтая, зеленая и бордовая). Видно, что линии сходятся в одну. Необходим результат как на рисунке 2.
Алгоритм визуализации сети с наложениями
Кстати, тут не совсем оптимально разнесены, надо желтую с зеленной поменять местами.
Я разобрался как разводить наложенные прямые, а вот выбрать порядок, так чтоб кол-во пересечений было наименьшее кол-во, пока не знаю. Есть идея, искать участки (пути) состоящие из "накладных" линий, и начиная с участков с наибольшим кол-вом таких наложений высчитывать оптимальный вариант расположения этих линий, но тут есть нюанс. Например сходятся два участка, в одном линии состоят из 3-х линий, а в другом из 2-х. В одном получается, что оптимальнее располагать например желтую - синюю - бордовую, а в другом бордовую-желтую. Таким образом на стыке необходимо, как-то перекрещивать линии.
Возможно я изобретаю велосипед (скорее всего), но серфинг, толку мало дал, я нашел как рисовать параллельные прямые под разными углами, соединять их и т.д. Кстати, линии могут быть ортогональны и наклоны, кривых нет.
Т.е. я могу нарисовать с разложенными линиями, а вот как при этом разложении учесть условия оптимальности (суммарное минимальное кол-во пересечений)?
Может кто сталкивался с похожими задачами, ткинете носом пожайлуста. Крутиться в голове теория графов, но каков именно алгоритм?
http://www.cyberforum.ru/algorithms/thread1194358.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.03.2016, 21:23
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм визуализации сети с наложениями (Алгоритмы):

Разработка алгоритма визуализации чертежа
Разработка алгоритма визуализации чертежа. Подскажите, какой алгоритм можно...

Алгоритм работы сети.
Всем привет. Прочитал кое что про лок сети но так до конца и не понял как...

sorting networks\сортирующие сети алгоритм
помогите пожалуйста написать (шаблонный) алгоритм сортировки массива\вектора (n...

Нейронные сети. Алгоритм обратного распространения
Ребят помогите мне срочно нужно реализовать на C++ алгоритма обратного...

Помогите набросать алгоритм написания соц. сети?
всем привет. Помогите набросать алгоритм написания соц. сети?

4
Shamil1
Модератор
2068 / 1374 / 303
Регистрация: 26.03.2015
Сообщений: 5,002
02.03.2016, 01:24 #2
6 вариантов всего... пусть программа попробует их все и сравнит количество пересечений
0
bossyara
0 / 0 / 0
Регистрация: 18.03.2015
Сообщений: 7
02.03.2016, 08:36  [ТС] #3
Это тестовый пример. Стартовых может быть до двадцати, а конечных в разы больше.
0
bossyara
0 / 0 / 0
Регистрация: 18.03.2015
Сообщений: 7
02.03.2016, 08:42  [ТС] #4
Пример более сложной сети.
Алгоритм визуализации сети с наложениями
0
Shamil1
Модератор
2068 / 1374 / 303
Регистрация: 26.03.2015
Сообщений: 5,002
02.03.2016, 10:01 #5
Цитата Сообщение от bossyara Посмотреть сообщение
Это тестовый пример. Стартовых может быть до двадцати, а конечных в разы больше.
Как оптимизировать - это решается на основе того, как обычно выглядят оптимизируемые сети. Оптимизируется не произвольная картинка, а картинка, удовлетворяющая некому набору ограничений. Я не могу угадать, какому набору ограничений удовлетворяют Ваши картинки.

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

Если кратко:
Шаг - минимальные изменения, например, поменять местами две соседние линии на каком-то отрезке. Вероятно, Вы используете подобные "шаги" в своём алгоритме "развода прямых".
Целевая функция - количество пересечений.

1. Разводите линии случайным образом.
2. Перебираете все возможные "шаги".
2а. Если нашёлся шаг, улучшающий целевую функцию, выполняете его. Переходите к пункту 2 для нового состояния.
2б. Если улучшающих шагов нет, то запоминаете решение. Переходите к пункту 1.

Количество перезапусков определите сами.
0
02.03.2016, 10:01
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.03.2016, 10:01
Привет! Вот еще темы с решениями:

Алгоритм Форда-Фалкерсона, максимальный поток в сети
Первое красное значение на пути это вес а второе поток. Проблема заключается в...

Гибридный алгоритм обучения нечеткой сети TSK
Здравствуйте! Нужно обучить нейронную сеть Такаги-Сугено-Канга. Сеть написана...

Алгоритм обратного распространения ошибки. Нейронные сети
Прошу помощи с реализацией алгоритма обратного распространения ошибки. Написал...

Необходимо подобрать алгоритм шифрования(симметричный, поточный) для передачи потокового видео по сети
Необходимо подобрать алгоритм шифрования(симметричный, поточный) для передачи...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru