рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Работа сделанна в 2005 году

Задача коммивояжера методом ветвей и границ - Расчетно-графическая Работа, раздел Математика, - 2005 год - Министерство Образования И Науки Украины Национальный Технический Университет...

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

– Конец работы –

Используемые теги: Задача, коммивояжера, методом, ветвей, границ0.079

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Задача коммивояжера методом ветвей и границ

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Применение метода ветвей и границ для задач календарного планирования
К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при загрузке оборудования,… Процесс продолжается до тех пор, пока не получено оптимальное целочисленное… Алгоритм решения: Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи…

Методы решения жестких краевых задач, включая новые методы и программы на С++ для реализации приведенных методов
Стр. 8. Второй алгоритм для начала счета методом прогонки С.К.Годунова.Стр. 9. Замена метода численного интегрирования Рунге-Кутта в методе прогонки… Стр. 10. Метод половины констант. Стр. 11. Применяемые формулы… Стр. 62. 18. Вычисление вектора частного решения неоднородной системы дифференциальных уравнений. Стр. 19. Авторство.…

Лекция 1. Предмет, задачи и методы педагогической психологии. Предмет и задачи педагогической психологии. Психология и педагогика. История развития педагогической психологии в России и за рубежом
План... Предмет и задачи педагогической психологии Психология и педагогика... История развития педагогической психологии в России и за рубежом...

Статистические показатели себестоимости продукции: Метод группировок. Метод средних и относительных величин. Графический метод
Укрупненно можно выделить следующие группы издержек, обеспечивающих выпуск продукции: - предметов труда (сырья, материалов и т.д.); - средств труда… Себестоимость является экономической формой возмещения потребляемых факторов… Такие показатели рассчитываются по данным сметы затрат на производство. Например, себестоимость выпущенной продукции,…

Лекция №1. Задачи начертательной геометрии. Методы проецирования. Комплексный чертеж точки. 1.1. Основные задачи начертательной геометрии. Условные обозначения
План... Основные задачи начертательной геометрии Условные обозначения... Методы проецирования Проецирование точки на две взаимно перпендикулярные плоскости...

Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева
При прямом включении на каждом шаге рассматриваются только один очередной элемент исходной последовательности и все элементы готовой… Полностью алгоритм прямого выбора приводится в прогр. 3. Таблица 2. Пример… Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения.Для С имеем…

- содержательная постановка задачи коммивояжёра, транспортной задачи, задачи распределения ресурсов в ТЭС;
На сайте allrefs.net читайте: - содержательная постановка задачи коммивояжёра, транспортной задачи, задачи распределения ресурсов в ТЭС;...

Расчетно-графическое задание состоит из четырех задач. Для задач 1,2,3 имеется два варианта, для задачи 4 – вариант для каждого студента.
На сайте allrefs.net читайте: Расчетно-графическое задание состоит из четырех задач. Для задач 1,2,3 имеется два варианта, для задачи 4 – вариант для каждого студента....

Метод ветвей и границ
Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение задачи и . Если же компонент… Пусть например переменная приняла в плане Х0 дробное значение.Тогда в… Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному…

Задачи и методы политологии
Но она одна из самых современных общественных наук, поскольку свое целостное оформление и самостоятельное место в системе наук приобрела только в XX… Предмет политологического исследования определяется конкретной задачей,… Выделим пять наиболее очевидных функций политологии. Мировоззренческая функция состоит в том, что политология…

0.046
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам