Так что это вопрос алгоритма.Задача состоит в следующем: с учетом двух списков координат (или длины n каждого) велосипедов и людей на двумерной сетке (или двумерной сетке, показывающей положение каждого велосипеда и человека), рассчитать оптимальное соединение велосипедов илюди, так что общее расстояние Манхэттена всех пар сведены к минимуму.Гарантируется, что для каждого человека расстояние до всех велосипедов не будет одинаковым и одинаковым для всех велосипедов.
В этом вопросе есть решение , в котором говорится, что мыможет отсортировать все расстояния от низкого до высокого и соединить велосипед с человеком, если они оба непарные.Сложность, очевидно, O (n ^ 2 logn) времени и O (n ^ 2) пространства.
Итак, мои вопросы
- Это оптимальный путь и почему?Может ли кто-нибудь доказать его оптимальность?Если он не является оптимальным, каким будет оптимальный алгоритм минимизации общего расстояния?
- Как это связано с проблемой стабильного брака ?
Обновление:
В связанном вопросе используется другой критерий приоритета.Так какой же будет алгоритм, который вычисляет оптимальное спаривание, если критерии минимизируют общее расстояние Манхэттена (за исключением алгоритма грубой силы DFS, который имеет экспоненциальную сложность)?
Обновление 2:
Если критерии таковы, что ни одна пара не предпочтет друг друга, чем их текущий партнер, тогда это проблема стабильного брака.Если критерием является общая сумма расстояний, следует использовать венгерский алгоритм.