Кратчайшие пути. Алгоритмы их нахождения
Алгоритмы нахождения кратчайшего пути: анализ при помощи математических объектов - графов. Оптимальный маршрут между двумя вершинами (алгоритм Декстры), всеми парами вершин (алгоритм Флойда), k-оптимальных маршрутов между двумя вершинами (алгоритм Йена).
Подобные документы
Применения языка логического программирования Пролог и языка программирования Haskell для реализации алгоритма поиска оптимального каркаса графа. Алгоритм Прима, преимущество перед другими алгоритмами нахождения оптимального каркаса, близких к полным.
курсовая работа, добавлен 13.06.2012Графы: определения, примеры, способы изображения. Смежные вершины и рёбра. Путь в ориентированном и взвешенном графе. Матрица смежности и иерархический список. Алгоритм Дейкстры - алгоритм поиска кратчайших путей в графе. Работа в программе "ProGraph".
презентация, добавлен 27.03.2011Алгоритм и программа вычисления функции на параллельной структуре. Разложение функции в ряд Маклорена. Однопроцессорный и многопроцессорный алгоритмы решения. Программа на Паскале. Размер буферной памяти между звеньями. Матрица вероятностных переходов.
контрольная работа, добавлен 14.02.2009Многоблочный метод решения сложных задач. Программирование параллельных ЭВМ. Алгоритм сокращения критического пути (CPR). Упаковка в контейнеры. Алгоритмы EVAH. Общая архитектура разработанного средства. Первоначальные предложения по отображению.
дипломная работа, добавлен 15.10.2010Использование информационных технологий для планирования размещения оптимальных точек водоснабжения, используя теорию графов. Функциональные возможности разрабатываемого приложения. Программная реализация основных модулей на основе алгоритма Флойда.
курсовая работа, добавлен 31.01.2012Энтропия и количество информации. Комбинаторная, вероятностная и алгоритмическая оценка количества информации. Моделирование и кодирование. Некоторые алгоритмы сжатия данных. Алгоритм арифметического кодирования. Приращаемая передача и получение.
курсовая работа, добавлен 28.07.2009Модификация алгоритма RPC таким образом, чтобы он не требовал входного параметра, но сохранил свою гибкость при решении задачи нахождения максимальной клики для разных графов. Метод ветвей и границ. Построение функции-классификатора. Листинг алгоритма.
курсовая работа, добавлен 06.10.2016Задача нахождения кратчайшего покрытия булевой матрицы. Алгоритмы поиска кратчайших покрытий методом Патрика и методом Закревского. Метод предварительного редуцирования булевой матрицы. Описание программы "Нахождение кратчайшего покрытия булевых матриц".
курсовая работа, добавлен 12.12.2010Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.
курсовая работа, добавлен 22.03.2012Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Представление графов в ЭВМ. Составление алгоритм Краскала с использованием графов с оперделением оптимального пути прокладки телефонного кабеля в каждый из 8 городов.
курсовая работа, добавлен 23.12.2009Значение сетевых структур в системах искусственного интеллекта, их применение для построения семантических сетей, фреймов и других логических конструкций. Составление программного кода на языке программирования Pascal, тестирование с ручном просчетом.
курсовая работа, добавлен 31.07.2010Алгоритмы, алфавит языка, структура программы, написанной на Турбо Паскале. Целые, вещественные, логические, символьные типы данных, их совместимость. Линейные алгоритмы, пустой и составной операторы, простейший ввод и вывод, разветвляющиеся алгоритмы.
курсовая работа, добавлен 03.11.2009Генератор псевдослучайной последовательности в системах защиты информации. Шифрование мультимедийных данных. Вероятностное шифрование и алгоритм Эль-Гамаля. Основные понятия теории конечных полей. Алгоритм нахождения циклического избыточного кода.
дипломная работа, добавлен 19.07.2013Алгоритм решения функциональной задачи. Выбор системы команд специализированной ЭВМ. Форматы команд и операндов. Содержательные графы микропрограмм операций АЛУ. Разработка объединенной микропрограммы работы АЛУ. Закодированные алгоритмы микропрограмм.
курсовая работа, добавлен 17.11.2010Теоретические сведения. Основные понятия. Строка, её длина, подстрока. Понятие о сложности алгоритма. Алгоритмы основанные на методе последовательного поиска. Алгоритмы Рабина, Кнута - Морриса - Пратта, Бойера – Мура.
курсовая работа, добавлен 13.06.2007Универсальная подпрограмма по записи элементов и атрибутов из таблицы XML в различные массивы, в зависимости от раздела. Алгоритм трехмерной визуализации. Классы разбора таблицы XML по элементам и атрибутам. Алгоритмы работы с двухмерными объектами.
дипломная работа, добавлен 06.03.2013Создание компьютерных программ. Сравнение C# с другими языками программирования. Решение задач транспортной логистики. Теория графов и структуры данных. Алгоритмы поиска маршрутов в графе. Выбор среды разработки. Редактирование транспортной сети.
курсовая работа, добавлен 08.10.2015- 43. Алгоритмы поиска
Поиск в массивах и списках, ключ и произвольные данные. Линейный (последовательный) поиск. Бинарный поиск в упорядоченном массиве. Алгоритм Рабина-Карпа, простая и улучшенная хэш-функция. Алгоритм Бойера-Мура со сдвигом по стоп-символам и по суффиксам.
презентация, добавлен 19.10.2014 Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.
курсовая работа, добавлен 24.10.2012Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo.
курсовая работа, добавлен 04.04.2015Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ.
презентация, добавлен 19.10.2014Способ улучшения сжатия файлов формата DjVu. Общая схема алгоритма классификации букв. Основной алгоритм сравнения пары букв. Быстрый отказ для пары разных букв. Дерево разрезов. Получение монохромных изображений. Алгоритм для устранения мусора.
курсовая работа, добавлен 28.10.2008Составление структурных программ для решения практических задач по теме "Целочисленная арифметика". Алгоритм нахождения делителей натурального числа, алгоритм проверки простое ли число, алгоритм Решета Эратосфена. Система программирования Free Pascal.
разработка урока, добавлен 03.09.2014Математические графы, области их применения. Способы раскраски вершин и ребер графов, задачи на их применение. Разработка алгоритма, работающего на основе операций с матрицей смежности. Описание логической структуры программы. Пример зарисовки графа.
курсовая работа, добавлен 27.01.2013Практическое использование алгоритмов для нахождения минимального пути в лабиринте. Разработка программы на языке С++ и в среде Visual C++. Основные способы поиска пути: метод волны и приоритетов. Описание разработанных функций и инструкция пользователя.
дипломная работа, добавлен 16.03.2012