Алгоритм планирования наилучшего соответствия

Question

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

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

Answer 1

Я думаю, вы должны использовать генетический алгоритм, потому что:

• Лучше всего подходит для больших проблемных случаев.
• Снижает сложность во времени по цене неточного ответа (не самый лучший)
• Вы можете легко указать ограничения и предпочтения, изменив наказания за несоблюдение правил.
• Вы можете указать срок выполнения программы.

• Качество решения зависит от того, сколько времени вы собираетесь потратить на решение программы.

  Определение генетических алгоритмов

  Учебник по генетическим алгоритмам

  Планирование класса проекта с GA

Answer 2

Есть несколько способов сделать это

Один из подходов - программирование с ограничениями. Это частный случай динамического программирования, предложенного feanor. Целесообразно использовать специализированную библиотеку, которая может выполнять функции ограничения и ветвления за вас. (Google для "gecode" или "comet-online", чтобы найти библиотеки)

Если вы склонны к математике, вы также можете использовать целочисленное программирование для решения этой проблемы. Основная идея здесь состоит в том, чтобы перевести вашу проблему в набор линейных неравенств. (Google для "планирования целочисленного программирования", чтобы найти много примеров из реальной жизни и Google для "Abacus COIN-OR" для полезной библиотеки)

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

Answer 3

Ваше описание проблемы не совсем понятно, но если все, что вы пытаетесь сделать, это найти расписание, в котором нет перекрывающихся событий, то это простая двусторонняя проверка соответствия .1004 * У вас есть два набора узлов: события и время.Нарисуйте край от каждого события к каждому возможному времени встречи.Затем можно эффективно построить сопоставление (максимально возможный набор ребер между узлами), используя расширенные пути .Это работает, потому что вы всегда можете преобразовать двудольный граф в эквивалентный потоковый граф.

Примером кода, который делает это, является BIM .Стандартные графические библиотеки, такие как GOBLIN и NetworkX , также имеют реализации двустороннего сопоставления.

Answer 4

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

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