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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: задача. Предмет: Математика. Добавлен: 24.07.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


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

Определения

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

Маршрутом в графе называется последовательность вершин не обязательно попарно различных, где для любого смежно с . Маршрут называется цепью, если все его ребра попарно различны. Если то маршрут называется замкнутым. Замкнутая цепь называется циклом.

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

Коммивояжер должен объездить n городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат.

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {cij}, где cij ?0 - длинна (или цена) дуги (i, j), . Под маршрутом коммивояжера z будем понимать цикл i1, i2,…, in, i1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера, длина маршрута l(z) равна сумме длин дуг, входящих в маршрут. Пусть Z - множество всех возможных маршрутов. Начальная вершина i1 - фиксирована. Требуется найти маршрут z0 Z, такой, что l(z0)= min l(z), z Z.

Решение задачи

Основная идея метода ветвей и границ состоит в том, что вначале строят нижнюю границу ? длин множества маршрутов Z. Затем множество маршрутов разбивается на два подмножества таким образом, чтобы первое подмножество состояло из маршрутов, содержащих некоторую дугу (i, j), а другое подмножество не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества маршрутов. Полученные нижние границы подмножеств и оказываются не меньше нижней границы множества всех маршрутов, т.е. ?(Z)? ? (), ?(Z) ? ? ().
Сравнивая нижние границы ? () и ? (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.
Затем одно из подмножеств или по аналогичному правилу разбивается на два новых и . Для них снова отыскиваются нижние границы ? (), и ? () и т.д. Процесс ветвления продолжается до тех пор, пока не отыщется единственный маршрут. Его называют первым рекордом. Затем просматривают оборванные ветви. Если их нижние границы больше длины первого рекорда, то задача решена. Если же есть такие, для которых нижние границы меньше, чем длина первого рекорда, то подмножество с наименьшей нижней границей подвергается дальнейшему ветвлению, пока не убеждаются, что оно не содержит лучшего маршрута.
Если же такой найдется, то анализ оборванных ветвей продолжается относительно нового значения длины маршрута. Его называют вторым рекордом. Процесс решения заканчивается, когда будут проанализированы все подмножества.
Для практической реализации метода ветвей и границ применительно к задаче коммивояжера укажем прием определения нижних границ подмножеств и разбиения множества маршрутов на подмножества (ветвление).
Для того чтобы найти нижнюю границу воспользуемся следующим соображением: если к элементам любого ряда матрицы задачи коммивояжера (строке или столбцу) прибавить или вычесть из них некоторое число, то от этого оптимальность плана не изменится. Длина же любого маршрутом коммивояжера изменится на данную величину.
Вычтем из каждой строки число, равное минимальному элементу этой строки. Вычтем из каждого столбца число, равное минимальному элементу этого столбца. Полученная матрица называется приведенной по строкам и столбцам. Сумма всех вычтенных чисел называется константой приведения.
Константу приведения следует выбирать в качестве нижней границы длины маршрутов.
Разбиение множества маршрутов на подмножества

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени ?ij нулевых элементов этой матрицы. Степень нулевого элемента ?ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов cij - не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.
Для получения платежной матрицы маршрутов, включающей дугу (i, j) вычеркиваем в матрице строку i и столбец j, а чтобы не допустить образования цикла в маршруте, заменяем элемент, замыкающий текущую цепочку на бесконечность.
Множество маршрутов, не включающих дугу (i, j) получаем путем замены элемента cij на бесконечность.

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

Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:
A
B
C
D
E
F
A
?
26
42
15
29
25
B
7
?
16
1
30
25
C
20
13
?
35
5
0
D
21
16
25
?
18
18
E
12
46
27
48
?
5
F
23
5
5
9
5
?

Решение задачи

Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).
Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r1=15, r2=1, r3=0, r4=16, r5=5, r6=5.
После их вычитания по строкам получим:
1
2
3
4
5
6
1
?
11
27
0
14
10
2
6
?
15
0
29
24
3
20
13
?
35
5
0
4
5
0
9
?
2
2
5
7
41
22
43
?
0
6
18
0
0
4
0
?
Минимумы по столбцам: h1=5, h2=h3=h4=h5=h6.
После их вычитания по столбцам получим приведенную матрицу:
1
2
3
4
5
6
1
?
11
27
0
14
10
2
1
?
15
0
29
24
3
15
13
?
35
5
0
4
0
0
9
?
2
2
5
2
41
22
43
?
0
6
13
0
0
4
0
?
Найдем н и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.