Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск максимального кол-ва пар в графе

Автор: voov 28.4.2009, 15:36

Есть граф (некоторое кол-во узлов со связями между ними).
Для большей наглядности данной задачи расположим узлы по кругу (вроде циферблата часов).
Каждый узел связан с произвольным кол-вом других узлов.

Необходимо найти наибольшее кол-во пар узлов в графе.
Пара узлов - это 2 связаных узла. Каждый узел может одновременно входить только в одну пару.

Автор: Lipetsk 28.4.2009, 16:24

ответ: количество связей

Автор: voov 28.4.2009, 16:47

Цитата(Lipetsk @ 28.4.2009, 16:24

)

ответ: количество связей

пардон, не уточнил сразу. один узел может одновременно входить только в одну пару.

Автор: maxdiver 28.4.2009, 17:54

Эта классическая задача называется "максимальным паросочетанием" ("maximum matching"). В двудольных графах это очень простой алгоритм Куна (Kuhn), в недвудольных - например, его обобщение - алгоритм Эдмондса (Edmonds), либо Кун + рандомизация, либо (но только для поиска совершенных паросочетаний) матрица Татта (Tutte).

Автор: voov 30.4.2009, 16:39

maxdiver, благодарю за помощь и оперативность. ставлю +.

я не силен в теории графов, потому не знал, что это классическая задача.
благодаря maxdiver узнал кое-чего нового.

граф у меня не двудольный, по сему применил алгоритм Эдмондса.
нашел статью того же maxdiver http://e-maxx.ru/algo/matching_edmonds, откуда взял код. все работает, единственно была ошибка в коде

Код


int lca (int a, int b) {
    bool used[] = { 0 };     // <-- выделяется память под массив из 1го элемента
    // поднимаемся от вершины a до корня, помечая все чётные вершины
    for (;;) {
        a = base[a];
        used[a] = true;     // <-- здесь портим память
        if (match[a] == -1)  break; // дошли до корня
        a = p[match[a]];
    }
    // поднимаемся от вершины b, пока не найдём помеченную вершину
    for (;;) {
        b = base[b];
        if (used[b])  return b;
        b = p[match[b]];
    }
}

исправил так:

Код


    bool used[MAXN] = { 0 };

Добавлено через 9 минут и 28 секунд
хотя возможно я не прав, так как с алгоритмом ознакомился поверхностно. хотелось бы услышать по этому поводу мнение maxdiver.

Автор: maxdiver 30.4.2009, 21:09

Ну да, там конечно понятно, что MAXN должно быть, только в процессе написания оно куда-то улетучилось smile

Добавлено @ 21:13
Кун + рандомизация тоже жжот smile

Рандомно перемешиваем все вершины (перенумеровываем), случайно перемешиваем все списки смежности, запускаем Куна. Несколько (раз 100 smile

) выполняем это дело, из всех ответов выбираем лучший. Завалить это очень сложно, скорее даже невозможно smile

Ну и, понятно, кода будет намного меньше, чем в Эдмондсе. Кстати, вроде как конкретно моя реализация - это алгоритм Габова называется (он придумал, как безо всяких структур данных реализовать алгоритм Эдмондса за куб). Хотя я его статью не читал, может, у него на самом деле другой подход был.

Автор: voov 5.5.2009, 10:25

Цитата(maxdiver @ 30.4.2009, 21:09

)

Ну да, там конечно понятно, что MAXN должно быть,

ага. ну тогда вопрос закрыт. контрольный пример алгоритм проглотил на ура.

еще раз спасибо.