Использование понятия дерева в информатике и программировании
Дерево — неориентированный граф без циклов.
Деревья особенно часто возникают на практике при изображении различных иерархий. Деревья - очень удобный инструмент представления информации самого разного вида.
Деревья отличаются от простых графов тем, что при обходе дерева невозможны циклы. Это делает графы очень удобной формой организации данных для различных алгоритмов. Таким образом, понятия дерева активно используется в информатике и программировании.
Эквивалентные определения дерева.
1. Связный граф называется деревом, если он не имеет циклов.
2. Содержит N-1 ребро и не имеет циклов.
3. Связный и содержит N-1 ребро.
4. Связный и удаление одного любого ребра делает его несвязным.
5. Любая пара вершин соединяется единственной цепью.
6. Не имеет циклов и добавление одного ребра между любыми двумя вершинами приводит к появлению одного и только одного цикла.
36. Итерпритация задачи о кратчайших путях.
Нахождение кратчайшего пути в графе Пусть дан граф, дугам которого приписаны веса. Задача о нахождении кратч-о пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что такой путь существует. Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответ-ь стоимости (или времени) передачи инфор-и м/у вершинами. В этом случае мы ищем самый дешевый (или самый скорый).
Алгоритм нахождения кратчайшего пути Данные: Расстояния D[v] от фиксированной вершины s до всех остальных вершин v V, фиксированная вершина t, матрица весов ребер,A[u, v], u, v V.Рез-ты: СТЕК сод-т последов-ть вершин, опред-ую кратч-ий путь из s в t.Begin CTEK := ; CTEK t; v:= t;while v ╧ s dobegin u := вершина, для которой D[v] = D[u] + A[u, v]; CTEK u; v:= u endend.
37. Данная задача может быть разбита на две 2 типа:
1. для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;
2. найти кратчайшие пути между всеми парами вершин.
38. алгоритм решения для задачи первого типа:
Необходимо найти путь от s - начальной вершины до t - конечной вершины. Каждой вершине присваиваем пометки I(Xi).
1. I(s) = 0, I(Xi) равно бесконечности для всех Хiне равных s и считать эти пометки временными. Положить р = s.
2. Для всех Хi, пренадлежащихГ(р) и пометки которых временны, изменить пометки по следующему правилу:
I(Xi) = min[I(Xi), I(p) + c(p, Xi)]
3. среди всех вершин с временными пометками найти такую, для которой I(Xi*) = min[I(Xi)]
4. считать пометку вешины Хi* постоянной и положить р = Хi*.
5. если р =t,тоI(р) явл-я длинной кратч-о пути,если нет, перейти к шагу 2.
39. Задача о нахождении максимального потока.
Пусть дан граф G, в котором выделены две вершины: исток S и сток T, а у каждого ребра определена пропускная способность Cu,v. Поток F можно представить как поток вещества, которое могло бы пройти по сети от истока к стоку, если рассматривать граф как сеть труб с некоторыми пропускными способностями. Т.е. поток - функция Fu, v, определённая на множестве рёбер графа.
Задача заключается в нахождении максимального потока. Здесь будет рассмотрен метод Эдмондса-Карпа, работающий за O (N M2), или (другая оценка) O (F M), где F - величина искомого потока. Алгоритм был предложен в 1972 году.
Алгоритм
Остаточной пропускной способностью называется пропускная способность ребра за вычетом текущего потока вдоль этого ребра. При этом надо помнить, что если некоторый поток протекает по ориентированному ребру, то возникает так называемое обратное ребро (направленное в обратную сторону), которое будет иметь нулевую пропускную способность, и по которому будет протекать тот же по величине поток, но со знаком минус. Если же ребро было неориентир-м, то оно как бы распадается на два ориент-х ребра с одинаковой пропускной способностью, и каждое из этих рёбер является обратным для др-го (если по одному протекает поток F, то по другому протекает -F).
Общая схема алгоритма Эдмондса-Карпа такова. Сначала полагаем поток равным нулю. Затем ищем дополняющий путь, т.е. простой путь из S в T по тем рёбрам, у которых остаточная пропускная способность строго положительна. Если дополняющий путь был найден, то производится увеличение текущего потока вдоль этого пути. Если же пути не было найдено, то текущий поток является максимальным. Для поиска дополняющего пути может использоваться как Обход в ширину, так и Обход в глубину.
Рассмотрим более точно процедуру увеличения потока. Пусть мы нашли некоторый дополняющий путь, тогда пусть C - наименьшая из остаточных пропускных способностей рёбер этого пути. Процедура увеличения потока заключается в следующем: для каждого ребра (u, v) дополняющего пути выполним: Fu, v += C, а Fv, u = - Fu, v (или, что то же самое, Fv, u -= C).
Величиной потока будет сумма всех неотрицательных величин FS, v, где v - любая вершина, соединённая с истоком.
Основные понятия и определения теории планирования эксперимента.
Планирование эксп-а – процедура выбора числа и условий проведения опытов, необходимых и достаточных для решения поставленной задачи.
Основная задача метода планирования эксперимента – найти оптимальное условия реализации опыта.
«Черный ящик»
Стрелки y1…yk – численные характеристики целей исследования, наз. параметрами оптимизации. Для проведения эксперимента необходимо вождействовать на поведение черного ящика. Способы воздействия обозначены стрелками x1…xk – факторы. Ур-ие связывающее параметр оптимизации с факторами наз. ф-цией отклика.
Каждый фактор в опыте может принимать одно или несколько значений, кот наз уровнями. Фиксированный набор уровней фвкторов определяет 1 из возможных состояний черного ящика. Одновременно это есть условие проведения 1 из возможных опытов. Если перебрать все возможные наборы состояний, то получим полное множество различных состояний данного ящика, т.е. число возможных различных опытов. Чтобы узнать это числа, достаточно число уровней факторов р (если оно одинакового для всех факторов) возвести в степень числа факторов к.
Для систем с 5 факторами на 5 уровнях число состояний n=55=3125
Перебор велик и найти оптимум сложно. Для этого применяют планирование экстремального эксперимента, т.е. метод выбора min кол-ва опытов, необходимых для отыскания оптимального условия.