 |
|
|
 
|
|
Поиск максимального кол-ва пар в графе, пара - это 2 узла связаных между собой 
| voov |
|
|||
 Патамушта мы пилоты  Профиль Группа: Участник Сообщений: 460 Регистрация: 29.11.2007 Репутация: нет Всего: 8 |
Есть граф (некоторое кол-во узлов со связями между ними).
Для большей наглядности данной задачи расположим узлы по кругу (вроде циферблата часов). Каждый узел связан с произвольным кол-вом других узлов. Необходимо найти наибольшее кол-во пар узлов в графе. Пара узлов - это 2 связаных узла. Каждый узел может одновременно входить только в одну пару. Это сообщение отредактировал(а) voov - 28.4.2009, 16:55 |
|||
|
||||
Загрузка ...
| Lipetsk |
|
|||
 в форме ;) Профиль Группа: Участник Сообщений: 180 Регистрация: 28.1.2009 Где: Липецк Репутация: 2 Всего: 5 |
ответ: количество связей
|
|||
|
||||
Дата 28.4.2009, 16:24 (| voov |
|
|||
|
Патамушта мы пилоты Профиль Группа: Участник Сообщений: 460 Регистрация: 29.11.2007 Репутация: нет Всего: 8 |
пардон, не уточнил сразу. один узел может одновременно входить только в одну пару. Это сообщение отредактировал(а) voov - 28.4.2009, 16:56 |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Эта классическая задача называется "максимальным паросочетанием" ("maximum matching"). В двудольных графах это очень простой алгоритм Куна (Kuhn), в недвудольных - например, его обобщение - алгоритм Эдмондса (Edmonds), либо Кун + рандомизация, либо (но только для поиска совершенных паросочетаний) матрица Татта (Tutte).
Это сообщение отредактировал(а) maxdiver - 28.4.2009, 17:56 |
|||
|
||||
| voov |
|
||||
|
Патамушта мы пилоты Профиль Группа: Участник Сообщений: 460 Регистрация: 29.11.2007 Репутация: нет Всего: 8 |
maxdiver, благодарю за помощь и оперативность. ставлю +.
я не силен в теории графов, потому не знал, что это классическая задача. благодаря maxdiver узнал кое-чего нового. граф у меня не двудольный, по сему применил алгоритм Эдмондса. нашел статью того же maxdiver Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах, откуда взял код. все работает, единственно была ошибка в коде
исправил так:
Добавлено через 9 минут и 28 секунд хотя возможно я не прав, так как с алгоритмом ознакомился поверхностно. хотелось бы услышать по этому поводу мнение maxdiver. |
||||
|
|||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Ну да, там конечно понятно, что MAXN должно быть, только в процессе написания оно куда-то улетучилось
 Добавлено @ 21:13 Кун + рандомизация тоже жжот Рандомно перемешиваем все вершины (перенумеровываем), случайно перемешиваем все списки смежности, запускаем Куна. Несколько (раз 100 ) выполняем это дело, из всех ответов выбираем лучший. Завалить это очень сложно, скорее даже невозможно Ну и, понятно, кода будет намного меньше, чем в Эдмондсе. Кстати, вроде как конкретно моя реализация - это алгоритм Габова называется (он придумал, как безо всяких структур данных реализовать алгоритм Эдмондса за куб). Хотя я его статью не читал, может, у него на самом деле другой подход был. Это сообщение отредактировал(а) maxdiver - 30.4.2009, 21:15 |
|||
|
||||
| voov |
|
|||
|
Патамушта мы пилоты Профиль Группа: Участник Сообщений: 460 Регистрация: 29.11.2007 Репутация: нет Всего: 8 |
ага. ну тогда вопрос закрыт. контрольный пример алгоритм проглотил на ура. еще раз спасибо. |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.1265 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |