0 / 0 / 0
Регистрация: 17.03.2015
Сообщений: 4
1

Алгоритм Куна

26.02.2016, 19:52. Показов 2471. Ответов 2
Метки нет (Все метки)

Доброго времени суток. Необходимо решить задачу о назначениях, все шло отлично пока не дошло до поиска максимального паросочетания. Нашел множество примеров и интернете, но не один не дает верного результата.
Так же не могу понять как работает сам алгоритм, в частности строку int to = CombinatonMatrix[v,i];(в коде ниже), какой смысл брать значение 1 или 0, которыми заполнена матрица смежности, в качестве индекса массива?
Вот кусок кода на C# в котором я начинаю поиск максимального паросочетания, прошу помочь разобраться с алгоритмом
C#
1
2
3
4
5
6
7
8
9
       
            SearchResult = new int[size];
            visited = new bool[size];
            fillValue(SearchResult, -1);//заполнение массива результатов значением -1
            for(int i = 0; i < size;i++)
            {
                fillFalse(visited);//заполнение массива visited значением 0
                try_kuhn_dfs(i);
            }
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    static bool try_kuhn_dfs(int v)
        {
            if (visited[v]) return false;
            visited[v] = true;
            for (int i = 0; i < size; ++i)
            {
                int to = CombinatonMatrix[v,i];//CombinatonMatrix[,] - матрица смежности заполненная 0 и 1 в зависимости от наличия пути из v в i
                if (SearchResult[to] == -1 || try_kuhn_dfs(SearchResult[to]))
                {
                    SearchResult[to] = v;
                    return true;
                }
            }
            return false;
        }
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.02.2016, 19:52
Ответы с готовыми решениями:

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар)
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм 1. Объясни, что...

Разработать алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм
Расставить строки данной матрицы в порядке возрастания наибольших элементов в строках.

2
Заблокирован
27.02.2016, 14:39 2
jidjid
Вы извините. Я хотел спросить, что означает
"максимальное паросочетание"? Это когда
Сумма двух рядом стоящих элементов массива
максимальна? Или это что-то иное?
0
Модератор
2961 / 2100 / 450
Регистрация: 26.03.2015
Сообщений: 8,158
27.02.2016, 15:26 3
Цитата Сообщение от jidjid Посмотреть сообщение
int to = CombinatonMatrix[v,i];
правильно будет:
int to = g[v][i];
где g[v] - список/массив индексов смежных элементов v-того элемента.

Добавлено через 5 минут
Цитата Сообщение от ichs Посмотреть сообщение
что означает "максимальное паросочетание"?
максимальное паросочетание
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.02.2016, 15:26
Помогаю со студенческими работами здесь

Алгоритм устранения непродуктивных нетерминалов, алгоритм построения недостижимых символов
Задание: найдите лишние нетерминалы в следующей грамматике с начальным нетерминалом S и в...

Построить алгоритм Маркова, который ищет НОД (Алгоритм Евклида)
Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в...

Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке [a,b] с шагом h.
Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке с шагом h....

Составить алгоритм-вычисление квадрата суммы двух чисел и алгоритм для вычисления функции
Здравствуйте!Мне нужно все с самого начала и точно,помогите пожалуйста! 1.составить...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru