Самый короткий путь между узлами в графе можно найти несколькими алгоритмами (Dikstra, A-star и т. Д.).Каковы приложения алгоритма кратчайшего пути?
Но какие приложения имеет эта проблема? (Я знаю немало уже, но мне хотелось бы увидеть еще много примеров).
Пожалуйста, приложите только одно заявление/ответ! Объясните приложение и как его можно преобразовать в проблему с коротким пути.
Учитывая сеть компьютеров (например, приложение равноправных узлов ЛВС), найти кратчайший путь от машины А к машине В.
SLaks, но зачем вам нужен кратчайший путь в одноранговом приложении? – skanatek
В одноранговом приложении две машины не обязательно подключаются с использованием одного соединения. Все соединения проходят через начальный шлюз, а затем через многие промежуточные маршрутизаторы или коммутаторы, по существу формируя сеть. Здесь вы найдете кратчайший путь. –
Учитывая ряд городов с автомагистралей, соединяющих их, найти кратчайший путь от Нью-Йорка до Чикаго.
Движение и длина автомобильных дорог - это дорожные грузы.
Это также может быть использовано для различных компьютерных игр. – SLaks
В видеоиграх эти алгоритмы часто используются для нахождения кратчайшего пути между двумя точками на карте. «Pathfinding», как он называется в этом контексте, может использоваться AI для построения маршрутов или движка игры, чтобы помочь пользователям в построении маршрутов.
Один пример, который я вижу, вероятно, используется в устройствах с предварительно установленными точками, которые должны проходить через определенные точки с определенным количеством заряда аккумулятора или топлива.
В армии у нас есть некоторые небольшие беспилотные летательные аппараты/устройства, у которых есть некоторая предустановленная точка, необходимая для разведки, и поскольку она должна путешествовать на очень большие расстояния, на таком маленьком устройстве, что было бы слишком дорого попробовать для управления им через спутник, и радиоуправление ухудшилось, прежде чем достигнуть самой далекой точки. Именно здесь вступает в игру алгоритм.
Просто настройте какую-то точку, в которой вы хотите разведать разведку и отпустить ее. Позволяя ему найти кратчайший путь, пройденный, чтобы покрыть все точки. Он не требует больших инструментов, поэтому он более доступный и портативный.
Это коммивояжер, не самый короткий путь. – SLaks
ts - проблема класса sp, хотя –
Что такое «проблема класса sp»? –
Социальная сеть ... найти кратчайший путь между двумя людьми (степень разделения)
Это звучит действительно интересно! Но к чему это можно было бы привыкнуть? – BlackBear
Вы знаете, что в linkedIn, они обеспечивают, что кто-то является вашим вторым соединением или третьим соединением, там 2 является кратчайшим путем от вас к этому человеку. –
Показано, что каждый человек в Америке связан друг с другом с отношением 6: –
Кратчайшие проблемы пути образуют фундамент целого класса задач оптимизации, которые могут быть решены с помощью технологии Генерация столбцов. К примерам относится проблема маршрутизации транспортных средств, проблема проблем с сетевым дизайном, среди прочего. В таких проблемах существует основная проблема (обычно это линейная программа), в которой каждый столбец представляет собой путь (подумайте о пути в проблеме маршрутизации транспортного средства в качестве одного из возможных маршрутов, который может принять транспортное средство, подумайте о пути в сети проблема дизайна как возможный маршрут, по которому товар может быть отправлен между источником и пунктом назначения). Основная проблема неоднократно решена. Каждый раз, используя метрики решения, решается отдельная проблема (называемая подзапросом генерации столбцов). Эта проблема оказывается задачей кратчайшего пути (обычно с боковыми ограничениями или отрицательной длиной дуги, представляющей проблему NP-Hard). Если получен новый полезный путь, он добавляется к исходной основной проблеме, которая теперь решается на более широком подмножестве путей, что приводит к более качественным (более дешевым, обычно) решениям.
Спасибо, я googled «генерация столбцов» и нашел книгу на эту тему ... – ragnarius
Алгоритмы кратчайшего пути могут быть использованы для решения word ladder puzzles.
Например, изменить слово «кот» в слово «собака», изменив одну букву в то время - «кошка», «летучая мышь», «мешок», «болото», «собака»
Существует интересное, а не прямое очевидное применение алгоритмов кратчайшего пути, которые, вероятно, довольно часто используются в алгоритмическом торговом и финансовом секторе, который занимается торговыми активами и товарами.
Представьте, что вы можете конвертировать 1000 USD в 950 EUR, а затем от 950 EUR до 1020 CAD, которые вы конвертируете обратно до 1007 USD :) Просто переведя из валюты в валюту, вы можете зарабатывать деньги.
Эта ситуация называется возможностью арбитража. Это можно сделать с помощью любого актива и между различными рынками.
В этом случае отношения между активами моделируются как ориентированный кратно-взвешенный график, и нахождение так называемых отрицательных циклов на графике фактически находит эти возможности арбитража.
Вы можете увидеть больше деталей с хорошим объяснением и примерами здесь: http://algs4.cs.princeton.edu/44sp/
Самым коротким путем часто используется в СНСЕ (Social Network Analysis) для вычисления промежуточности центральности среди других. Обычно люди с самыми сильными облигациями имеют тенденцию общаться по кратчайшему пути. Зная на графике, кратчайший путь между людьми (узлами) может дать вам знать скрытые сильные связи. Вы можете обнаружить много интересного на графике, просто вычислив некоторые показатели.
Вы можете найти свой путь к дому с меньшим количеством баров и избегать его. –