Max паросочетание (ГА)
Привет. Требуется помощь по задаче. Вобщем, мне необходимо написать программу нахождения максимального паросочетания в двудольном графе с помощью генетического алгоритма. Так вот, у меня возникли трудности с формализацией задачи. Необходимо определить как генерировать начальное решение и как его оценивать ?
Мои размышления по этому поводу:
Решение у меня получается это хромосома. Как я полагаю, длина решения в моем случае будет равна кол-ву ребер в графе.
Генерация начального решения
Просматриваем вершины, если ребро входит в эту вершину, то записываем в решение 1, если не входит то 0.
Оценочная фукнция
Идем по первой половине графа (по левым вершинам), если из вершины выходит более 1 ребра, то уменьшаем оценочную функцию (я делю кол-во ребер на 2), если из вершины выходит не более 1 ребра, то увеличиваем оцен. функцию (я уможаю кол-во ребер на 2)
Спасибо :)
Мои размышления по этому поводу:
Решение у меня получается это хромосома. Как я полагаю, длина решения в моем случае будет равна кол-ву ребер в графе.
Генерация начального решения
Просматриваем вершины, если ребро входит в эту вершину, то записываем в решение 1, если не входит то 0.
Оценочная фукнция
Идем по первой половине графа (по левым вершинам), если из вершины выходит более 1 ребра, то уменьшаем оценочную функцию (я делю кол-во ребер на 2), если из вершины выходит не более 1 ребра, то увеличиваем оцен. функцию (я уможаю кол-во ребер на 2)
Спасибо :)