Принятие решений с помощью неориентированных графов

Август 24, 2022

Главная
Разное
Принятие решений с помощью неориентированных графов

Содержание

2. Задача о минимаксном остове взвешенного графа
3. На взвешенном неориентированном графе G(X,U) требуется выделить подмножество ребер U’ таких, что: 1. Отношения достижимости вершин
4. Требуется выбрать такие маршруты передвижения между населенными пунктами, которые бы обеспечивали перевозку максимального количества товара каждым
5. Исходный граф G(X,U) Граф G(X,U’) 4 1 2 3 4 5 3 8 1 7 5
7. Шаг 1. А = 1 Шаг 2. В = │U│. Шаг 3. Ищется перестановка ребер π
8. Пользуясь приведенным выше алгоритмом, определить минимаксный остов графа, изображенного на рис. 2.1 слева. Решение. А=1. В=8.
9. 10. Очевидно, что отношения достижимости вершин графов G(X,U’) и G(X,U) не совпадают. 11. А = С
10. Достоинства: Гарантия получения глобально оптимального решения. Сравнительно высокое быстродействие. Легкость программной реализации. Возможность использовать алгоритм для
11. 1. Пользуясь алгоритмом 2.1, определить минимаксный остов графа G(X,U), заданного матрицей М ниже: 2. Предложите альтернативу
12. Задача о минимаксных маршрутах
13. На взвешенном неориентированном графе G(X,U) выделена вершина и требуется определить такое подмножество ребер U’, что: 1.
14. Требуется выбрать такие маршруты передвижения между населенными пунктами, которые бы обеспечивали перевозку максимального количества товара каждым
15. Исходный граф G(X,U) Граф G(X,U’) 4 1 2 3 4 5 3 8 1 7 5
17. Шаг 1. Q = 0. Шаг 2. На множестве ребер, инцидентных выделенной вершине , выбирается ребро
18. Пользуясь приведенным выше алгоритмом 3.1, определить оптимальное значение целевой функции задачи (3.1) применительно к графу, изображенному
19. Q = 0. Выбирается ребро (1,2), вес которого равен трем, Q=3. Вес всех ребер, инцидентных х₁,
20. 2 1 2 3 4 5 0 5 1 7 5 2 4 3 1 3
21. 5. Выбирается ребро (1,5) с весом, равным трем. 6. Q=Q+3=6. 7. Вес всех ребер, инцидентных х₁,
22. 2 1 3 4 5 2 1 1 7 2 0 1 3 4 1 1
23. 10. Вес обоих ребер, инцидентных первой вершине, равен единице. 11. Q = Q + 1 =
24. Исходный граф G(X,U) Оптимальный граф G(X,U’) 4 1 2 3 4 5 3 8 1 7
25. Достоинства: Гарантия получения глобально оптимального решения. Высокое быстродействие. Легкость программной реализации. Низкие требования к объему оперативной
26. Пользуясь алгоритмом 3.1, определить минимаксные маршруты из третьей вершины графа G(X,U), заданного матрицей М ниже, во
27. Определить: минимаксные маршруты из второй вершины графа G(X,U), заданного матрицей М ниже, во все остальные: минимальные
28. №3 №4
30. №7 №8
31. №9 №10
32. №11 №12
33. №13 №14
34. №15 №16
35. №17 №18
36. №19 №20
37. №21 №22
39. Скачать презентацию

Слайд 2

Задача о минимаксном остове взвешенного графа

Слайд 3

На взвешенном неориентированном графе G(X,U) требуется выделить подмножество ребер U’

таких, что:
1. Отношения достижимости вершин графов G(X,U’) и G(X,U) совпадают.
2. Максимальный вес ребра подмножества U’ является минимальным.

Слайд 4

Требуется выбрать такие маршруты передвижения между населенными пунктами, которые бы

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

Слайд 5

Исходный граф G(X,U)
Граф G(X,U’)
4
1
2
3
4
5
3

8 1 7

5 2

4
6

3 1

Минимаксный остов (подмножество ребер U’) исходного графа G(X,U), изображенного на рис. слева, показан на том же рисунке справа (граф G(X,U’)).

Слайд 6

Слайд 7

Шаг 1. А = 1
Шаг 2. В = │U│.
Шаг 3. Ищется

перестановка ребер π = {(i,j)₁, (i,j)₂, (i,j)₃, … } такая, что справедливо неравенство: r(i,j)k < r(i,j)k+1.
Шаг. 4. С = entire{(А + В)/2}.
Шаг 5. Из исходного графа удаляются все ребра, индекс k которых в упорядочении π превышает С. Подмножество оставшихся ребер обозначается U’.
Шаг 6. Если для полученного и исходного графа совпадают условия достижимости вершин: то перейти к шагу 7, в противном случае – к шагу 9.
Шаг 7. Если В – А < 2, то перейти к шагу 10, в противном случае – к шагу 8.
Шаг 8. В = С, перейти к шагу 4.
Шаг 9. А = С, перейти к шагу 4.
Шаг 10. Конец алгоритма. Значение целевой функции равно весу ребра, стоящего на B-м месте в перестановке π.

Слайд 8

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

