IPB

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в эту темуОткрыть новую тему
> Найти максимальный разрез в графе методом ветвей и границ, Описание соответствует названию
Daniel
сообщение 13.1.2010, 21:47
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 1
Регистрация: 13.1.2010
Город: Сыктывкар



Необходимо написать алгоритм для нахождения максимального разреза в графе методом ветвей и границ.
Т.Е. если R(S,T)-вес разреза в графе. то максимизировать R(S,T) = max Суммы по i Cуммы по j wij.
R(S,T) можно записать в виде сумм (1-yiyj)*wij/2, где если yi принадлежит S, то yi=-1, и если T, то yj=1.
Строится дерево перебора G всевозможных n мерных векторов (y1.....yn), где yi принадлежит {-1,1}.
Вопрос: Как оценить множество G, G(1), G(-1), G(-11), G(-1-1), и так далее
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия Сейчас: 29.3.2024, 13:12

Книжки в помощь: "Сборник заданий по высшей математике" Кузнецов Л.А., "Сборник заданий по высшей математике" Чудесенко В.Ф., "Индивидуальные задания по высшей математике" Рябушко А.П., и другие.




Зеркало сайта Решебник.Ру - reshebnik.org.ru