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

Реферат

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

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

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

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 299 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

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

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 - 2016
Рейтинг@Mail.ru