Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задачи для самостоятельного решенияПоиск на нашем сайте Задачи для самостоятельного решения Найти решения задач о назначениях на узкие места для следующих матриц эффективностей: 1. 2.
3. 4.
5. ЗАДАЧА КОММИВОЯЖЕРА Имеется n городов, между которыми существует определенная сеть дорог. Коммивояжер, выходя из некоторого города, должен обойти все остальные города, побывав в каждом из них по одному разу, и вернуться в исходный город. При этом пройденное коммивояжером расстояние должно быть минимально. Расстояния между городами задаются матрицей C = | cij |nxn, у которой элемент cij ≥ 0 равен длине дороги, непосредственно соединяющей i-ый и j-ый города, и равен ∞ при отсутствии дороги, связывающей непосредственно i-ый и j-ый города. Кроме этого cii = ∞, для запрещения коммивояжеру возвращаться сразу же в город.Для графа G = (V, E ) гамильтоновым называется цикл, содержащий все вершины графа. Если построить граф, вершины которого соответсвуют городам, а дуги (ребра) непосредственно связывающим города дорогам, то приписав дугам длины, совпадающие с длинами дорог, мы получим задачу нахождения гамильтонова цикла минимальной длины.Введем для дуг графа G в рассмотрение переменные  Тогда задачу коммивояжера можно сформулировать в виде задачи линейного булевого программирования:  Здесь ce - длина дуги e  E .Для решения задачи коммивояжера применяется одна из реализаций метода ветвей и границ.5.1. Общая схема метода ветвей и границМетод ветвей и границ - общий метод для нахождения решений задач дискретной и комбинаторной оптимизации. Метод является алгоритмом перебора с отсевом подмножеств допустимых решений, не содержащих оптимальных решений. Опишем идею метода на примере поиска минимума функции f(x) на конечном множестве допустимых значений Ω. Метод ветвей и границ основан на трех процедурах: ветвление, нахождение оценок (границ), отсев вариантов. Ветвление состоит в разбиении по некоторому правилу A множества допустимых решений на подмножества Из полученных подмножеств Описанный процесс можно изобразить в виде дерева поиска, корень которого соответсвует исходному множеству допустимых решений Ω, вершины - подмножествам, полученным в результате разбиений по правилу A, дуги идут от вершины-подмножества к вершинам-подмножествам, состовляющим его разбиение.
Общий шаг метода ветвей и границ состоит в выборе из всех висячих вершин дерева поиска вершины с наименьшей границей, разбиении соответствующего подмножества допустимых решений по правилу A, вычислении по правилу B для вновь полученных подмножеств нижних границ с добавлением в дерево поиска вершин и дуг, соответсвующих вновь полученным подмножествам. В силу конечности множества Ω, за конечное число шагов хотя бы одна из висячих вершин будет соответствовать множеству, состоящему из одного допустимого решения {x*}. Значение функции f *= f(x*) называют рекордом. Процедура отсева основана на следующем простом принципе: если нижняя граница γ’ для подмножества Ω’ дерева поиска не меньше f *, то все допустимые решения из множества Ω’ могут быть исключены из дальнейшего рассмотрения (вершина Ω’ в дереве поиска далее не ветвиться). Если нижние границы для всех висячих вершин дерева поиска не меньше рекорда, то решение найдено: Если мы получаем висячую вершину, соответствующую одному допустиму решению {x0}, и f(x0) < f *, то рекорд обновляется f *= f(x0) . Чтобы использовать метод ветвей и границ для решения конкретного класса задач, необходимо указать правило ветвления и правило вычисления нижних границ. 5.2. Алгоритм ЛиттлаАлгоритм Литтла является реализацией метода ветвей и границ для задачи коммивояжера. Правило ветвления состоит в разбиении множества рассматриваемых гамильтоновых циклов на два подмножества, одно из которых состоит из циклов, содержащих выбранную дугу e, а другое из циклов, не содержащих этой дуги. Дуга e выбирается среди дуг минимальной длины по условию, что запрет на использование этой дуги должен приводить к максимальному увеличению длины гамильтонова цикла. Правило вычисления нижних границ основано на процедуре приведения матриц расстояний, соответствующих вновь полученным висячим вершинам дерева поиска.Опишем алгоритм Литтла.Шаг 1. Приведение матрицы расстояний. Находим в каждой i-ой строке матрицы Шаг 2. Вычисляем сумму приводящих констант Шаг 3. Для каждого нулевого элемента c’ij = 0 матрицы Шаг 4. Выбираем нулевой элемент с максимальным штрафом Шаг 5. Вычисляем нижнюю границу γ1 = γ + θij для гамильтоновых циклов подмножества Ω1 .Строим соответсвующую Ω1 матрицу расстояний C’1. Для этого значение элемента c’ij заменяем на Шаг 6. Вычисляем нижнюю границу для гамильтоновых циклов подмножества Ω2. Для этого удаляем из матрицы Шаг 7. Если в результате шага 6 получаем матрицу C’2 порядка два и ее нижняя граница не превышает границ висячих вершин дерева поиска, то процесс заканчивается, решение найдено, преходим к шагу 11. В противном случае переходим к шагу 8. Шаг 8. Среди висячих вершин построенного дерева поиска выбираем вершину с наименьшей границей (если таких вершин несколько, выбираем любую из них). Шаг 9. Если выбранная на шаге 8 вершина соответствует свойству “включающие дугу (i,j)”, то соответствующую ей матрицу расстояний C’2, полученную на шаге 6, берем за С’ и переходим к шагу 3. В противном случае переходим к шагу 10. Шаг 10. Выбранная на шаге 8 вершина соответствует свойству “не включающие дугу (i, j)”). Соответствующую ей матрицу расстояний C’1, полученную на шаге 5, берем за С’ и переходим к шагу 3. Шаг 11. Строим гамильтонов цикл минимальной длины. Для этого включаем в гамильтонов цикл дуги соответствующие нулевым элементам 2x2-матрицы расстояний C’2 , полученной на шаге 7. Далее двигаемся от висячей вершины к корню дерева поиска по единственному обратному пути. При прохождении обратной дуги дерева поиска, соответствующей переходу от множества решений к его подмножеству по свойству “ включающие дугу (i, j)”, дугу (i, j) включаем в гамильтонов цикл. Пример. Решить задачу коммивояжера со следующей матрицей расстояний C¥ ¥ ¥ ¥ ¥
Приведем матрицу по строкам. Имеем: α1 = 2 , α2 = 3 , α3 = 2 , α4 = 2 , α5 = 1 . Получим матрицу ¥ ¥ ¥ ¥ ¥ Приведем матрицу по столбцам. Имеем: β1 = 0, β2 = 0, β3 = 0, β4 = 1, β5 = 0 . Получим матрицу C’ ¥ ¥ ¥ ¥ ¥ Текущая нижняя граница γ = 11 . Находим штрафы для нулевых элементов: θ13 = 1, θ21 = 0, θ23 = 0, θ32 = 3, θ34 = 1, θ45 = 4, θ51 = 1. Максимальный штраф θ45 = 4. Разбиваем множество всех гамильтоновых циклов ¥ ¥ ¥ ¥ ¥ ¥ Для второго подмножества матрица расстояний C’2 получается из C’ удалением 4-ой строки и пятого столбца, причем для запрещения образования цикла 4->5->4, полагаем c’54 =
¥ ¥ ¥ ¥ Сумма приводящих констант равна 0, следовательно, γ2 = 11. Минимальную нижнюю границу имеет множество Ω2. Поэтому в матрице C’2 вычисляем штрафы для нулевых элементов: θ13 = 1, θ21 = 0, θ23 = 0, θ32 = 3, θ34 = 1, θ51 = 1. Максимальный штраф θ32 = 3. Разбиваем множество Ω2 на два подмножества Ω21 - “не включающие дугу (3,2)” и Ω22 - “включающие дугу (3,2)”. Для подмножества Ω21 нижняя граница γ21 = 14. Матрицу расстояний C’21 получим из матрицы C’2, положив c’32 =
¥ ¥ ¥ ¥ ¥ Для подмножества Ω22 матрицу расстояний C’22 получаем из C’2, удаляя третью строку и второй столбец, затем для запрещения образования цикла 3->2->3, полагаем c’23=
¥ ¥ ¥ Сумма приводящих констант равна 1, следовательно, γ22 = 12. В дереве поиска висячие вершины соответсвуют подмножествам Ω1, Ω21, Ω22. Минимальную нижнюю границу имеет множество Ω22. Поэтому в матрице C’22 вычисляем штрафы для нулевых элементов: θ13 = 1, θ14 = 0, θ21 = 0, θ24 = 0, θ51 = 1. В результате сравнения мы получили два одинаковых максимальных штрафа равных 1. Возьмем θ13 = 1. Разбиваем множество Ω22 на два подмножества Ω221 - “не включающие дугу (1,3)” и Ω222 - “включающие дугу (1,3)”. Для подмножества Ω221 нижняя граница γ221 = 13 . Матрицу расстояний C’221 получим из матрицы C’22, положив c’13 =
¥ ¥ ¥ ¥ Для подмножества Ω222 матрицу расстояний C’222 получаем из C’22, удаляя первую строку и третий столбец, затем для запрещения образования цикла 1->3->2->1, полагаем c’21=
¥ ¥ В дереве поиска висячие вершины соответсвуют подмножествам Ω1, Ω21 , Ω221 , Ω222 . Минимальную нижнюю границу имеет множество Ω222. Соответсвующая матрица C’222 имеет размерность 2x2. Следовательно, решение найдено. Переходим к постоению гамильтонового цикла. Включаем в гамильтонов цикл дуги (2,4), (5,1), как соответствующие нулевым элементам матрицы C’222. Затем, двигаясь по дереву поиска к корню, включаем дуги (1,3), (3,2), (4,5). Дерево поиска приведено на рисунке 13.
γ=11
γ1=15 Ω1 Ω2 γ2=11   
γ22=12 γ21=14 Ω22  Ω21 
γ222=12 γ221=13 Ω222 Ω221 
Рис. 13. Гамильтонов цикл минимальной длины состоит из дуг (5,1), (1,3), (3,2), (2,4), (4,5).
|
||
|
|
Последнее изменение этой страницы: 2024-07-06; просмотров: 38; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.217.128 (0.01 с.) |
. Процедура нахождения оценок заключается в поиске по некоторому правилу B нижних границ для минимальных значений функции f(x) на 
. Пусть 
полученные нижние границы. Очевидно, 
.
, выбираем подмножество Ωm, у которого 
. По правилу A разбиваем Ωm на подмножества 
, и вычисляем по правилу B нижние границы для минимальных значений функции f(x) на 
.
минимальный элемент αi и вычитаем его из всех элементов этой строки. В полученной матрице в каждом j-ом столбце находим минимальный элемент βj и вычитаем его из всех элементов данного столбца. После проделанных операций получим матрицу 
, каждая строка и каждый столбец которой содержит, по крайней мере, один нуль.
. Очевидно, что γ является нижней границей для всего множества решений 
, которое берется в качестве корня дерева поиска и текущего множества решений.
находим штраф за неиспользование 
(сумма минимальных элементов в строке и столбце, на пересечении которых стоит нуль, без учета самого нулевого элемента).
. Разбиваем текущее множество всех гамильтоновых циклов 
и приводим полученную матрицу (неприведенными могут быть только i-ая строка и j-ый столбец, поэтому сумма приводящих констант равна θij) .
i-ю строку и j-й столбец, сохраняя исходную нумерацию для оставшихся строк и столбцов, и заменяем на 
на два подмножества Ω1 - “не включающие дугу (4,5)” и Ω2 - “включающие дугу (4,5)”. Для первого подмножества нижняя граница γ1 = 15, а соответствующую матрицу расстояний C’1 получим из матрицы C’, положив c’45 = 
и приведя результат.
, полученный результат приводим.
