Реферат: Задача коммивояжера - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 299 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

23 Содержание Введение 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 г . У . Гамильтон придумал игру “Кругосветное путешествие” , состоящую в отыскании такого пути , проходящего через все вершины (города , пункты назначения ) графа , изображенного на рис . 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути , обладающие таким свойством , называются гамильтоновыми циклами . Задача о гамильтоновых циклах в графе получила различные обобщения . Одно из этих обобщений – задача коммивояжера , имеющая ряд применений в исследовании операций , в частности при решении некоторых транспортных проблем. 1. Задача коммивояжера 1.1. Общее описание Задача коммивояжера (в дальнейшем сокращённо - ЗК ) является одной из знаменитых задач теории комбинаторики . Она была поставлена в 1934 году , и об неё , как об Великую теорему Ферма обламывали зубы лучшие математики . В своей области (оптимизации дискретных задач ) ЗК служит своеобразным полигоном , на котором испытываются всё новые методы. Постановка задачи следующая. Коммивояжер (бродячий торговец ) должен выйти из первого города , посе тить по разу в неизвестном порядке города 2,1,3.. n и вернуться в первый город . Расстояния между городами известны . В каком порядке следует обходить города , чтобы замкнутый путь (тур ) коммивояжера был кратчайшим ? Чтобы привести задачу к научному виду , введё м некоторые термины . Итак , города перенумерованы числами j Т =(1,2,3.. n ). Тур коммивояжера может быть описан циклической перестановкой t =( j 1 , j 2 ,.., j n , j 1 ), причём все j 1 .. j n – разные номера ; повторяющийся в начале и в конце j 1 , показывает , что перестановка зациклена . Расстояния между парами вершин С ij образуют матрицу С . Задача состоит в том , чтобы найти такой тур t , чтобы минимизировать функционал Относительно математизированной формулировки ЗК уместно сделать два замечания. Во-первых , в постановке С ij означали расстояния , поэтому они должны быть неотрицательными , т.е . для всех j Т : С ij 0 ; C jj =
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Колумб, закрой Америку!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по математике "Задача коммивояжера", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru