Очень доброжелательный и компетентный автор. Всегда был на связи, все разъяснил, предоставил несколько вариантов программы. Рекомендую.
Информация о работе
Подробнее о работе
Модернизация алгоритма Дейкстры поиска кратчайших путей для векторно-весовой функции
- 32 страниц
- 2017 год
- 153 просмотра
- 1 покупка
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Введение
Граф представляет собой отображение отношений внутри некоторого множества объектов, представляемых вершинами графа: наличие или отсутствие связей между ними (в первом случае они соединены друг с другом ребрами; во втором случае ребра отсутствуют), а также количественно выраженная направленность и интенсивность связей.
Универсальность такого представления структуры позволяет описывать и давать количественную оценку широкого класса задач в технических, технологических, экономических и многих других приложениях.
Например, в виде графа отображают последовательность выполняемых работ при строительстве объектов, начиная от изыскательских работ и заканчивая обустройством прилегающих территорий, маршруты транспортировок материалов, взаимосвязи этапов работ, потоки ресурсов различного рода (материальных, финансовых, трудовых, энергетических), системы учета и управления проектами в соответствии с каждым из этапов и т.д.
Несмотря на различную природу описываемых отношений, графы обладают многими общими свойствами, что позволяет использовать методы дискретной математики и, в частности, теории графов для количественного описания их общих свойств, независимо от реальных объектов, которые они представляют.
Графы используют во всех областях науки и техники, в частности при принятии решении и в задачах оптимизации, когда в пространстве всех возможных состояний системы необходимо выбрать наилучшее с позиций поставленных цели и критериев.
В теории графов задача кратчайшего пути является задачей нахождения пути между двумя вершинами (или узлами) в графе, так что минимизируется сумма весов составляющих его ребер. Это одна из наиболее классических и значимых задач упомянутой теории. К настоящему времени разработаны многие алгоритмы ее решения.
Значимость задачи о кратчайшем пути определяется ее многочисленными и продолжающимися увеличиваться практическими приложениями. Так, в GPS-навигаторах необходимо прокладывать кратчайшие маршруты в режиме реального времени для задаваемых начальной и конечной точек. При этом вершинами являются перекрестки, а дороги – ребрами, и нужно найти минимальную длину дорог на пути следования.
Задача нахождения кратчайшего пути между двумя пересечениями на дорожной карте (вершины графа соответствуют пересечениям, а ребра соответствуют сегментам дороги, каждый из которых взвешен по длине своего сегмента дороги), может быть смоделирована специальным случаем задачи кратчайшего пути на графах.
Другим примером является задача проектирования оптимальных сложных инженерных систем, имеющих пространственное (например, геоинформационное) распределение. Эти инженерные объекты (трубопроводы для транспортировки углеводородов, железные и автомобильные дороги и другие системы) требуют больших капитальных вложений и эксплуатационных затрат. Следовательно, оптимизация конфигурации сети, связывающей множество распределенных потребителей с точечными источниками, самым существенным образом отразится на снижении многих параметров проекта: его общей стоимости, капиталовложений и затрат труда и эксплуатационных издержек в течение его службы.
Если представить недетерминированную абстрактную машину как граф, где вершины описывают состояния и ребра, описывают возможные переходы, алгоритмы кратчайшего пути могут быть использованы для нахождения оптимальной последовательности выборов для достижения определенного целевого состояния или для установления нижних границ времени, необходимого для достижения заданного состояния. Например, если вершины представляют состояния головоломки как кубик Рубика, и каждое направленное ребро соответствует одному ходу или повороту, алгоритмы кратчайшего пути могут быть использованы для нахождения решения, которое использует минимально возможное количество ходов.
Другие приложения, часто изучаемые в операционных исследованиях, включают компоновку завода и объекта, робототехнику, транспорт и проектирование СБИС [2].
Проблема поиска кратчайшего пути от заданного узла до другого узла рассматривалась, традиционно, в рамках оптимизации одной цели или критерия.
Более конкретно, предполагается, что некоторое значение связано с каждой дугой (например, длиной или временем прохождения), и целью является определение допустимого пути, для которого минимизируется либо общее расстояние, либо общее время движения. Во многих реальных приложениях часто обнаруживается, что одной единственной целевой функции недостаточно, чтобы адекватно охарактеризовать проблему. В таких случаях используются многокритериальные (многоцелевые) кратчайшие пути (MOSP).
Существует множество публикаций, посвященных этим проблемам в двух наиболее часто используемых областях: компьютерных сетях (Cidon et al., 1997; 1999; Kerbache and Smith, 2000; Silva and Craveirinha, 2004) и транспортировке (Dial, 1979; Halder and Majumber, 1981 год, Рана и Виксон, 1988 год, Фуджимура, 1996 год, Модешть, 1998 год). Например, в транспортных сетях типичная ситуация, которая может быть адекватно представлена только с учетом множественных целей, связана с планированием военных маршрутов, где одновременно необходимо учитывать время, расстояние или способность маскировки на пути (Tarapata , 2003).
Таким образом, актуальность разработки и исследований алгоритма Дейкстры поиска кратчайших путей для векторно-весовой функции определяется актуальностью задач, в которых используются эти алгоритмы как инструмент оптимизации.
Целью работы является исследование алгоритма Дейкстры поиска кратчайших путей для получения Парето-оптимального решения многокритериальных задач.
Объектом исследования являются методы оптимизации многокритериальных задач.
Предметом – эффективность алгоритма Дейкстры поиска кратчайших путей для векторно-весовой функции.
Оглавление
Введение 3
1. Основные определения и понятия теории графов 7
2. Задачи многокритериальной оптимизации 10
3. Оптимальность по Слейтеру и Парето 13
4. Модифицированная задача и алгоритма Дейкстры поиска кратчайших путей для векторно-весовой функции 16
5. Вычислительная эффективность алгоритма 22
6. Пример реализации модифицированного обобщенного алгоритма Дейкстры 24
7. Методы ускорения классического алгоритма Дейкстры 29
Заключение 31
Список использованной литературы 32
Заключение
При наличии нескольких весов ребер обычно нет единого оптимального пути, так как пути имеют разные затраты в разных весах. В классическом подходе вычисляются все оптимальные по Парето пути P, т.е., где для каждого другого пути P0 имеется по меньшей мере один из реберных весов, для которых P лучше, чем P0. Говорят, что путь P доминирует над другим путем P0, если P0 не лучше в любом краевом весе. Наиболее распространенным алгоритмом для вычисления всех паретооптимальных путей является обобщение алгоритма Дейкстры (Парето-Дейкстра).
У него больше нет свойства установления узла, поскольку уже установленные узлы, возможно, придется обновлять снова, а несколько оптимальных по Парето путей к узлу представлены многомерными метками. Вычисление всех оптимальных по Парето путей, вообще говоря, NP-сложно, и на практике существует также множество оптимальных по Парето путей в дорожных сетях.
Список использованной литературы
1. Валуев А.М. Модель многокритериального выбора основных проектных решений для глубоких карьеров // Научное обозрение. 2014. №12. С. 76–80.
2. Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. М., 1978.
3. Deo, N., Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, New Jersey, 1974.
4. Ху Т. Целочисленное программирование и потоки в сетях, М.: Мир, 1974. - 520 с.
5. JOHNSON, D. E., and JOHNSON, J. E., Graph Theory with Engineering Applications, Ronald Press, New York, New York, 1972.
6. Филлипс Д.,Гарсия-Диас А. Методы анализа сетей: пер. с англ. М. Мир, 1984. — 496 с.
7. Hitchner, L. E., A Comparative Investigation of the Computational Efficiency of Shortest Path Algorithms, University of California, Berkeley, Operations Research Center, Report No. ORC 68-17, 1968.
8. Dreyyfus, S. E., An Appraisal of Some Shortest-Path Algorithms, Operations Research, Vol. 17, pp. 395-412,1969.
9. Gilsinn, J., and Witzgall, C., A Performance Comparison of Labelling Algorithms for Calculating Shortest Path Trees, National Bureau of Standards, Washington, DC, NBS Technical Note No.777, 1973.
10. Golden, B., Shortest-Path Algorithms: A Comparison, Operations Research, Vol. 24, pp. 1164-1168,1976.
11. Denardo, E., and Fox, B., Shortest-Route Methods, 1: Reaching, Pruning, and Buckets, Operations Research, Vol. 27, pp. 161-186, 1979.
12. Bloniarz, P., A Shortest-Path Algorithm with Expected Time O(n2log n log* n), SlAM Journal on Computing, Vol. 12, pp. 588-600, 1983.
13. ФордЛ.Р., Фалкерсон Д.Р. Потоки в сетях. : пер. с англ. – М.: Мир, 1966, 356с.
14. Moore, E. F., The Shortest Path through a Maze, Proceedings of the International Symposium on the Theory of Switching, Part II, pp. 285-292, 1957; Annals of the Computation Laboratory of Harvard University, Harvard University Press, Cambridge, Massachusetts, Vol. 30, 1959.
15. Bellman, R. E., On a Routing Problem, Quarterly of Applied Mathematics, Vol. 16, pp. 87-90, 1958.
16. Floyd, R. W., Algorithm 97, Shortest Path, Communications of the ACM, Vol. 5, p.345, 1962.
17. Эвристики для поиска кратчайших путей [Электронный ресурс]. – Режим доступа: http://neerc.ifmo.ru/wiki/index.php?title=Эвристики_для_поиска_кратчайших_путей. Дата обращения: 01.03.2017 г.
18. Эвристический поиск [Электронный ресурс]. – Режим доступа: http://chernykh.net/content/view/293/493/. Дата обращения: 13.03.2017 г.
19. Hart, P. A Formal Basis for the Heuristic Determination of Minimum Cost Paths / P. Hart, N. Nilsson, B. Raphael // IEEE Trans. Syst. Science and Cybernetics. – 1968. - № SSC-4(2). – C. 100-107.
20. 54 Koenig, S. Incremental Heuristic Search in Artificial Intelligence / S. Koenig, M. Likhachev, Y. Liu, D. Furcy // Artificial Intelligence Magazine. – 2004. - № 25(2). - C. 99-112.
21. Cormen, Thomas H. Introduction to Algorithms Third Edition Thomas / Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. – Ldn. : The MIT Press, 2009. – 1313 c.
22. Deo, N. Shortest-path algorithms: Taxonomy and Annotation / N. Deo, C. Pang // Networks. – 1984. - № 14. - С. 275–323.
23. Котов, А.Н. Метод минимизации суммарных затрат по развертыванию распределительных сетей на основе модифицированного метода Дейкстры [Электронный ресурс] / А.Н. Котов. – СПб. : СПбГУТ им. проф. М.А. Бонч-Бруевича, 2007. – Режим доступа: http://jurnal.org/articles/2007/radio4.html. Дата обращения: 26.03.2017 г.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
