Слободской государственный колледж педагогики и социальных отношений

Практическая работа №10

Специальность: 230115 Программирование в компьютерных системах.

Дисциплина: Теория алгоритмов.

Тема: Создание алгоритма решения задачи коммивояжера.

Цель работы:

1. Изучить приближенные алгоритмы решения задач

2. Решить задачу коммивояжера.

Ход работы

Теория

Задача коммивояжера была поставлена в 1934 году. Ее сущность заключается в поиске

оптимального маршрута движения при необходимости посетить все запланированные

объекты с наименьшими финансовыми и временными издержками. Как правило, речь

идет о простом перемещении по заданным точкам, либо с перевозкой груза небольшого

формата на транспортном средстве.

Задача коммивояжера является одной из знаменитых задач теории комбинаторики и

пользуется популярностью благодаря тому, что к ней сводится большое количество

практических задач.

Среди современных практических приложений задачи можно выделить: доставку

продуктов в магазин со склада, работу почтальона по разноске корреспонденции,

мониторинг объектов (нефтяные вышки, базовые станции сотовых операторов),

изготовление отверстий на специализированном станке.

Для решения задачи коммивояжера используют различные группы простейших методов:

полный и случайный перебор, жадный и деревянный алгоритмы, метод имитации отжига.

Широкое применение получили различные модификации более эффективных методов,

таких как метод ветвей и границ, генетических алгоритмов, а также алгоритм муравьиных колоний.

Задачи

1. Задача. Монетная система некоторого государства состоит из монет достоинством
a₁ = 1 < a₂ <... < a_n. Требуется выдать сумму S наименьшим возможным количеством монет.

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства a_n:. Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.

Решить задачу получения денежной суммы с помощью жадного алгоритма в Паскале

Проверить решение на примере получения суммы в 10 копеек монетами в 1, 5 и 6 коп.

(Ответ 6 коп. — 1 шт., 1 коп. — 4 шт.)

Является ли это решение оптимальным или можно получить сумму 10 копеек меньшим числом монет.

Проверить жадный алгоритм для реальной российской монетной системы.

2. Задача. (Задача коммивояжера)

«Сотруднику компании ООО «Новые технологии» Петрову Н.И. необходимо обновить

программный продукт автоматизированного учета в пяти организациях: А, Б, В, Г и Д. Он решил начать свой обход с организации «А», так как она находится на первом этаже дома, в котором проживает Петров. Сотруднику необходимо, спланировать свой маршрут таким образом, чтобы к концу рабочего дня обойти все организации в определенном порядке и выполнив свою работу, вернутся домой (в пункт «А»). В каком порядке Петрову следует обходить организации, чтобы его замкнутый тур был кратчайшим? Если расстояния между каждой парой организаций заданы следующей квадратной матрицей (5x5):

	¥
		¥
			¥
				¥
					¥

Содержание отчета:

Выписать в тетрадь практических работ название, цель работы и решения выполненных задач. Сделать вывод к работе:

1. Значимость решения задачи коммивояжера

2. Методы ее решения.

3. Какое практическое применение имеет задача о коммивояжере?

Критерии оценок:

«5» - выполнено 2 пункта.

«4» - выполнено 2 пункта, решение 2 задачи неполное.

«3» - выполнено решение 1 задачи, описание 2 задач

«2» - не выполнено решение ни одной задачи полностью.

Литература.

1. Семакин, И.Г. Основы алгоритмизации и программирования. Практикум [Текст]: учеб. пособие / И.Г. Семакин, А.П. Шестаков. - М.:Изд. центр «Академия», 2013-144с.

2. Википедия https://ru.wikipedia.org