Алгоритм соответствия в двудольном графе

Question

Я знаю, это похоже на домашнюю работу в школе, но это настоящая проблема для бизнеса. Поскольку я не могу написать, с каким объектом мы работаем, я буду использовать сюрреалистическое описание проблемы c:

Существует несколько городов (несколько десятков). В каждом городе есть максимальное количество ракет, которое может поразить его (от 1 до нескольких сотен).

Существует также множество ракет, распространенных по всему миру (около 1-2 тысяч). У каждой ракеты есть список городов, на которые она может нацелиться. Может быть только один город, может быть несколько или он может содержать все возможные города.

Задача:

Назначать цели ракетам, чтобы максимальное количество ракет могло быть выпущено.

То, что мы делаем сейчас, - это решение «наивная сила-случайность»:

1. Randomly sort list of missiles
2. Pass each missile, and set it to target first city from it's list, that still can accept missile
3. Count number of of targeted missiles
4. If it's better than best solution so far, save it
5. Repeat multiple times (we can do this about 1-10 million times in reasonable time).

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

Физически проверить каждое решение невозможно, так как их будет более 1000! (тысяча факторных) комбинаций.

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

Мы думали об алгоритме Хопкрофта-Карпа, но он не подходит - было бы хорошо, если бы была разрешена только одна ракета на город.

Буду признателен за любую помощь.

Не стесняйтесь исправлять мой английский sh.

Answer 1

Hopcroft-Karp требует только минимальных модификаций, чтобы справиться с этой проблемой.

Вы могли бы разделить каждый город на N копий, где N - количество ракет, которые он может принять чтобы каждая копия могла принять только 1 ракету. Тогда вы будете искать максимальное двудольное совпадение и можете использовать Хопкрофт-Карп.

Это, конечно, значительно увеличит размер вашей проблемы и количество решений, поскольку это не имеет значения на какую копию города вы нацеливаетесь с помощью любой ракеты, и многие совпадения, которые вы можете найти, в конечном итоге станут тем же решением, если вы объедините разделенные города.

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

1. Расширяющийся путь должен начинаться со свободной city ​​- это тот, у которого меньше текущей пропускной способности.
2. Затем он следует за неиспользуемым ребром к ракете;
3. Затем он следует за существующим ребром в город, Способность города не имеет значения, потому что;
4. Затем следует за неиспользованным фронтом к другой ракете и повторяется 3-4 по мере необходимости.

Теперь w когда вы переворачиваете края вдоль увеличивающейся траектории, только начальный город видит изменение количества ракет, нацеленных на него, поэтому вам не нужно каким-либо образом учитывать возможности городов во время поиска.

Единственная реальная разница между этим поиском и Хопкрофтом-Карпом заключается в том, что вам нужно учитывать пути, которые посещают один и тот же город (но не одну и ту же ракету) несколько раз.

Answer 2

Возможный способ - использовать алгоритм c geneti. Если есть m ракет, хромосома будет вектором значений m, каждое из которых будет целым числом в диапазоне (0, 1, ..., n). 0 - это специальное значение, которое означает «нет цели». n - это значение, которое зависит от ракеты (поскольку каждая ракета имеет свой собственный список возможных целей).

Функция максимизации (пригодность хромосомы) - это число ненулевых значений.

Однако существует проблема с скрещиванием и мутацией: они могут генерировать неверные решения (потому что городские возможности могут быть не удовлетворены). Обходной путь - применить штраф к функции пригодности.

Скажем, у нас есть город 1 с мощностью 10 и город 2 с мощностью 5. Если город 1 получает 12 ракет, а город 2 получает 8, у нас 2 + 3 = 5 дополнительных ракет. Удалите 5 * k из пригодности (k - некоторый коэффициент, который нужно будет выбрать).

Алгоритм geneti c предпочитает хромосомы с высокой приспособленностью, что означает, что он должен производить решения, которые удовлетворяют ограничениям емкости .