Недавно я наткнулся на случай в интервью, когда случай использования, который был попрошен для решения, относится к проблеме коммивояжера/проблеме маршрутизации транспортных средств. Я смог рассказать им, что представляет собой настоящая проблема, и какие математики участвуют в этой проблеме. Я объяснил, как нижеприведенный вариант использования также можно решить с помощью парадигмы MapReduce в Hadoop. (объясняется, как несколько сокращений заданий на карте могут решить проблему), используя алгоритм Graph, упомянутый в этой книге "Интенсивная обработка текста с помощью MapReduce" Джимми Лин и Крис Дайер.
Из любопытства я провел некоторое исследование в google, и я вижу, что для этой проблемы в разных вариантах сделано много исследований и исследований. Задача, о которой я спрашивал, имеет координаты города, упомянутого в (x, y) формате, и многие решения, которые я видел в google, рассматривают некоторые другие факторы, такие как дистанция единицы измерения, отрицательные/позитивные единицы измерения и так далее. Поэтому, короче, я занимался исследованиями и чтением, и я стал более смущенным.
Мой вопрос здесь для нижеследующего варианта использования, какие могут быть возможные решения, и что будет лучшим решением среди них. Если какой-нибудь опытный человек может поставить на него какие-то огни, будет полезно очистить мое замешательство и лучше понять решение. или если кто-то может направить меня в правильном направлении (чтобы я больше не путал изучение всего океана решений)
Случай использования, заданный в интервью:
Компания пытается найти оптимальное оптимальное решение для обслуживания своей клиентской базы в 300 человек с 12 сотрудниками. Они хотят, чтобы технологическое решение подсказывало, как они смогут удовлетворять требования клиентов по мере роста бизнеса, а также другие изменения, такие как местоположение изменений клиентов, новые местоположения и т.д.
Проблема в основном представляет собой проблему с проблемой коммутирующего коммивояжера (TSP) или маршрутизации транспортного средства (VSP). Следующие вещи должны быть завершены здесь.
Начальные координаты (0,0) и пример городских координат приведены ниже. Вот координаты, с которыми ожидаемое рабочее решение предоставляется в текстовом файле как вход:
X coordinate Y Coordinate
420 278
421 40
29 178
350 47
298 201
417 186
378 134
447 239
42 114
45 199
362 195
381 243
429 1
338 209
176 9
364 26
326 182
500 129
190 51
489 103
368 142
132 260
305 200
446 137
375 154
440 190
9 118
437 32
383 266
Что может быть правильным способом справиться с этой NP-трудной проблемой или если не правильно каким образом могут быть разные подходы со своими плюсами и минусами.
Поскольку его большая проблема, основанная на анализе, может быть видной визуализации чтобы решить эту проблему. Как некоторый график или использование R/аналитических инструментов
Сообщите мне, если вам нужна дополнительная информация, или если вы можете предложить, где я могу читать и понимать больше.
Заранее спасибо
Нет правильного пути решения проблемы NP. Поскольку сложность экспоненциальна, это займет очень много времени для чего-то другого, кроме тривиальных примеров.
Однако существуют приближения, которые могут приблизиться к реальному ответу и могут быть достаточно хороши для вашего приложения (как, впрочем, это не самый короткий путь, но он находится в пределах некоторого относительного диапазона).
Ознакомьтесь с нашей страницей wikipedia. У них даже есть несколько примеров.
Если бы я задал этот вопрос на собеседовании - я предложу что-то вроде описанного в этом paper, выглядит как наилучшее совпадение для вашей задачи рецептура. В этой статье вы найдете оптимизированный приблизительный подход для решения проблемы нескольких продавцов со всеми продавцами, начиная с одной точки. Это может быть принято, если мы знаем, где сотрудники уходят, решая каждую задачу подпрограммы каждого коммерческого продавца (кластеризация делит основную проблему на классические проблемы) с началом в конкретном домашнем/домашнем офисе продавца.
Если у нас есть график мест как входных данных, а не только координаты - мы можем заменить k-средства алгоритмом кластеризации графа, например MCL.
В самом деле, как упоминает Дмитрий, это случай многолетней продавщицы. Естественно, что NP-hard собеседники ищут вам алгоритм оптимизации алгоритма.
Я думаю, что ключ в этом случае - это поиск алгоритма, который способен обновлять в реальном времени изменения количества и местоположения пунктов назначения. Ant colony optimisaiton (форма оптимизации роя частиц) была изначально сформулирована для проблемы коммивояжера, см. статью и википедию:
https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms
"М. Дориго, В. Маниццо и А. Колони, система Ant: оптимизация колонией взаимодействующих агентов, транзакции IEEE по системам, человеку и кибернетике - часть B, том 26, номер 1, страницы 29-41, 1996."
Это было обобщено, так как к проблеме множественного перемещения салмана см., например, эту статью (opensource) для некоторой хорошей работы в ней:
В ситуации с интервью я бы подробно остановился на том, что Плюсы: 1. эффективное эвристическое решение; 2. Возможность обновления в реальном времени обеих изменений в графике; 3. Для бонусных очков я упоминаю, что, как только разумно эффективное решение было получено в silico, самим драйверам можно было бы назначить маршруты немного вероятным образом, впоследствии можно было бы оптимизировать, управляемые реальными данными.
Минусы состоят в том, что разумно большие объемы мощности, вероятно, потребуются по сравнению с проблемами, которые сначала уменьшают пространство поиска, как предложил Дмитрий. Во-вторых, если они хотят, чтобы вы на самом деле составляли alogirthm, это могло бы быть довольно сложным в пространстве интервью.
Интересный вопрос:)
Я не эксперт, но вы не могли бы просто рассчитать расстояние между началом и всеми остальными точками и найти ближайшую точку, а затем повторить процесс для этой точки, пока не накроете каждую точку?