Задача коммивояжера методом ветвей и границ

Министерство образования и науки Украины Национальный технический университет Украины Киевский политехнический институт Славутичский филиал Расчетно-графическая работа по теории алгоритмов на тему Решение задачи коммивояжера методом ветвей и границ Выполнил Студент группы ИСС-31 факультета информатики и вычислительной техники Петренко Василий г. Славутич, 2005 р. План 1. Вступление 2. Постановка задачи 3. Математическая модель задачи коммивояжера 4. Алгоритм решения 5. Выводы 6. Список использованной литературы 1. Вступление В 1859 г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил детскую головоломку, в которой предлагалось совершить круговое путешествие по 20 городам, расположенных в различных частях земного шара. Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города a, b, t. Обязательным условием являлось требование каждый город за исключением первого можно посетить один раз. Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере.

Коммивояжер не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами.

Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой.

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

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

Имеются n городов, расстояния стоимость проезда, расход горючего на до... Если считать города вершинами графа, а коммуникации i, j его дугами, т... Алгоритм Литтла для решения задачи коммивояжера можно сформулировать в... Если в матрице, приведенной по строкам, окажутся столбцы, не содержащи... Подмножество гамильтоновых контуров содержит дугу ее не содержит. Для ...

Математическая модель задачи коммивояжера

. Математическая модель задачи коммивояжера. Для того, чтобы исключить при постановке задачи все возможные подциклы... 4. Однако этих ограничений не достаточно для постановки задачи коммивояже...

Алгоритм решения

Дана матрица расстояний, представленная в таблице 1. Таким образом, претендентом на включение в гамильтонов контур является... Чтобы не допустить образования негамильтонова контура, в таблице 3 зам... На рис.2 представлено дерево ветвлений. Затем все множество контуров разбивают на два подмножества таким образ...

Список использованной литературы

Список использованной литературы 1. О. Е. Акимов Дискретная математика.

Логика, группы, графы, Москва, 2003, 376 с ил изд. дом Лаборатория базовых знаний. 2. Ф. А. Новиков Дискретная математика для программистов С Петербург, 2002 г. 304 с ил изд. дом Питер. 3. В. М. Бондарев Основы программирования 1998 г 368 с. изд. дом Феникс.