Найти максимальный разрез в графе методом ветвей и границ, Описание соответствует названию |
Здравствуйте, гость ( Вход | Регистрация )
Найти максимальный разрез в графе методом ветвей и границ, Описание соответствует названию |
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), и так далее |
Текстовая версия | Сейчас: 29.3.2024, 13:12 |
Зеркало сайта Решебник.Ру - reshebnik.org.ru