Содержание Введение 1. Задача коммивояжера 1. Общее описание 2. Методы решения задачи коммивояжера 1. Жадный алгоритм. 2. Деревянный алгоритм 3. Метод ветвей и границ 4. Алгоритм Дейкстры 1.2.5. Мой метод решения задачи коммивояжера 6. Анализ методов решения задачи коммивояжера 3. Практическое применение задачи коммивояжера Выводы Литература Приложения Введение Комбинаторика раздел математики, посвящнный решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.
Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбинаторных конфигураций. Это изучение включает в себя вопросы существования комбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задач перечисления, в частности определение числа конфигураций данного класса.
Простейшим примером комбинаторных конфигураций являются перестановки, сочетания и размещения. Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем диссертация Комбинаторное искусство , Я. Бернулли работа Искусство предположений , Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейб-ница комбинаторные методы выделились в самостоятельную часть математики.
В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций методу производящих функций. Возвращение интереса к комбинаторному анализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам.
Классические комбинаторные задачи это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок. В 1859 г. У. Гамильтон придумал игру Кругосветное путешествие, состоящую в отыскании такого пути, проходящего через все вершины города, пункты назначения графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную.
Пути, обладающие таким свойством, называются гамильтоновыми циклами. Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем. 1. Задача коммивояжера 1.
о тогда fAn-11nе ак что fAfB1nе .е. В силу связности исходного графа G, G и G имеют хоть одну общую вершин... Нужно двигаться по перестановке справа налево, пока впервые не увидим ... Если в ней удастся построить правильную систему подчеркнутых элементов... 7 нужно вычеркнуть из матрицы C1,2 еще строку 3 и столбец 1, получив м...
Задача о производстве красок. Имеется производственная линия для произ... Всю производственную линию будем считать одним процессором Будем счита... Дыропробивной пресс производит большое число одинаковых панелей металл... Диск может вращаться одинаково в двух направлениях координата вращения... Проделать то же самое по оси y, затратив время ti, jy 3.
Выводы 1. Изучены эвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмы решения ЗК это полный перебор или усовершенствованный перебор.
Оба они, особенно первый, не эффективны при большом числе вершин графа. 2. Предложен собственный эффективный метод решения ЗК на основе построения выпуклого многоугольника и включения в него центральных вершин городов. 3. Проведн анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия для малого числа вершин можно использовать точный метод лексического перебора для большого числа вершин рациональнее применять метод ветвей и границ или метод автора работы Анищенко Сергея Александровича. 4. Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК. 5. Приведены тексты программ, позволяющие решить ЗК различными методами.
Литература 1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома М Мир , 1965, 174 с. 2. В. П. Сигорский. Математический аппарат инженера К Технка , 1975, 768 с. 3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко.
Математическое программирование учебное пособие. 2-е изд. перераб. и доп М. Высшая школа, 1980, 300 с ил. 4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. М Наука, 1979, 345 с. 5. Е. П. Липатов. Теория графов и е применения М Знание, 1986, 32 с. 6. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. Харьков, Фолио Ростов на Дону, Феникс, 1998, 368 с. 7. Ф. А. Новиков Дискретная математика для программистов Санкт-Петербург, Питер, 2001, 304 с ил. 8. Приложения.