"Космический извозчик" - разбор и решение олимпиадной задачи по программированию
Рассмотрение возможности применения инженерных подходов к решению олимпиадных задач по программированию. Анализ условий графовой задачи по нахождению кратчайшего пути (задача "Космический извозчик"). Алгоритм поиска кратчайшего пути по заданному графу.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 29.01.2019 |
| Размер файла | 779,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Подобные документы
Задача о кратчайшем пути как одна из важнейших классических задач теории графов. Общий обзор трех наиболее популярных алгоритмов для решения задачи о кратчайшем пути. Написание программы, которая реализует алгоритм Дейкстры и алгоритм Форда-Беллмана.
курсовая работа [2,1 M], добавлен 23.06.2014Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов.
курсовая работа [43,8 K], добавлен 19.10.2010Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Проверка работоспособности программы на тестовых примерах.
реферат [929,8 K], добавлен 23.09.2013Принципы и подходы к динамическому программированию, сферы его использования, приемы и принципы. Решение задачи теста для написания и отладки программы, используемые входные и выходные данные. Тестирование заданной программы и инструкция пользователя.
курсовая работа [2,3 M], добавлен 19.03.2015Разработка, макетирование и реализация экспертной системы для решения задачи о коммивояжере, используя возможности языка Prolog. Составление графа "Карта Саратовской области" и решение проблемы поиска кратчайшего пути между двумя пунктами на карте.
курсовая работа [366,4 K], добавлен 12.05.2009Алгоритм поиска по первому наилучшему совпадению на графе. Основные классы для поиска пути в лабиринте. Тестирование нахождения кратчайшего пути в лабиринте. Порядок обхода вершин. Тестирование поведения программы при отсутствии пути в лабиринте.
курсовая работа [888,7 K], добавлен 19.12.2013Математическая постановка задачи. Обоснование выбора средств разработки. Входные и выходные данные работы программы. Решение задачи теста для написания и отладки программы. Описание программных модулей. Разработка алгоритма, анализ полученных результатов.
курсовая работа [2,2 M], добавлен 13.12.2015Исследование методов решения задачи о ходе коня. Описание алгоритмов для итеративной и рекурсивной программ. Генерация перестановок элементов по индексам. Построение эйлерова цикла на графе. Поиск кратчайшего пути на графе. Программная реализация задачи.
курсовая работа [411,6 K], добавлен 25.04.2013Разработка программы в среде Delphi для нахождения кратчайшего пути между стартом, лежащим в одной из вершин многоугольника, и финишем, находящимся на одной из сторон. Установка опорных точек, контроль целостности вводимых данных, методы решения задачи.
курсовая работа [778,8 K], добавлен 19.10.2010Разработка в среде Delphi программы "Поиск кратчайшего пути", которая создает лабиринт, находит кратчайший путь его прохождения и отображает его. Структура данных задачи и методы ее решения. Общая схема организации и взаимодействия модулей, их описание.
курсовая работа [86,5 K], добавлен 19.10.2010Описание алгоритма сортировки с двоичным включением, выбор структур данных. Пример сортировки массива, отсортированного случайным образом. Алгоритм покрытия по методу "Построение одного кратчайшего покрытия". Волновой алгоритм поиска длиннейшего пути.
курсовая работа [78,2 K], добавлен 24.09.2010Математическая модель решения задачи коммивояжера. Поиск кратчайшего замкнутого пути обхода нескольких городов и возвращения в исходную точку. Описание программы и результатов ее тестирования. Основная форма программы после вывода конечных данных.
курсовая работа [603,3 K], добавлен 21.10.2012Представление задач в виде графов AND/OR, примеры. Задача с ханойской башней. Формулировка процесса игры в виде графа. Основные процедуры поиска по заданному критерию. Эвристические оценки и алгоритм поиска. Пример отношений с определением задачи.
лекция [154,6 K], добавлен 17.10.2013Выбор инструментальной среды разработки программного обеспечения системы. Алгоритм создания теста и ввода его исходных данных. Анализ экономической эффективности применения программного обеспечения "Тестирования знаний обучающихся программированию".
дипломная работа [3,2 M], добавлен 11.09.2014Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
реферат [39,6 K], добавлен 06.03.2010Задача нахождения кратчайшего покрытия булевой матрицы. Алгоритмы поиска кратчайших покрытий методом Патрика и методом Закревского. Метод предварительного редуцирования булевой матрицы. Описание программы "Нахождение кратчайшего покрытия булевых матриц".
курсовая работа [884,1 K], добавлен 12.12.2010Разработка приложения в среде Delphi для нахождения кратчайшего пути передвижения короля по заданному полю, соединяющего два заданных поля доски. Разработка и поиск алгоритма решения задачи, спецификация исходных данных и функций, тестирование программы.
курсовая работа [358,5 K], добавлен 19.10.2010Графы: определения, примеры, способы изображения. Смежные вершины и рёбра. Путь в ориентированном и взвешенном графе. Матрица смежности и иерархический список. Алгоритм Дейкстры - алгоритм поиска кратчайших путей в графе. Работа в программе "ProGraph".
презентация [383,8 K], добавлен 27.03.2011Алгоритмы нахождения кратчайшего пути: анализ при помощи математических объектов - графов. Оптимальный маршрут между двумя вершинами (алгоритм Декстры), всеми парами вершин (алгоритм Флойда), k-оптимальных маршрутов между двумя вершинами (алгоритм Йена).
курсовая работа [569,6 K], добавлен 16.01.2012
