Алгоритм: парування листів та конвертів - алгоритм, узгодження, двопартійність

Відмова від відповідальності: Це не будь-яка домашня робота.

Проблема подається так: Ми отримали M конвертів і N букв, кожен з яких описується як пара позитивних чисел. Обидві конверти і букви прямокутні і, очевидно, можна повертати. "s. Мета полягає в тому, щоб знайти максимальну відповідність конверт-букв.

Проблема легко перетворюється в максимальну дводольну задачу узгодження, для якої працює алгоритм O(sqrt(M+N) * MN) існує (Хопкрофт-Карп, перетворення виконується тривіально O(MN)). Я намагався придумати жадібний алгоритм або динамічний підхід, але не знайшов.

Чи знаєте ви про більш швидке рішення?

Відповіді:

Наступний підхід "жадібного" типу може допомогти.

Визначимо m [i] як мінімум двох цілих чисел огинаючої i.

mins = distinct values of m[i], in increasing order
letters_to_match = all letters
for min in mins:
envs = envelopes i with m[i] == min
match letters_to_match with envs
remove matched letters from letters_to_match

Хіба це не еквівалентно максимальному двосторонньому збігу?

Наприклад, припустимо, у вас є алгоритм для цієї проблеми, тоді ви можете вирішити максимальне двостороннє узгодження.

З огляду на дводольний графік, ми можемо призначати кожному вузлу конверти та букви (тобто два позитивних числа) ...

Зверху, я думаю, у мене є простий алгоритм, який забезпечує оптимальне рішення, хоча це не обов'язково є найбільш ефективним.

(1) Сортувати конверти в порядку зменшення площі. (2) Для кожного конверта (A) Знайти всі літери, які будуть відповідати. (B) Виберіть той, який має найбільшу площу.

Якщо я не помиляюся, це просто O (M * (N + 1)). 2А і 2В не повинні бути окремими прогонами, оскільки літера найбільшої площі для кожної огинаючої (2В) може бути визначена в процесі 2А.

Головне тут полягає в тому, що "великий О" не завжди є найкращим показником того, як підійти до проблеми. Це лише дуже груба оцінка.

Тому алгоритм, який вимагає лише декількох кроківщо є O (M * (N + 1)), може бути набагато кращим практичним рішенням, ніж O (MN), якщо потрібно 1000 рядків коду, щоб масажувати дані у належному форматі для "більш ефективного великого" MN.

(Додано пізніше: Я не отримав "великий О" прямо там, але знову ж таки це не було призначено для того, щоб бути найефективнішим рішенням, тільки тим, що знаходить оптимальне рішення просто. І це не так, як зазначив Петро Петрович зі своїм контрприкладом.