Читать курсовая по математике: "Задача о коммивояжере и ее обобщения" Страница 11


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

которые являются "составными частями" хода коня, имеют нулевой вес; все остальные ребра имеют вес, равный бесконечности. Оптимальный маршрут имеет нулевой вес и должен быть маршрутом коня. Читатель, возможно, удивится, узнав, что поиск маршрутов коня с помощью хороших эвристических алгоритмов для задачи коммивояжера вообще не составляет проблемы, в то время как поиск "вручную" является весьма непростой задачей.

ЗАКЛЮЧЕНИЕ Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике. Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики (расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал.

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

В основе метода ветвей и границ лежит следующая идея если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева).

Задача о коммивояжере имеет множество обобщений и методы её решения в различных проявлениях используются на практике.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

    Моисеев Н.Н. Методы оптимизации: Моисеев Н.Н., Иванилова Ю.П., Столярова Е.М.-М., 1978, 352 с; Черноусько Ф.Л. Вариационные задачи механики и управления: Численные методы/ Черноусько Ф.Л., Баничук Н.В.-М.,1973; http://dic.academic.ru/; http://www.lobanov-logist.ru/index.php?newsid=470; http://swsys.ru/index.php?page=article&id=827; http://e-maxx.ru/algo/mst_prim; http://www.dissercat.com/content/nekotorye-zadachi-marshrutizatsii-i-raspredeleniya-zadanii-metod-dinamicheskogo-programmirov; www.vecon.ru.



Интересная статья: Основы написания курсовой работы