Каковы применения алгоритма кратчайшего пути?

Question

Кратчайший путь между узлами в графе можно найти несколькими алгоритмами (Dikstra, A-star и т. Д.).

Но в каких приложениях эта проблема? (Я знаю немало уже, но я хотел бы видеть еще много примеров).

Пожалуйста, дайте только одну заявку / ответ! Объясните приложение и как оно может быть преобразовано в проблему кратчайшего пути.

Answer 1

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

Представьте, что вы можете конвертировать 1000Долларов США до 950 евро, а затем 950 евро в 1020 канадских долларов, которые вы конвертируете обратно в 1007 долларов США :). Просто конвертируя валюту в валюту, вы можете зарабатывать деньги.

Эта ситуация называется арбитражной возможностью.Это может быть сделано с любым активом и между различными рынками.

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

Вы можете увидеть более подробную информацию с хорошим объяснением и примерами здесь: http://algs4.cs.princeton.edu/44sp/

Answer 2

Учитывая количество городов, с которыми соединяются автомагистрали, найдите кратчайший путь из Нью-Йорка в Чикаго.

Трафик и протяженность автомобильных дорог - это веса трасс.

Answer 3

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

Например, замените слово «кошка» на слово «собака», меняя одну букву за раз: «кошка», «летучая мышь», «сумка», «болото», «собака»

Answer 4

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

Answer 5

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

Answer 6

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

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

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

Answer 7

В видеоиграх эти алгоритмы часто используются для поиска кратчайшего пути между двумя точками на карте. «Поиск пути», как его называют в этом контексте, может использоваться ИИ для построения маршрутов или игровым движком для помощи пользователям в построении маршрутов.

Answer 8

Учитывая сеть компьютеров (например, одноранговое приложение), найдите кратчайший путь от машины A к машине B.

Answer 9

Кратчайший путь часто используется в SNA (Анализ социальной сети) для вычисления центральности между другими.Обычно люди с самыми сильными связями имеют тенденцию общаться по кратчайшему пути.Зная на графике кратчайший путь между людьми (узлами), вы сможете узнать скрытые сильные связи.Вы можете обнаружить много интересных вещей в графике, просто рассчитав некоторые метрики.

Answer 10