Проблема с назначением

• Определение и основные свойства задачи о назначении

  • Задача о назначении — это проблема поиска оптимального распределения ресурсов между множествами. 
  • Задача имеет множество приложений в экономике, информатике и других областях. 
  • Существует несколько вариантов задачи, включая задачу о сбалансированном и несбалансированном назначении. 

• Сложность задачи о назначении

  • Сложность задачи зависит от структуры графа и может быть решена за полиномиальное время для некоторых графов. 
  • Для графов с n вершинами и m ребрами существует алгоритм с временем выполнения O(m + n log n). 

• Сбалансированное назначение

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

• Несбалансированное назначение

  • В задаче о несбалансированном назначении большая часть графа имеет n вершин, а меньшая — r<n вершин. 
  • Существует метод удвоения для решения задачи, который требует добавления новых ребер, но не увеличивает скорость. 

• Решение с помощью линейного программирования

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

• Обобщение задачи о назначении

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