Задача коммивояжера

  • Просмотров 8041
  • Скачиваний 634
  • Размер файла 176
    Кб

Содержание Введение 1. Задача коммивояжера 1.1. Общее описание 1.2. Методы решения задачи коммивояжера 1.2.1. Жадный алгоритм. 1.2.2. Деревянный алгоритм 1.2.3. Метод ветвей и границ 1.2.4. Алгоритм Дейкстры 1.2.5. Мой метод решения задачи коммивояжера 1.2.6. Анализ методов решения задачи коммивояжера 1.3. Практическое применение задачи коммивояжера Выводы Литература Приложения Введение   Комбинаторика – раздел математики, посвящённый

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

комбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задач перечисления, в частности определение числа конфигураций данного класса. Простейшим примером комбинаторных конфигураций являются перестановки, сочетания и размещения. Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (диссертация «Комбинаторное искусство»), Я. Бернулли (работа

«Искусство предположений»), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейб-ница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций – методу производящих функций. Возвращение интереса к комбинаторному анализу относится

к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам. Классические комбинаторные задачи – это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок. В 1859 г. У.