Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Контрольная работа: Задача о составлении маршрута коммивояжера. Метод ветвей и границ

Название: Задача о составлении маршрута коммивояжера. Метод ветвей и границ
Раздел: Рефераты по математике
Тип: контрольная работа Добавлен 10:37:10 10 июня 2011 Похожие работы
Просмотров: 3701 Комментариев: 2 Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать

Задача о составлении маршрута коммивояжера. Метод ветвей и границ


Введение

Актуальность данной темы заключается в следующем, Для решения оптимизационных и других задач строительства нередко прибегают к формулировке поставленной задачи в виде каких-то хорошо известных математических задач: транспортная задача, задача поиска оптимального пути (задача коммивояжера) и другие. Сформулированную таким образом задачу решают, используя такие математические методы, как метод ветвей и границ, симплексный метод,метод Фогеля (приближенного решения), метод дефектов и другие методы.

Переборные алгоритмы не эффективны (в расчете на худшую задачу), поэтому успех в решении каждой конкретной задачи существенным образом зависит от способа организации перебора.

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

Целью данной работы будет:

1. Познакомить читателя с основными понятиями теории графов.

2. Дать представление о задаче коммивояжера.

3. Описать метод ветвей и границ.

4. Привести пример использования метода ветвей и границ для решения задачи коммивояжера.


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

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3,4…n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? В терминах теории графов: найти гамильтонов цикл в графе минимальной длины.

Задача коммивояжера является так называемой NP-трудной задачей, т.е. задачей, точное решение которой в общем случае может быть получено только за экспоненциальное время. Следовательно, решать ее переборным алгоритмом неэффективно при большом количестве вершин графа.

Одним из подходов к ее решению является сокращение перебора методом ветвей и границ. Этот метод позволяет опознать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге отсекается целая ветвь. Тем не менее, удовлетворительных оценок быстродействию алгоритма Литтла, основанного на этом методе, и родственных алгоритмов нет, хотя практика показывает, что на современных ЭВМ они иногда позволяют решить задачу коммивояжера для графов с количеством вершин, меньшим 100.

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера. В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия «разделяй и властвуй»). На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. В качестве примера конкретного применения метода может быть предложена прикладная задача, связанная с проблемой размещения и обслуживания оборудования, в которой требуется определить оптимальную траекторию циклического маршрута движения робота-транспортера по траектории цеха с целью периодического обслуживания оборудования.

2. Обзор других методов решения задачи коммивояжера

