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

Question

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

Я знаю Алгоритм Дейкстры и Алгоритм Беллмана Форда , но здесь любопытно узнать о его реализации. Или это можно решить с помощью BFS (поиск в ширину) ?

Answer 1

Дополняя ответ @ jrook, обратите внимание, что «полное двухстороннее сопоставление минимального веса» («полное» или «идеальное», потому что в противном случае оптимальным решением является пустое сопоставление) также идет под именем linearзадача присваивания , просто чтобы дать вам еще несколько ключевых слов, чтобы вы начали.

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

Если вы знакомы с алгоритмами поиска кратчайшего пути и расширенного пути (например, те, которые можно использовать для максимального соответствия двухстороннего или максимального потока), тогда, возможно, самый простой для понимания алгоритм - это то, что вы сначала получите, осознав, что рассматриваемая проблема - это особый случай проблемы минимального потока затрат , которую можно решить, заменив шаг BFS наалгоритм Эдмондса - Карпа путем поиска кратчайшего пути. Более распространенным во вводных текстах является Венгерский алгоритм .

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

Answer 2

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

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

Эти примечания к лекции объясняют проблему и алгоритм.