Содержание
- 2. 5. Если R ≠ ∅, то переход к п. 2, иначе к п. 6; 1. В
- 3. 10. Составляется конъюнкция П’ = ∧ti. Раскрываются скобки. В полученной дизъюнкции на основе законов булевой алгебры
- 4. В матрице R подсчитываем число ненулевых элементов ri; 3. Гx1 = {x2, x3, x5, x6}, записываем
- 5. 5. R ≠ ∅, max ri = r4 = 4; Гx4 = {x2, x3, x5, x6},
- 6. 12. Составляем конъюнкцию Ci и выполняем минимизацию П = ∧Ci = C1 C2 C4 C5 =
- 7. ϕ1 = {x3, x6}, ϕ2 = {x3, x5}, ϕ3 = {x2, x6}, ϕ4 = {x2, x5},
- 8. Недостатком точных алгоритмов является низкое быстродействие. Поэтому на практике используют приближенные алгоритмы, примером которых может служить
- 9. 1. Положим j = 1; 2. Упорядочим вершины графа в порядке не возрастания ri. x1, x2,
- 10. 5. Упорядочим вершины графа в порядке не возрастания ri: x2, x4, x5, x6, x7, x8; 6.
- 11. Достоинство алгоритма – быстродействие. Недостаток – не оптимальность. Для раскраски вершин графа приближенным алгоритмом потребовалось четыре
- 12. Кратчайшие пути Пусть дан граф G(X, Γ), ребрам которого приписаны веса, заданные матрицей C=||cij||m×m. Задача о
- 13. 1. Положить l(s)=0+ и считать эту пометку постоянной. Положить l(xi)=∞ для всех xi ≠ s и
- 14. Заданы взвешенный граф G(X,Г) и матрица весов C=׀׀cij׀׀7×7. Необходимо найти кратчайшие пути от начальной вершины x1
- 15. 2. Гp ={x2, x6, x7} – все пометки временные, уточним их: l(x2)=min[∞ ,0++2]=2; l(x6)=min[∞, 0++10]=10; l(x7)=min[∞,
- 16. 6. l(xi*) = min[l(xi)] = l(x3) = 5. 7. l(x3) = 5+, p=x3. 8. Не все
- 17. 12. l(xi*) = min[l(xi)] = l(x7) = 11. 13. l(x7) = 11+, p=x7. 14. Не все
- 18. Кратчайшие расстояния от вершины x1 до всех вершин найдены. Как найти кратчайший путь до конкретной вершины,
- 19. Далее, l(x2) = 2, Гx2 ={x1, x3, x7}, 2 = l(x1)+ c(x1, x2)=0+2, 2 ≠ l(x3)+
- 20. Путь с наибольшей пропускной способностью. Каждое ребро графа имеет пропускную способность qij и требуется найти путь
- 21. Алгоритм Франка – Фриша 1. Взять (s-t) разрез К1 = ({s}, X\{s}) и найти 2. Закоротить
- 22. Найти (s-t) путь с наибольшей пропускной способностью в графе G(X,U) 18 18
- 23. 1. Проводим разрез К1 = ({s}, X \{s}) 18 2. Находим 3. Закорачиваем все ребра графа
- 24. 5. Проводим разрез К2, находим 6. Закорачиваем все ребра графа (xi, xj) с qij≥Q2. Это ребра
- 25. 8. Закорачиваем все ребра графа (xi, xj) с qij ≥ Q3. Получаем граф G3.
- 26. 9. Вершины s-t объединены. Пропускная способность искомого пути Q(P)=13. 10. Строим граф, вершины которого – вершины
- 27. Математическая модель задачи размещения Пусть заданы множество элементов E={e1, e2, …, em} и множество фиксированных позиций
- 28. Метод ветвей и границ Метод ветвей и границ – общий алгоритмический метод для нахождения оптимальных решений
- 29. Различные модификации общего метода отличаются способом расчета нижних границ и способом разбиения поля решений. Для описания
- 30. Пусть скалярное произведение двух векторов rd минимально. В векторе r поменяем местами элементы ri и rj.
- 31. Таким образом, простейшая нижняя граница может быть получена при рассмотрении верхних половин матриц R и D
- 32. Пример. Разместить элементы, заданные взвешенным графом G (рис. (а)) на множестве позиций Р (рис. (б)). Составим
- 33. Для этого упорядочим составляющие вектора r в невозрастающем порядке, а вектора d – в неубывающем. r
- 34. Получим v(P) = r×d = 2 + 1 + 0 = 3. Таким образом, нижняя граница
- 35. Назначаем элемент e1 в позицию р2. 3. Помещаем элемент e2 в позицию р1. Размещены два элемента:
- 36. 5. Помещаем элемент e2 в позицию р4. Размещены два элемента: e1 в позиции р2 и e2
- 37. Неразмещенный элемент {e4}, свободная позиция {р3}; r1 ={4} и d 2={1}, r1×d2 = 4; r2 ={0}
- 38. Назначаем элемент e3 в позицию р3. 8. Неразмещенный элемент {e4}, свободная позиция {р1}. Помещаем {e4}в позицию
- 39. Нахождение гамильтонова цикла. Алгоритм Робертса-Флореса Цикл, включающий все вершины один раз, называется гамильтоновым. Алгоритм Робертса-Флореса состоит
- 40. 1. у xr нет "возможной" вершины; 2. цепь S имеет длину ׀S׀=n. В этом случае: а)
- 41. Нахождение гамильтонова цикла Включаем в S начальную вершину S={x1}. Первая "возможная" вершина х2 Гх1, S={x1, х2}
- 42. Следующая "возможная" вершина х5. S={x1, х2, х3, х4, х6, х5}. У х5 больше нет "возможных" вершин.
- 43. И т.д., пока последней не окажется вершина х4, которая образует цикл с вершиной х1. Гамильтонов цикл
- 44. . Нахождение эйлерова цикла. Алгоритм Флери Элегантный алгоритм нахождения эйлерова цикла был предложен М. Флери (М.
- 45. 3. Назначить текущей xj вершину, инцидентную ребру uij. 4. Удалить uij из текущего графа и внести
- 46. Пусть на шаге 1 выбрана вершина x1. При выборе на шаге 2 ограничение никак не сказывается;
- 47. Сравнение эйлеровых и гамильтоновых циклов Несмотря на внешнюю схожесть определений эйлерова и гамильтонова циклов, задачи нахождения
- 48. Графы: эйлеров и гамильтонов (а); неэйлеров и гамильтонов (б); эйлеров и негамильтонов (в); неэйлеров и негамильтонов
- 49. Верны два следующих утверждения о взаимоотношении между эйлеровыми и гамильтоновыми циклами, принадлежащие Ф. Харари. 1. Если
- 50. Алгоритмы построения минимальных связывающих деревьев Для построения МСД разработан ряд полиномиальных алгоритмов. Алгоритм Прима Алгоритм Прима
- 51. Начнем с произвольной вершины графа xi и включим ее в остовное дерево. Из всех вершин, соединенных
- 52. Пример. Исходный взвешенный граф изображен на рисунке. В начале процесса выбираем произвольную вершину, например, х1. Выбираем
- 53. При добавлении к дереву вершины х2 необходимо определить, не следует ли добавить в кандидаты новые ребра.
- 54. Вес ребра (х5 х7) меньше веса ребра (х2 х7), поэтому оно замещает последнее. Из четырех ребер,
- 55. Ребро (х4 х6) имеет наименьший вес среди оставшихся, и оно добавляется следующим. Теперь осталось добавить к
- 56. Алгоритм Краскала Алгоритм заключается в следующем. Упорядочим все ребра исходного графа по не убыванию весов. Просматривая
- 57. Построим МСД для графа Упорядочим ребра: (х4 х6), (х1 х2), (х2 х5), (х1 х3), (х1 х6),
- 58. Следующее включаемое в дерево ребро (х4 х7). Суммарный вес ребер МСД равен 21. Сложность алгоритма Краскала
- 59. Планаризация графа Задача встает при проектировании электронных схем. Электрические цепи печатным способом наносятся на плату из
- 60. Однако критерий Понтрягина-Куратовского неконструктивен (требует перебора). Известны другие критерии, но их также трудно использовать. Разработан ряд
- 61. Критерий Бадера. Граф G(X,U) планарен, если его граф пересечений G' является бихроматическим графом. Критерий справедлив для
- 62. pi – число пересечений ребер i-ой вершины. . . . Согласно п. 5 принятых допущений p1=0.
- 63. Общее число пересечений ребер вершины x2 Для вершины xk Общее число пересечений ребер графа Проще определять
- 64. Определим p2n, для чего в матрице R выделим подматрицу R2n. Сумма единиц подматрицы R2n соответствует p2n.
- 65. Для определения двудольности G' используем максимальные внутренне устойчивые множества. Нахождение максимальных внутренне устойчивых множеств Для нахождения
- 66. 7. Положить i= i+1, пока i 8. Семейство внутренне устойчивых множеств ΨG' построено. Выделение из G'
- 67. Описанная процедура повторяется до тех пор, пока ΨG' не станет пусто.
- 68. Планаризовать граф G(X,U)
- 71. Построение графа пересечений G' Перенумеруем вершины графа таким образом, чтобы ребра гамильтонова цикла были внешними. Тогда
- 72. Строим граф пересечений G' Определим p24, для чего в матрице R выделим подматрицу R24. Ребро (х2х4)
- 73. Построение семейства ΨG ' В первой строке матрицы R(G') находим номера нулевых элементов. Составляем список J(j)
- 74. Из списка J’(j’) выбираем следующий элемент. Записываем дизъюнкцию M147= M14 ∨ r7= {11111110}. И, наконец, M1478=
- 75. Во второй строке ищем следующий нулевой элемент – r25. Составляем дизъюнкцию M25= r2 ∨ r5= {11111011}.
- 76. Семейство максимальных внутренне устойчивых множеств ΨG' построено. Это ψ1 ={u13, u37, u36, u35}; ψ2 ={u13, u37,
- 77. maxαγδ= α16= α35=7, дают две пары множеств ψ1, ψ6 и ψ3, ψ5. Возьмем множества ψ1 ={u13,
- 79. Скачать презентацию