рис. 2.1 слева.
Решение.
А=1.
В=8.
π = {(3,5), (3,4), (1,2), (2,4), (2,3), (1,5), (4,5), (2,5)}.
С = entire{(А + В)/2}=4.
U’={(3,5), (3,4), (1,2), (2,4)}.
Граф G(X,U’) изображен на рис. 1 справа, отношения достижимости его вершин совпадают с отношениями достижимости вершин графа G(X,U).
Так как В – А > 2, то В = С = 4.
С = 2.
U’={(3,5), (3,4)}.

Слайд 9

10. Очевидно, что отношения достижимости вершин графов G(X,U’) и G(X,U) не

совпадают.
11. А = С = 2.
12. Так как разность В – А = 2, определяется новое значение С = 3.
13. U’={(3,5), (3,4), (1,2)}.
14. Очевидно, что отношения достижимости вершин графов G(X,U’) и G(X,U) вновь не совпадают.
15. А = С=3.
16. Так как В – А < 2, то алгоритм закончен. Оптимальное подмножество U’={(3,5), (3,4), (1,2), (2,4)}, оптимальное значение целевой функции равно четырем, граф G(X,U’) изображен на рис. 2.1 справа.

Слайд 10

Достоинства:
Гарантия получения глобально оптимального решения.
Сравнительно высокое быстродействие.
Легкость программной реализации.
Возможность использовать

алгоритм для орграфов, изменив шаг 6.
Недостатки:
Перебор, реализуемый на шаге 6, понижает быстродействие алгоритма.
После того, как оптимальное решение найдено, алгоритм продолжает поиск, чтобы убедиться в этом.

Слайд 11

1. Пользуясь алгоритмом 2.1, определить минимаксный остов графа G(X,U), заданного

матрицей М ниже:
2. Предложите альтернативу описанному выше алгоритму.

Слайд 12

Задача о минимаксных маршрутах

Слайд 13

На взвешенном неориентированном графе G(X,U) выделена вершина и требуется определить

такое подмножество ребер U’, что:
1. Отношения достижимости выбранной вершины и остальных вершин множества Х на графах G(X,U’) и G(X,U) совпадают.
2. Минимизируется максимальный или суммарный вес ребер любого маршрута на G(X,U’) из выбранной вершины .

Слайд 14

Требуется выбрать такие маршруты передвижения между населенными пунктами, которые бы

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

Слайд 15

Исходный граф G(X,U)
Граф G(X,U’)
4
1
2
3
4
5
3

8 1 7

5 2

4
6

Оптимальное подмножество ребер U’ исходного графа G(X,U), изображенного слева, показано на том же рисунке справа (граф G(X,U’)) при условии, что S = 1, Т = 3.

Минимальный суммарный вес ребер маршрута 1-3.

Минимальный вес максимального ребра маршрута 1-3.

Слайд 16

Слайд 17

Шаг 1. Q = 0.
Шаг 2. На множестве ребер, инцидентных выделенной

вершине , выбирается ребро с минимальным весом r(s,k) .
Шаг 3. Q = Q+r(s,k).
Шаг 4. Вес всех ребер, инцидентных выделенной вершине, уменьшается на величину, равную r(s,k).
Шаг 5. Если на графе возникли ребра с нулевым весом, то соответствующие вершины «стягиваются» в выделенную.
Шаг 6. Если на полученном графе возникли параллельные ребра, то из каждой такой пары сохраняется то ребро, вес которого меньше, а остальные ребра удаляются.
Шаг 7. Если все вершины стянуты в выделенную, то перейти к шагу 8, в противном случае – к шагу 2.
Шаг 8. Конец алгоритма. Величина Q равна оптимальному значению целевой функции системы (3.1).

Слайд 18

Пользуясь приведенным выше алгоритмом 3.1, определить оптимальное значение целевой функции

задачи (3.1) применительно к графу, изображенному на рис. 3.1 слева при условии, что s = 1.

Слайд 19

Q = 0.
Выбирается ребро (1,2), вес которого равен трем, Q=3.
Вес всех

ребер, инцидентных х₁, уменьшается на величину, равную трем (рис. 3.2).
Вершина «2» «стягивается» в вершину «1» (рис. 3.3) при этом ребро (2,5) удаляется .

Слайд 20

2
1
2
3
4
5
0 5 1 7
5

4
3

5 4 1 7

Рис. 3.2 Рис. 3.3

Слайд 21

5. Выбирается ребро (1,5) с весом, равным трем.
6. Q=Q+3=6.

7. Вес всех ребер, инцидентных х₁, уменьшается на величину, равную трем (рис. 3.4) 8. После «стягивания ребра (1,5) и отбрасывания дуг (3,1) и (4,5) граф преобразуется к виду (рис. 3.5):

Слайд 22

2
1
3
4
5
2 1 1 7
2
0
1

1 1

Рис. 3.4 Рис. 3.5

Q = 6 Q = 7

Слайд 23

10. Вес обоих ребер, инцидентных первой вершине, равен единице.
11. Q =

Q + 1 = 7.
12. После вычитания единицы из веса ребер (1,3) и (1,4), их вес становится нулевым и они «стягиваются», а ребро (3,4) отбрасывается.
13. Поскольку все вершины стянуты в корневую, алгоритм закончен. Оптимальное значение Q = 7, ему соответствует исходный граф, не содержащий отброшенных в ходе поиска ребер (см. рис. 3.1, справа).

Слайд 24