2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Оптимизация графа (сокращение числа вершин)
Сообщение20.12.2017, 00:33 


15/10/13
3
Имеется вот такой граф о 18 вершинах.
Граф моделирует физическую систему. Насколько я понимаю, граф является деревом (не содержит циклов).

Вершина 0 — корень, вершины с 10 по 18 вкл. — листья, остальные вершины составляют неопределённое ядро.
У каждого из девяти листьев может быть ровно по два истока, причём веса дуг (для которых листья являются стоком) могут принимать значения либо $+1$, либо $-1$.
На дуги между вершинами, относящимися к ядру, распространяется условие: любая из вершин ядра не может быть стоком для более, чем двух, дуг.

Каждой вершине соответствует некоторое значение:
  • корню соответствует значение 1;
  • каждому стоку соответствует значение, являющееся взвешенной суммой истоков (т. е. сумма произведений веса дуги на значение соответствующего истока), причём по абсолютному значению сумма не должна превосходить любое из слагаемых более, чем в 15 раз;
  • листьям соответствуют следующие неизменные значения (номер вершины — значение): 10—58, 11—60, 12—63, 13—66, 14—68, 15—70, 16—71, 17—73, 18—76.

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

Начальное приближение (см. вот такой граф):
  • содержит в ядре вершины со следующими значениями: 1—4, 2—10, 3—14, 4—16, 5—17, 6—54, 7—64, 8—80, 9—90 (могут быть также определены через веса дуг);
  • веса дуг ($w_{\text{исток},\text{сток}}=\text{вес}$): $w_{0,1}=4$, $w_{0,2}=10$, $w_{0,5}=1$, $w_{1,3}=1$, $w_{1,4}=4$, $w_{1,10}=1$, $w_{1,11}=-1$, $w_{1,13}=1$, $w_{2,3}=1$, $w_{2,6}=1$, $w_{2,9}=1$, $w_{3,13}=-1$, $w_{3,18}=-1$, $w_{4,5}=1$, $w_{4,7}=4$, $w_{4,8}=1$, $w_{4,15}=1$, $w_{5,12}=-1$, $w_{5,16}=1$, $w_{5,17}=-1$, $w_{6,10}=1$, $w_{6,15}=1$, $w_{6,16}=1$, $w_{7,11}=1$, $w_{7,14}=1$, $w_{8,12}=1$, $w_{8,13}=1$, $w_{9,17}=1$, $w_{9,18}=1$.

Есть какие-нибудь предложения по решению такой задачи? Или рекомендации по формулированию в матричном виде оптимизационной задач для matlab или octave?
Буду весьма признателен.

 Профиль  
                  
 
 Re: Оптимизация графа (сокращение числа вершин)
Сообщение20.12.2017, 07:36 


15/10/13
3
Существенное дополнение.
Веса дуг должны быть целыми.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group