Жадный алгоритм для двудольного сопоставления

Question

Итак, я столкнулся с проблемой, в которой были «n» пилоты и «м» самолеты. У каждого пилота был список самолетов, которые он мог летать. И один пилот может летать только на одном самолете за раз. Вы должны были определить максимальное количество самолетов, которые могут летать одновременно. Стандартная проблема двустороннего сопоставления (о которой я узнал позже).

В конкурсе, я придумал жадный алгоритм следующим образом:

Хотя есть самолеты в графике:

1) Выберите плоскость, которая может быть пролетела минимальным число пилоты

2) Жадно выделить пилот этой плоскости (из тех, кто может летать)

3) Удалите как плоскость и а, llocated пилот из графика

В общем, для двудольных паросочетаний, предлагаю следующий алгоритм:

Хотя есть узлы в правильном наборе двудольного графа:

1) Выберите узел справа, установленный с минимальной входящей степенью

2) Жадно сопоставить его с ЛЮБОЙ точкой f (который имеет к нему край)

3) Удалите оба этих узла из графика (это также приведет к уменьшению входящей степени всех узлов справа, к которым этот узел имеет ребро)

Я не математически опытным, чтобы доказать правильность этого алгоритма и после того, как много мыслей я не был в состоянии придумать контрпример. Итак, мой конкретный вопрос: это стандартный или известный алгоритм, или я делаю какую-то вопиющую ошибку, которую я не вижу?

Пожалуйста, не стесняйтесь редактировать мой вопрос, чтобы сделать его более ясным, если вы так чувствуете. Спасибо.

Answer 1

контрпример:

a1 a2 a3 a4 a5 
p1 x x 
p2 x x x x   
p3 x x x x 
p4     x 
p5   x x x 

a5 выбран первым. Случайно выберите пилот, который МОЖЕТ быть p5. Если это так, p4 не имеет плоскости.

Answer 2

Жадный подход не будет работать на двухстороннем согласовании. Проблема, о которой вы могли догадаться, заключается в «выборе любого узла слева».

Вот пример: узлы слева - это A, B, C и D, а справа - x, y, z, t. Соедините каждый из A, B, C с каждым из x, y, z (так что здесь 9 ребер) соединяют D с t и A с t. В результате у вас есть 3 узла справа с степенью 3 (x, y, z) и один со степенью 2 (t). Таким образом, вы выбираете t, и вы выбираете один из узлов слева случайным образом - это может быть A или D. Проблема в том, что если вы выберете A, ваше совпадение будет иметь размер 3, а реальный ответ - 4 (путем выбора D) ,

Answer 3

Нет причин использовать жадный алгоритм! Если вы не можете доказать свою правильность, то это неверно. И вот, например, ваш жадный алгоритм терпит неудачу, потому что его вывод зависит от порядка вершин.

Вы должны прочитать эту статью: https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Algorithms_and_computational_complexity

Существует, например, эффективный алгоритм для двудольных графов: Hopcroft-Karp