Автор работы: Пользователь скрыл имя, 19 Марта 2013 в 11:56, курсовая работа
Изучены эвристический, приближенный и точный алгоритмы решения ЗК.Точные алгоритмы решения ЗК – это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.
Предложен собственный эффективный метод решения ЗК на основе по-строения выпуклого многоугольника и включения в него центральных вершин (городов).
Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора; для большого числа вершин рациональнее применять метод ветвей и границ или метод автора работы (Анищенко Сергея Александровича).
Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.
Приведены тексты программ, позволяющие решить ЗК различными методами.
Введение 3
1. Задача коммивояжера. Общее описание 5
2. Методы решения ЗК 7
2.1. Жадный алгоритм 7
2.2. Деревянный алгоритм 11
2.3. Метод ветвей и границ 16
3.Практическое применение задачи коммивояжера 17
Заключение 19
Список литературы 20
4.Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
5.В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
6.Ф. А. Новиков. Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.
7. Бодров В.И., Лазарева Т.Я., Мартемьянов Ю.Ф. Тамбов ,Методы исследования операций при принятии решений: Изд-во Тамб. гос. техн. ун-та, 2004.
8. Сырцова Е. Д. Математические методы в планировании и управлении строительным производством. Учебное пособие. М., «Высшая школа», 1972.
9. Грин Д., Кнут Д. Математические методы анализа алгоритмов. — М.: Мир, 1987.- 120 с
10.Конюховский П. В. Математические методы исследования операций в экономике—СПб: Питер, 2000.—208 с,с ил.