Другие методы, предложенные для поиска кратчайших гамильтоновых циклов – алгебраический метод, основанный на работе Йоу, Даниэльсона и Дхавана (включает в себя построение всех простых цепей с помощью последовательного перемножения матриц), метод перебора Робертса и Флореса (метод перебора имеет дело с одной цепью, непрерывно продлеваемой вплоть до момента, когда либо становится ясно, что эта цепь не может привести к гамильтонову циклу. Тогда цепь модифицируется некоторым систематическим способом, после чего продолжается поиск гамильтонова цикла. Другой подход – мультицепной метод, предложенный Селби.

3. Теория графов

3.1 Основные понятия теории графов. Определения

Граф G задается множеством точек или вершин x 1 , x2 , …xn (которое обозначается через X) и множеством линий или ребер a1 , a2 , …am (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается парой (X, A).

Если ребра из множества А ориентированны, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называют ориентированным графом. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Граф в этом случае обозначается парой G=(X, Г).

Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

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

Иногда дугам графа G сопоставляются (приписываются) числа – дуге (xi , xj ) ставится в соответствие некоторое число ci j , называемое весом, или длинной. Тогда граф G называется графом со взвешенными дугами. Иногда веса приписываются вершинам xi графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. При рассмотрении пути , представленного последовательностью дуг, за его вес (или длину) принимается число , равное сумме весов всех дуг, входящих в , т.е. .

Гамильтонов цикл в орграфе – это ориентированный цикл (контур), проходящий ровно один раз через каждую вершину графа (т.е. простая орцепь).

коммивояжер граф задача метод

Если G = (X, A) – неориентированный граф с n вершинами, то остовным деревом (или, короче, остовом) графа G называется всякий остовный подграф G, являющийся деревом (т.е. графом не имеющим циклов, в котором каждая пара вершин соединена одной и только одной простой цепью). Например, если G – граф, показанный на рис. 1а, то графы на рис. 1.б, в являются остовом этого графа.

3.2 Задача коммивояжера

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

Постановка задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3,4…n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? В терминах теории графов: найти гамильтонов цикл в графе минимальной длины.

Задача коммивояжера является так называемой NP-трудной задачей, т.е. задачей, точное решение которой в общем случае может быть получено только за экспоненциальное время. Следовательно, решать ее переборным алгоритмом неэффективно при большом количестве вершин графа.

Решение обобщенной задачи коммивояжера

Пусть каждой дуге (i, j) графа (I, U) поставлено в соответствие число называемое длиной дуги.

Рассмотрим задачу: определить кратчайший путь из множества А в множество В, пересекающий каждое множество разбиения один и только один раз. Очевидно, что если каждое множество разбиения состоит из одного элемента и , то имеем обычную задачу коммивояжера.

Определим функцию : положим для произвольного пути . Итак, значениями функции будут множества номеров подмножеств разбиения, которые пересекает путь . Пусть каждое множество Фi , , состоит из всевозможных подмножеств множества {1, 2,…, p}, a. Применим для решения этой задачи следующий алгоритм.

Достаточной системой функций в данном случае будут функции

Обозначим через число элементов произвольного конечного множества А.

Шаг 0. Положим . Пометим вершины признаками . Для помеченных вершин увеличим на 1. Рассмотрим одну из пометок и перейдем к шагу 1.

Шаг 1. Пусть – рассматриваемая пометка. Пометим признаками все те вершины, для которых . Для вновь помеченных вершин увеличим на 1.

Рассмотрим следующую помеченную вершину, и будем повторять помечивания до тех пор, пока не пометим некоторую вершину так, чтобы для признака пометки этой вершины выполнялось условие или пока нельзя будет сделать дальнейших пометок. В первом случае перейдем к шагу 2. а во втором к шагу 3.

Шаг 2. Строим кратчайший допустимый путь от вершины . Пусть – пометка вершины, для которой . Перейдём к вершине и рассмотрим пометку вершины,

для которой . Далее перейдем к вершине , с пометкой , для которой . Последовательность и является кратчайшим допустимым путем.

Шаг 3. Пусть – множество помеченных вершин. Рассмотрим все возможные числа при . Определим среди этих чисел наименьшее и возьмем его за новое приближение к длине искомого пути. Затем перейдем к шагу 1.

Этот алгоритм можно изменить. Если для некоторой пометки при всех j, для которых или , то путь соответствующий этой пометке, уже продленво все смежные с вершины. Следовательно, для таких пометок признаки можно стирать.

3.3 Метод ветвей и границ (МВГ)

Представим, что необходимо обойти все города страны. Так как их много, то определить кратчайший путь затруднительно. Тогда можно выбрать некоторое разбиение множества городов, например, рассматривать республики, области или районы, и определить кратчайший путь, пересекающий каждое из выбранных подмножеств разбиения только один раз. Затем уже в пределах выбранных подмножеств достроить полученный путь до требуемого. Такой подход используется в методе ветвей и границ. Этот метод позволяет опознать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге отсекается целая ветвь. Тем не менее, удовлетворительных оценок быстродействию алгоритма Литтла, основанного на этом методе, и родственных алгоритмов нет, хотя практика показывает, что на современных ЭВМ они иногда позволяют решить задачу коммивояжера для графов с количеством вершин, меньшим 100.

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.

Описание метода ветвей и границ

Пусть х1 – центр куба Х. Вычисляем и присваиваем это значение рекорду . Разбиваем куб Х 1i со стороной ½ и вычисляем значения целевой функции в их центрах: , i= 1,… 2n , обновляя по ходу вычислений значение рекорда . Проверяем выполнение условия для i=1,…, 2n и отбрасываем соответствующие подкубы. Каждый из оставшихся разбиваем на 2n одинаковых подкубов Х2 ij со стороной ¼ и поступаем как прежде. На любом шаге у нас формируется множество К «кубиков» со сторонами 2- l , l>=2, целое. Правило выбора очередного кубика для разбиения называется правилом ветвления – возможные варианты приводятся ниже. Кубики со стороной не больше исключаются из множества К – дробление кубика заканчивается. Также исключаются кубики, попавшие в множество (с индексом k – номером кубика) для текущего значения рекорда, – правило отсечения ветвей. Рекорд обновляется при получении меньшего значения целевой функции (правило получения границ, т.е. оценок). Значения целевой функции вычисляются в центре каждого нового подкубика, включаемого в К после разбиения выбранного для этого кубика. Алгоритм останавливается, когда К пусто.

Рис. 2. Граф-дерево

Указанная терминология и название метода определяются тем, что визуально данная схема перебора представляется в виде графа-дерева, корневая вершина которого соответствует кубу Х, вершины первого яруса – подкубам Xli , вершины второго яруса – кубикам X2 li , подсоединенным к своим порождающим вершинам Xli -го яруса, и т.д. (см. рис. 2). Если кубик исключается из К, его вершина закрывается – из нее не будут идти ветви на следующий ярус. Порядок закрытия вершины определяется правилом отсечения (своим для каждой массовой задачи), порядок раскрытия – правилом ветвления (своим для каждой индивидуальной задачи). Различают два вида правил ветвления по типу построения дерева решений (выбора вершин для раскрытия): «в ширину», когда сначала раскрываются все вершины одного яруса до перехода к следующему, и в «глубину» – всякий раз раскрывается лишь одна (обычно с лучшим значением рекорда) вершина на ярусе до конца ветви. На практике реализуют некоторую смесь, например, первое правило пока хватает машинной памяти (в К не слишком много элементов), затем переключаются на второе. Предпочтительность той или иной стратегии ветвления оценивается каждым вычислителем по-своему, исходя из главной задачи метода ветвей и границ – быстрее получить лучший рекорд, чтобы отсечь больше ветвей. Удачный выбор стратегии ветвления в МВГ (например, на основе имеющейся у вычислителя дополнительной информации или эвристических соображений об объекте) позволяет (хотя и не гарантированно) решать задачи большой размерности.

Отметим, что в худшем случае – не удается отбросить ни одной точки х – и приходим к полному перебору; т.е. указанная экспоненциальная оценка точна на классе всех липшицевых функций.

4. Выбор объекта управления. анализ аспектов его работы

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

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

5. Постановка и решение оптимизационной задачи

5.1 Выбор критерия оптимальности

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

Перечислим основные экономические показатели, связанные с работой робота:

1. Прямые затраты

1.1 Единовременные – по доставке машин.

1.2 Амортизационные суммы.

2. Накладные расходы. Заработная плата рабочих.

3. Условно-постоянные расходы.

4. Косвенные расходы.

Анализируя работу робота, можно сказать, что основной экономический показатель, который можно регулировать (и за счет этого добиться большего экономического эффекта) – это амортизационные суммы, связанные с перемещением машин по цеху, строительной площадке и т.п.

Таким образом, следует по возможности сократить путь, проходимый роботом.

Итак, задачу уменьшения денежных затрат мы свели к задаче поиска пути минимальной длинны. Имеем задачу коммивояжера.

5.2 Выявление основных особенностей рассматриваемого объекта

Будем считать, что у нас имеются собранные статистические данные, показывающие время движения робота между агрегатами цеха (См. табл. 1). Здесь – номера агрегатов. – соответствует времени движения выраженном в некоторых условных единицах. Таблица симметрична. Незаполненные поля говорят о невозможности данного маршрута по каким-то причинам.

Таблица 1.

1 2 3 4 5
1 * 4 2 5
2 * 1 9
3 * 3 4
4 * 11
5 *

5.3 Пример решения задачи коммивояжера

Имеем «чисто» математическую задачу, которую решим, используя метод Ветвей и Границ.


В симметричном графе, изображенном на рис. 3, определить кратчайший путь из вершины 1 в вершину 2, проходящим через все вершины графа только по одному разу.

Шаг 0. Значение. Пометим вершину 1 признаком

Шаг 1. Пометим вершину 3 признаками

Рис. 3. Шаг З. Имеем .

Шаг 1. Пометим следующие вершины: вершину 4 – признаками вершину 5 – признаками

Шаг 3. Имеем .

Шаг 1. Пометим вершину 5 признаками

Шаг 3. Имеем .

Шаг 1. Пометим вершину 3 признаками

Шаг 3. Имеем .

Шаг 1. Пометим вершину 4 признаками

Шаг 1. Пометим вершину 2 – признаками так как , то искомый путь построен.

Шаг 2. Искомый путь составляет последовательность вершин 1, 5, 3, 4, 2.

Общее затрачиваемое время в пути составит 13.

Выводы

В данной работе мы познакомили читателя с основными понятиями теории графов, дали представление о задаче коммивояжера, описали метод ветвей и границ. Также привели пример использования метода ветвей и границ для решения задачи коммивояжера.

Еще раз отметим, что задача коммивояжера является одной из самых важнейших задач в теории графов. Возможность представления (записи) различных производственных процессов на языке теории графов и умение решить сформулированную математическую задачу позволяют найти оптимальную стратегию ведения хозяйства, сэкономить ресурсы, выполнить поставленную задачу в более короткие сроки. Очевидно, что изучение методов теории графов, методов математического программирования, системного анализа и пр. – является важным этапом подготовки инженеров в МГСУ.


Список литературы

1. Н.М. Новикова «Основы оптимизации», курс лекций. М. 1998.

2. Н. Кристофидес «Теория графов. Алгоритмический подход», М., Мир, 1978.

3. С.Е. Канторер. «Методы обоснования эффективности применения машин в строительстве». М. 1969.

4. Институт математики им. С.Л. Соболева СО РАН Лаборатория «Математические модели принятия решений», статья «Метод ветвей и границ». Адрес в интернете: http://math.nsc.ru/AP/benchmarks/index.html.

5. Е.А. Тишкин«Эвристический алгоритм решения задачи коммивояжера». Публикация на сайте http://nit.itsoft.ru. Самарский государственныйаэрокосмическийуниверситет, Россия.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:51:09 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:54:26 29 ноября 2015

Работы, похожие на Контрольная работа: Задача о составлении маршрута коммивояжера. Метод ветвей и границ
Эйлеровы и гамильтоновы графы
Министерство народного образования Республики Дагестан Дагестанский Государственный Университет Курсовая работа Программирование задач на графах ...
И так до тех пор, пока не будет исчерпано все множество Гk"[e(S0)] и придется прибегнуть к возвращению (т.е. e(S0) удаляется из S0 и заменяется другой вершиной и т.д.). Отметим ...
Для практической реализации метода ветвей и границ применительно к задаче коммивояжера нужно указать прием определения нижних границ подмножеств и разбиения множества гамильтоновых ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 6760 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать
Орграфы, теория и применение
Федеральное агентство по образованию РФ Государственное образовательное учреждение высшего профессионального образования "Санкт-Петербургский ...
Граф называется двудольным, если существует такое разбиение множества его вершин на две части, что концы каждого ребра принадлежат разным частям (долям).
ОРИЕНТИРОВАННЫЙ ГРАФ (ОРГРАФ) G есть пара G=(V,E), где V - к-нечное множество вершин, а E - п-оизвольное подмножество V*V - множество ориентированных (направленных) ребер (дуг).
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1147 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
AGraph: библиотека классов для работы с помеченными графами
1. Актуальность разработки библиотек для работы с графами К настоящему времени накоплен большой опыт решения теоретико-графовых задач на ЭВМ ...
Библиотека предлагает различные абстрактные типы данных (стеки, очереди, приоритетные очереди, отображения, списки, множества, разбиения, словари, интервальные множества и др ...
В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на ...
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 1852 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Алгоритм Дейкстры
1. Постановка задачи Настоящая курсовая работа моделирует логическую задачу, состоящую из следующих частей: 1) Изучение конкретного раздела дискретной ...
В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от s к этой вершине.
В конце шага 2 каждой итерации временная пометка l(xi) дает кратчайший путь от s к xi, проходящий полностью по вершинам множества S1.
Раздел: Рефераты по математике
Тип: курсовая работа Просмотров: 2352 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Экспертные системы. Классификация экспертных систем. Разработка ...
db_dan(""°ў аЁйҐбвў° ЇаҐ$ЇаЁЁ= вҐ"Ґ°",7605,"ГЁ" db_dan("Ѭ*Ѭ"",1165,""°ў аЁйҐбвў° ЇаҐ$ЇаЁЁ= вҐ"Ґ°" db_dan("ѬѬ"*",7094,"Ѭ*Ѭ"" db_dan("-"*",8205,"ѬѬ ...
Вершины такого графа связаны между собой дугами, отвечающими операторам.
Один из приемов, который может позволить снизить требуемый объем перебора, состоит в том, чтобы сразу же после раскрытия вершины отбросить почти все дочерние вершины, оставив лишь ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 34045 Комментариев: 7 Похожие работы
Оценило: 10 человек Средний балл: 4.5 Оценка: 5     Скачать
Графы и их представление на ЭВМ
Федеральное агентство по образованию Федеральное государственное общеобразовательное учреждение высшего профессионального образования Чувашский ...
Графом G(V, Е) называется совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элемен тов множества V (Е - множество ...
5. Если задана функция Е: V ° М и/или F: Е° М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным).В качестве множества пометок обычно ...
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 3405 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Эйлеровы графы
ПОМОРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. Ломоносова КУРСОВАЯ РАБОТА ЭЙЛЕРОВЫ ГРАФЫ Выполнила студентка 4 курса 42 группы математического ...
Граф G - пара (V,X), где V конечное непустое множество, содержащее p вершин, а множество Х содержит q неупорядоченных пар различных вершин из V.
- Помеченные графы (или перенумерованные), если его вершины отличаются одна от другой какими-либо пометками.
Раздел: Рефераты по математике
Тип: курсовая работа Просмотров: 2249 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Блочно-симметричные модели и методы проектирования систем обработки ...
Казахский Национальный Технический Университет имени К.И.Сатпаева УДК 658.512 519.87 004.83 на правах рукописи НАБИЕВА ГУЛНАЗ СОЦИАЛЕВНА Блочно ...
Технологии решения каждой задачи соответствует направленный граф , где множество вершин графа, отражающих информационные элементы задачи ; - множество отношений между ...
В рамках синтеза модульных диалоговых систем поставлена и решена задача оптимального выделения подсистем ДС в соответствии с определенным локальными сценариями диалогов, разбиения ...
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 1847 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Программирование на сетях
Содержание: Введение. 2 1. Основные понятия теории графов. 3 2. Матричные способы задания графов. 4 3. Упорядочение элементов орграфа. 6 4. Постановка ...
Если в графе G все элементы множества U изображаются дугами, то граф называется ориентированным (орграф), если ребрами, - неориентированным.
Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями.
Раздел: Рефераты по экономико-математическому моделированию
Тип: курсовая работа Просмотров: 461 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Основы дискретной математики
Федеральное агентство по образованию Новомосковский институт (филиал) Государственного образовательного учреждения высшего профессионального ...
Шаг 3. Если все вершины графа вошли в один букет, то процедура заканчивается, т. к. помеченные голубым ребра образуют покрывающее дерево.
Шаг 2. В случае формирования контура строится уменьшенный граф путем стягивания дуг и вершин выявленного контура исходного графа Go в одну вершину V.
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 4177 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Все работы, похожие на Контрольная работа: Задача о составлении маршрута коммивояжера. Метод ветвей и границ (2118)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151259)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru