.RU

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

Министерство образования и науки РФ

Государственное образовательное учреждение высшего профессионального образования

АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

(ГОУВПО «АмГУ»)

Факультет математики и информатики

Кафедра математического анализа и моделирования

КУРСОВАЯ РАБОТА

на тему: «Задача о коммивояжере и ее обобщения »

по дисциплине «Вариационное исчисление и методы оптимизации»


СОДЕРЖАНИЕ

Введение

1 Постановка задачи

2 Эвристические методы

2.1 Алгоритм Борувки

2.2 Алгоритм Крускала

2.3 Алгоритм Прима

2.4 Вывод

3 Генетический алгоритм

4 NP-полная задача

5 Метод ветвей и границ

6 Практическое применение задачи коммивояжер

Заключение

Библиографический список


ВВЕДЕНИЕ

В 1859 г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил детскую головоломку, в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара.

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

Задача о коммивояжере относится к классу NP-трудных задач. Методы решения задачи о коммивояжере различны. В данной курсовой кратко рассказывается только о некоторых наиболее известных.

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

И наиболее удобным мне кажется метод ветвей и границ. Его можно применять и при большом количестве городов.


1. ПОСТАНОВКА ЗАДАЧИ


vopros-1-planirovanie-semejnogo-byudzheta-uchebnoe-posobie-s-e-markuckaya-e-a-kackova-m-izdatelstvo-ekzamen.html
vopros-159-obyazannosti-i-prava-rabotnikov-v-sfere-trudovih-otnoshenij-kurs-lekcii-dlya-rukovoditelej-i-specialistov-sluzhb-ohrani-truda.html
vopros-2-svoeobrazie-rimskogo-teatra-bitovaya-komediya-palliata-grecheskaya-literatura-vopros-antich-rabovlad-obsh-polis.html
vopros-9-teatralnaya-reforma-ks-stanislavskogo-i-vi-nemirovicha-danchenko-akter-shkoli-stanislavskogo-v-spektaklyah-mht.html
vopros-dnya-komsomolskaya-pravda-14012006-4-str-3-tv-12-pervij-kanal-novosti-14-01-2006-kriskevich.html
vopros-doveriya-4-zhiznennie-pozicii-druzya-voprosi-dlya-obsuzhdeniya-principa-uvelichitelnogo-stekla.html
  • universitet.bystrickaya.ru/trekbol-trackball-konspekt-lekcij-lekciya-1-vvedenie-v-mashinnuyu-grafiku-osnovnie-napravleniya-kompyuternoj-grafiki.html
  • zadachi.bystrickaya.ru/plenarnoe-zasedanie.html
  • esse.bystrickaya.ru/rashodi-po-obichnim-vidam-deyatelnosti-ezhekvartalnijotche-t-emitenta-emissionnih-cennih-bumag-za-2-kvartal-2006-g.html
  • textbook.bystrickaya.ru/iii3-transportnaya-infrastruktura-ooo-ekspertno-konstruktorskoe-byuro-pri-tulgu.html
  • universitet.bystrickaya.ru/uchebnie-plani-9-h-klassov-fbup-2004-poyasnitelnaya-zapiska-k-uchebnim-planam-mou-gimnazii-32-g-kaliningrada.html
  • reading.bystrickaya.ru/konkurs-organizuet-i-provodit-upravlenie-socialnogo-razvitiya-administracii-municipalnogo-obrazovaniya-gorod-novodvinsk.html
  • diploma.bystrickaya.ru/vliyanie-masonskih-idej-na-razvitie-otechestvennoj-zhurnalistiki-chast-10.html
  • ekzamen.bystrickaya.ru/sostoyanie-zdorovya-pyatiklassnikov-publichnij-otchet-municipalnogo-obsheobrazovatelnogo-uchrezhdeniya-gimnaziya-3-g-belgoroda.html
  • school.bystrickaya.ru/lyuis-kerol.html
  • literature.bystrickaya.ru/dogovornaya-teoriya-vozniknoveniya-gosudarstva-i-prava-chast-7.html
  • shkola.bystrickaya.ru/osnovnaya-obrazovatelnaya-programma-nachalnogo-obshego-obrazovaniya-mou-stolbishenskoj-sosh-stranica-4.html
  • uchit.bystrickaya.ru/srednegorya-stranica-3.html
  • tests.bystrickaya.ru/lgotnikam-govoryashie-termometri-155-mlrd-rublej-ot-bankov-ria-novosti-rbk-gazeta-idr-10-12-2009.html
  • testyi.bystrickaya.ru/azastan-respublikasini-ebek-kodeksi.html
  • lesson.bystrickaya.ru/organizaciya-skladskogo-hozyajstva-na-otdelnom-predpriyatii-i-napravleniya-eyo-sovershenstvovaniya.html
  • tasks.bystrickaya.ru/33-vidi-marketingovih-kommunikacij-markov-aleksandr-petrovich.html
  • studies.bystrickaya.ru/legalizaciya-operativno-rozisknoj-informacii-pri-formirovanii-dokazatelstv-po-delam-svyazannim-s-nezakonnim.html
  • thesis.bystrickaya.ru/pravovoe-regulirovanie-zemelnih-otnoshenij.html
  • abstract.bystrickaya.ru/-otdel-vtoroj-mneniya-i-verovaniya-tolpi-kniga-1-psihologiya-narodov.html
  • tasks.bystrickaya.ru/2-5-formirovanie-predmetnih-kompetentnostej-v-obuchenii-fizike-programma-razvitiya-innovacionnih-processov-v-obrazovanii.html
  • abstract.bystrickaya.ru/3-rasprostranenie-tehnicheskih-znanij-v-rossiiv-xix-nachale-xx-vv-kak-predposilka-razvitiya-filosofii-tehniki-v-roscii.html
  • pisat.bystrickaya.ru/trifonov-a-ne-mogu-skazat-chto-ya-silno-obradovalsya1-chto-proishodit-na-sovremennih-birzhevih-ploshadkah-vo-vremya.html
  • writing.bystrickaya.ru/1-ne-sprashivajte-razresheniya-vashih-redaktorov-na-provedenie-sociologicheskogo-issledovaniya.html
  • bukva.bystrickaya.ru/rekomendacii-po-oformleniyu-stendovogo-soobsheniya.html
  • exchangerate.bystrickaya.ru/51-sostoyanie-sistemi-upravleniya-kachestvom-na-fakultete-otchet-o-rezultatah-samoobsledovaniya-fakulteta-politicheskih.html
  • teacher.bystrickaya.ru/evropejskij-sud-po-pravam-cheloveka-bolshaya-palata-delo-kononov-kononov-protiv-latvii.html
  • textbook.bystrickaya.ru/hudozhestvennaya-literatura-rossijskaya-proza-stranica-21.html
  • paragraph.bystrickaya.ru/konspekt-uroka-chteniya-v-3-klasse-programma-shkola-2100.html
  • crib.bystrickaya.ru/innovacii-i-ih-vliyanie-na-organizacionnoe-povedenie.html
  • uchitel.bystrickaya.ru/realizuemie-obrazovatelnie-programmi-uchebnij-plan-shkoli-poyasnitelnaya-zapiska-perechen-kruzhkov-i-sportivnih-sekcij-rezultativnost-obrazovatelnogo-processa.html
  • exchangerate.bystrickaya.ru/62-tablica-raspredeleniya-vremeni-videlennogo-na-samostoyatelnuyu-rabotu-i-zadaniya-studentam-ochno-zaochnoj-formi-obucheniya.html
  • abstract.bystrickaya.ru/24-analiz-i-obsuzhdenie-rezultatov-issledovanie-motivacii-agressivnogo-povedeniya.html
  • literature.bystrickaya.ru/belyaeva-ma-v-p-proskurnin-zamestitel-glavi-municipalnogo-obrazovaniya-gorod-suhoj-log-predsedatel-komissii.html
  • tetrad.bystrickaya.ru/urok-po-izucheniyu-romana-i-a-goncharova-oblomov-pervij-urok-bil-posvyashen-izucheniyu-obrazu-oblomova-1-8-glavi-romana.html
  • student.bystrickaya.ru/3-kanal-gorod-31012011-1900-teleprogramma-gorod-3-kanal-31012011-rossijskie-smi-o-mchs-monitoring-za-1-fevralya-2011-g.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.