алгоритм — Максимальное переполнение стека
Я решаю проблему соответствия с двумя 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 по своим показателям.
Я не знаю, является ли это правильным подходом к решению этой проблемы, это моя первая попытка максимального соответствия, я прочитал много статей и просмотрел учебники в Интернете, и я не могу заставить свой «код» функционировать должным образом.
Мне не нужен код, я могу написать свой код. Я просто хочу понять этот алгоритм шаг за шагом. Если кто-то может дать мне алгоритм, подобный тому, который я пробовал выше, я был бы признателен за это. Кроме того, если с тех пор я иду в неправильном направлении, пожалуйста, поправьте меня.
Решение
Я не уверен, правильно ли вы находите пути расширения. Я предлагаю следующий подход.
-
Найти начальное соответствие жадным способом. Чтобы получить это, мы проходим через каждую вершину в левой части и жадно пытаемся сопоставить ее с какой-нибудь свободной (непревзойденной) вершиной в правой части.
-
Попробуйте найти увеличивающий путь P на графике. Для этого нам нужно выполнить поиск в ширину, начиная со всех свободных вершин с левой стороны и чередуясь через совпадающие и несопоставленные ребра в поиске. (то есть второй уровень содержит все правые боковые вершины, смежные с уровнем-1
вершины, третий уровень содержит все левые боковые вершины, которые
соответствует вершинам уровня 2, четвертый уровень содержит всю правую сторону
вершины, смежные с вершинами уровня 3 и т. д.). Мы прекращаем поиск, когда мы
посетить свободную вершину на любом будущем уровне и вычислить путь увеличения P
используя дерево поиска в ширину, вычисленное до сих пор. -
Если мы можем найти путь увеличения P на предыдущем шаге: замените совмещенные и несопоставленные ребра в P на несоответствующие и совмещенные ребра соответственно и перейдите к шагу 2.
-
Иначе: полученное соответствие максимально.
Этот алгоритм требует поиска в ширину для каждого дополнения, поэтому сложность в худшем случае O(nm), Хотя Алгоритм Хопкрофта-Карпа может выполнять несколько расширений для каждого поиска в ширину и имеет лучшую сложность в худшем случае, это
Кажется (из статьи в Википедии), что это не быстрее на практике.
Другие решения
Других решений пока нет …
detector