Министерство образования и науки Украины Национальный технический университет Украины Киевский политехнический институт Славутичский филиал Расчетно-графическая работа по теории алгоритмов на тему Решение задачи коммивояжера методом ветвей и границ Выполнил Студент группы ИСС-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 с. изд. дом Феникс.