Описание используемых методов и алгоритмов - Выбор оптимального маршрута для строительства дороги
В данном пункте нужно проанализировать используемый алгоритм поиска кратчайшего пути.
Алгоритм Дейкстры
Находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса.
Смысл этого способа заключается в том, что обходятся все вершины, начиная с заданной, при этом каждой присваивается метка с некоторым значением. Затем в результат войдут те вершины, метки которых минимальны. На первом шаге исходной вершине присваивается метка со значением 0. Затем рассматриваются все следующие вершины, то есть те, в которые можно попасть из исходной. Им присваиваются метки, значение которых определяется как сумма исходника и веса пути. Из вершин следующего шага выбирается та, что имеет наименьшее значение метки, и изучаются все вершины, в которые из нее можно пройти, не используя промежуточных вершин. Определяется новое значение метки, равное метке вершины - исходника плюс вес пути. Если полученное значение меньше, чем метка вершины, то метка изменяется. В противном случае остается исходное значение. При этом в отдельном массиве, размерность которого равна количеству вершин графа, сохраняется результат оптимизации, по которому и определяется путь.
Главным достоинством алгоритма является простота реализации.
Главным недостатком - то, что по ходу выполнения функции, то есть нахождения кратчайшего пути, алгоритм не может вернуться назад, чтобы пересмотреть другие варианты.
Похожие статьи
-
В данном разделе была разработана функциональная схема работы программного комплекса, которая в общем виде описывает состав комплекса, характер и виды...
-
Обзор и анализ существующих программных решений Из доступных программных решений можно выделить пару программ. Первая программа SusaninLab 1.2 -...
-
ЗАКЛЮЧЕНИЕ, Список использованных источников - Выбор оптимального маршрута для строительства дороги
При написании программного комплекса курсовой работы использовался язык C Sharp, среда программирования - Microsoft Visual Studio. В результате были...
-
При разработке данной программы были допущены следующие синтаксические ошибки: - неправильное использование операторов присваивания; - неверное...
-
Разработаем алгоритм одного из основных методов, используемого в данной программе. Private void pictureBox1_MouseDown(objects sender, MouseEventArgs e)...
-
Определение структуры и состава программной системы В программе использованы поля данных, структуры, конструктор, а также методы. Поля данных: - public...
-
Виды контроля качества разрабатываемого ПО Тестирование программы - это этап, на котором проверяется, как ведет себя программа на как можно большем...
-
Введение - Выбор оптимального маршрута для строительства дороги
В данном курсовом проекте по дисциплине "Языки программирования" описаны алгоритмы функционирования разрабатываемой программы. Практическая часть проекта...
-
Для того, чтобы использовать симметричные алгоритмы шифрования, необходимо безопасно обменяться ключами. Протокол Диффи - Хеллмана позволяет двум и более...
-
Обоснование выбора языка и среды программирования Для реализации данного курсового проекта был выбран язык программирования Visual C#. Язык основан на...
-
Графический и пользовательский интерфейс представляет собой важную часть любой программы. От его оптимизации зависит скорость и удобство работы с...
-
Приложение, которое необходимо разработать, должно производить геометрическую реконструкцию сцены и вычисление цвета вершин модели. Для геометрической...
-
Работа алгоритма LBFS начинается с заданной вершины графа, которая в общем случае выбирается случайно. Получаемый порядок вершин также может быть основан...
-
Методы изображение алгоритмов - Алгоритм
На практике наиболее распространены следующие формы представления алгоритмов: 12. словесная (записи на естественном языке); 13. графическая (изображения...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Программная модель данных, получившая название "MapReduce", была создана несколько лет назад в компании Google, и там же была осуществлена первая...
-
Стек технологий При выборе стека технологий основное внимание уделялось следующим факторам, в порядке убывания значимости: § Кроссплатформенность; §...
-
Проектирование визуальных конструкций Вторая глава описывает процесс трансформации текстового языка JAPE в визуальный язык, который позволит описывать...
-
Ввиду того, что для языка JAPE не предусмотрен специализированный редактор, разработчики рекомендуют использовать Vim[10] или Eclipse[11], ассоциировав...
-
Описание бизнес-процессов бюджетирования в группе компаний нефтегазового сектора Одна из исследовательских задач данной работы состоит в том, чтобы...
-
В работе возникает необходимость выбора предметной области, в которой будет тестироваться каскадный классификатор. Главными вопросами на данном этапе...
-
Разработка с "нуля", Выбор метода разработки - Различные виды программ для Multi-Touch столов
Разработка приложения на каком-либо языке с нуля достаточно трудоемкий процесс, так как в случае создания интерфейсов понадобиться множество времени для...
-
Общее описание программного обеспечения, реализующего разработанный алгоритм Основной идеей дипломного проекта, является реализация алгоритма...
-
Теоретические аспекты поставленной задачи В этой части проекта будут объяснены этапы применения МКЭ для плоской фермы. В первой главе было рассмотрено...
-
Выбор среды программирования Delphi - это попытка фирмы borland объединить лучшее, что было создано на тему визуального программирования, в единый...
-
Для того, чтобы строить диаграммы в соответствии с рисунком 2.7, необходимо реализовать алгоритм соединения двух объектов линией. Для отображения линии...
-
Обоснование выбранного метода При дизайне системы согласно требованиям или при оптимизации существующей необходимо ввести модель, позволяющую не только...
-
Технические требования Техническое задание данной работы требует разработать программу для визуального редактирования HTML-кода. Программа должна быть...
-
Система мониторинга социальных сетей предоставляет исследователю возможность собрать интересующие его упоминания в социальных сетях по какой-либо...
-
Для вычисления цвета могут быть использованы различные подходы. Вычисление цвета может проводиться одновременно с геометрической реконструкцией,...
-
Для создания трехмерной реконструкции сцены или объекта необходимо создать его трехмерную модель и вычислить цвет ее вершин. Для геометрической...
-
Описание алгоритмов обучения - Функциональные модели универсального нейрокомпьютера
Все алгоритмы обучения сетей методом обратного распространения ошибки опираются на способность сети вычислять градиент функции ошибки по обучающим...
-
Информационная система (ИС) ГИБДД должна обеспечивать хранение информации об автомобилях (марка, номер кузова, номер двигателя, цвет кузова, гос. номер),...
-
Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы...
-
Можно выделить три основных метода разработки программного обеспечения: 1. Конструкторы программ (Аlgoritm2, Devel Studio, MnCreator, Game Maker и др.)....
-
Использование парадигмы ООП. Разрабатываемая АИС является системой с открытым исходным кодом и значит должна являться масштабируемой сторонними...
-
Данный алгоритм (англ. Maximal Neighborhood Search - MNS) [7] в отличие от алгоритма BFS позволяет дополнительно упорядочить вершины в найденных...
-
Для написания АИС использовались следующие языки программирования, программные средства и библиотеки: - Язык программирования PHP 5.4; -...
-
Модификации алгоритма Лемпеля-Зива, предложенная Терри Уэлчем - Анализ алгоритма Лемпеля-Зива
В 1984 году Терри Уэлч (Terry Welch) предложил адаптивный сброс словаря для алгоритма LZ78 [3]. В этом случае при заполнении словаря сброс словаря не...
-
"WWWSQLDesigner" позиционируется как абсолютно бесплатный, доступный для пользователей, универсальный веб-редактор, значительно упрощающий процесс...
Описание используемых методов и алгоритмов - Выбор оптимального маршрута для строительства дороги