Решение задач на тему: Деревянный алгоритм решения задачи коммивояжёра

Введение

В 1859г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил детскую головоломку, в которой предлагалось совершить "круговое путешествие" по 20 городам, расположенных в различных частях земного шара.

Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжёре. Коммивояжёр - не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими - либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжёре, если каждое из ребёр снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между рёбрами как угодно.

Задача о коммивояжёре, который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. Это одна из типичных задач, решаемых методом динамического программирования. О сложности её говорит такой факт: если городов - 4, то число возможных маршрутов равно 6, а уже при 11 городах существует более 3,5 млн. допустимых маршрутов. В общем случае, когда число городов "n" количество маршрутов равно (n-1)!. Задача заключается в поиске сокращённых способов расчёта, позволяющих отказываться от сплошного перебора возможных маршрутов.

Оглавление

- Введение

- Общая часть

- Деревянный алгоритм

- Пример

- Решение задач средствами Excel

- Алгоритм решения задачи

- Алгоритм основной программы

- Алгоритм подпрограммы

- Листинг программы Литература