Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo.
Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил детскую головоломку, в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара. Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой.Алгоритм Прима обладает тем свойством, что ребра в множестве всегда образуют единое дерево. Дерево начинается с произвольной корневой вершины R и растет до тех пор, пока не охватит все вершины. На каждом шаге к дереву добавляется легкое ребро, соединяющее дерево и отдельную вершину из оставшейся части графа. Данное правило добавляет только безопасные ребра; следовательно, по завершении алгоритма ребра образуют минимальное остовное дерево. Данная стратегия является жадной, поскольку на каждом шаге к дереву добавляется ребро, которое вносит минимально возможный вклад в общий вес.Дана полная сеть, показанная на рисунке 9. Решение: Деревянный алгоритм вначале строит остовное дерево, показанное на рисунке 10 штриховой линией, затем эйлеров цикл 1-2-1-3-4-3-5-6-5-3-1, затем тур 1-2-3-4-5-6-1 длиной 43, который показан сплошной линией на рисунке 10 Решение задачи при помощи надстройки MS Excel «Поиск решения» Программа Поиск решений - дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации С помощью этой надстройки можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине).В ходе анализа полученных результатов, приходим к выводу, что наш путь: 1-3-2-5-4-12.
План
Содержание
Введение
1. Общая часть
1.1 Деревянный алгоритм
1.2 Пример
1.3 Решение задач средствами Excel
2. Алгоритм решения задачи
2.1 Алгоритм основной программы
2.2 Алгоритм подпрограммы
2.3 Листинг программы
Литература
Введение
В 1859г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил детскую головоломку, в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара.
Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере. Коммивояжер - не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими - либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами как угодно.
Задача о коммивояжере, который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. Это одна из типичных задач, решаемых методом динамического программирования. О сложности ее говорит такой факт: если городов - 4, то число возможных маршрутов равно 6, а уже при 11 городах существует более 3,5 млн. допустимых маршрутов. В общем случае, когда число городов «n» количество маршрутов равно (n-1)!. Задача заключается в поиске сокращенных способов расчета, позволяющих отказываться от сплошного перебора возможных маршрутов.
Вывод
В ходе анализа полученных результатов, приходим к выводу, что наш путь: 1-3-2-5-4-1
Расстояние = 27
Список литературы
1) В.П.Агальцов, И.В.Волдайская. - Математические методы в программировании.
Размещено на
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
