алгоритм — Максимальное переполнение стека

Question

алгоритм — Максимальное переполнение стека

Я решаю проблему соответствия с двумя vectors из class

class matching
{
public:
int n;
char match;
};

Вот алгоритм, который я пытаюсь реализовать:

int augment(vector<matching> &left, vector<matching> &right)
{
while(there's no augmenting path)
if(condition for matching)
<augment>
return "number of matching";
}

Для грубого соответствия, если left[i] соответствует right[j], затем left[i].n = j, left[i].match ='M' , right[j].n = i а также right[j].match = 'M' и непревзойденные имеют членов n = -1 а также match = 'U'

При поиске путей расширения, если один существует для другого (i, j), то мы меняем член match из того, что не имеет себе равных из 'M' в 'U' И его n = -1 и у двух совпадающих с увеличивающимся путем есть свои члены match изменилось на «А», пока мы меняем их членов n по своим показателям.

Я не знаю, является ли это правильным подходом к решению этой проблемы, это моя первая попытка максимального соответствия, я прочитал много статей и просмотрел учебники в Интернете, и я не могу заставить свой «код» функционировать должным образом.

Мне не нужен код, я могу написать свой код. Я просто хочу понять этот алгоритм шаг за шагом. Если кто-то может дать мне алгоритм, подобный тому, который я пробовал выше, я был бы признателен за это. Кроме того, если с тех пор я иду в неправильном направлении, пожалуйста, поправьте меня.

2

algorithm bipartite c++graph matching

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я не уверен, правильно ли вы находите пути расширения. Я предлагаю следующий подход.

Найти начальное соответствие жадным способом. Чтобы получить это, мы проходим через каждую вершину в левой части и жадно пытаемся сопоставить ее с какой-нибудь свободной (непревзойденной) вершиной в правой части.
Попробуйте найти увеличивающий путь P на графике. Для этого нам нужно выполнить поиск в ширину, начиная со всех свободных вершин с левой стороны и чередуясь через совпадающие и несопоставленные ребра в поиске. (то есть второй уровень содержит все правые боковые вершины, смежные с уровнем-1
вершины, третий уровень содержит все левые боковые вершины, которые
соответствует вершинам уровня 2, четвертый уровень содержит всю правую сторону
вершины, смежные с вершинами уровня 3 и т. д.). Мы прекращаем поиск, когда мы
посетить свободную вершину на любом будущем уровне и вычислить путь увеличения P
используя дерево поиска в ширину, вычисленное до сих пор.
Если мы можем найти путь увеличения P на предыдущем шаге: замените совмещенные и несопоставленные ребра в P на несоответствующие и совмещенные ребра соответственно и перейдите к шагу 2.
Иначе: полученное соответствие максимально.

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

4