Как можно улучшить это решение для двустороннего сопоставления?

Question

Я работаю в битвах с кодами и пытаюсь выполнить задачу busyHolidays из задач компании Instacart.

Задача содержит три массива. Shoppers содержит строки, представляющие время начала и окончания их смен. Orders содержит строки, представляющие время начала и окончания заказов, а leadTime содержит целые числа, представляющие количество минут, необходимое для выполнения задания.

Цель состоит в том, чтобы определить, могут ли заказы соответствовать покупателям так, чтобы у каждого покупателя был только один заказ, а у каждого заказа был покупатель. Заказ может быть согласован с покупателем только в том случае, если покупатель может как начать, так и завершить его в течение времени заказа.

У меня есть решение, которое проходит 19/20 тестов, но так как я не вижу последний тест, я понятия не имею, что происходит не так. Первоначально я потратил пару дней, пытаясь выучить такие алгоритмы, как Алгоритм Эдмонда и Венгерский алгоритм, но мой недостаток знаний по CS и слабость в математике немного утомили меня, и я не могу понять, как на самом деле реализовать эти методологии, поэтому я пришел к решению, которое включает взвешивание каждого узла на каждой стороне графика в соответствии с его количеством возможных соединений. Я был бы признателен, если бы кто-нибудь мог помочь мне взглянуть на мое решение и указать, где оно может испортиться, или предложить более стандартное решение проблемы таким образом, чтобы кому-то было бы легче без формального обучения алгоритмам понять , Заранее спасибо.

Я положу код в гист, так как он довольно длинный

Код: https://gist.github.com/JakeTompkins/7e1afc4722fb828f26f8f6a964774a25

Answer 1

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

Вы правильно определили это как случай проблемы с назначением. Точнее говоря, это проблема «максимального двудольного соответствия», и алгоритм Эдмондса-Карпа является наиболее простым способом ее решения (https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm)

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

1. Сделать начальное назначение
2. Попробуйте найти улучшение
3. Повторяйте, пока больше не будет найдено улучшений.

Для двустороннего сопоставления «улучшение» всегда имеет одну и ту же форму, что облегчает решение этой проблемы. Чтобы найти улучшение, вы должны найти путь, который соединяет неназначенного покупателя с неназначенным заказом, следуя этим правилам:

• Путь может идти от любого покупателя к любому заказу, который он / она может выполнить, но не
• Путь может идти из любого заказа только к покупателю, выполняющему его в текущем назначении.

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

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

PREVIOUS       PATH FOUND      IMPROVED ASSIGNMENT

    1              1                  1
                 /                  /
A              A                  A
  \              \     
    2              2                  2
                 /                  /
B              B                  B           
  \              \       
    3              3                  3
                 /                  /
C              C                  C