- •Технология подготовки и решения задач с помощью компьютера
- •Базовые конструкции для написания структурированных программ. Способы обращения неструктурированных программ в структурированные.
- •Ввод и вывод данных, оператор присваивания.
- •Условный оператор: группа If
- •Цикл с параметром: группа For
- •Цикл с параметром: While, Repeat
- •Контрольные вопросы:
- •Пошаговая детализация алгоритма
- •Процедуры и функции
- •Контрольные вопросы.
- •Структуры данных: массивы, строки, записи. Размещение в памяти. Пользовательские типы данных.
- •Контрольные вопросы.
- •Модульное программирование. Организация личных библиотек.
- •Контрольные вопросы:
- •Рекурсивные алгоритмы
- •Контрольные вопросы.
- •Сортировка и поиск. Методы внутренней сортировки.
- •Быстрые алгоритмы сортировки
- •Контрольные вопросы
- •Статистическое и динамическое распределение памяти. Динамические структуры данных.
- •Контрольные вопросы.
- •Алгоритмы с возвращением.
- •Поиск в глубину
- •Поиск в ширину
- •Деревья
- •Достижимость
- •Метод построения максимального потока в сети
- •Метод локальной оптимизации
- •Организация файловой системы. Создание и обработка баз данных.
- •Варианты
- •Контрольные вопросы:
- •Библиотечные модули системы программирования Паскаль: Crt, Dos, Graph.
- •Графический режим работы экрана
- •Основные графические функции и процедуры
- •Контрольные вопросы:
- •Комбинаторные алгоритмы.
- •Перебор с возвратом. Общая схема
- •Задача о рюкзаке (перебор вариантов)
- •Задача о коммивояжере (перебор вариантов)
- •Объектно-ориентированное программирование
Поиск в ширину
Идея метода. Суть (в сжатой формулировке) заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины - выбирается та, которая была раньше рассмотрена. Для реализации данного принципа необходима структура данных “очередь”.
Деревья
Деревом называют произвольный связный неориентированный граф без циклов. Его можно определить и по-другому: связный граф, содержащий N вершин и N-1 ребер, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью. Для произвольного связного неориентированного графа G=<V,E> каждое дерево <V,T>, где TE называют стягивающим деревом (каркасом, остовом). Ребра такого дерева называют ветвями, а остальные ребра графа - хордами.
Достижимость
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Простой путь - это путь, в котором каждая дуга используется не более одного раза.
Элементарный путь - это путь, в котором каждая вершина используется не более одного раза.
Если существует путь из вершины графа v в вершину u, то говорят, что u достижима из v. Матрицу достижимостей R определим следующим образом:
R[v,u]=
Метод построения максимального потока в сети
Рассмотрим метод на примере. Пусть дана сеть G=(V,E), узлом-источником является вершина 1, узлом-стоком - вершина 6. Построим максимальный поток (F) между этими вершинами. Начальное значение F нулевое. Очевидно, что структурой данных для описания F является матрица того же типа, что и матрица С, в которой определены пропускные способности дуг.
Первая итерация. Присвоим вершине 1 метку [1,@]. Первый шаг. Рассмотрим дуги, началом которых является вершина 1 - дуги (1,2) и (1,3). Вершины 2 и 3 не помечены, поэтому присваиваем им метки, для 2-й - [1,2] и 3-й - [1,6]. Что представляют из себя метки? Первая цифра - номер вершины, из которой идет поток, вторая цифра - численное значение потока, который можно передать по этой дуге.
Вторая итерация. Первый шаг. Присвоим вершине 1 метку [1,@]. Рассмотрим дуги, началом которых является помеченная вершина 1. Это дуги (1,2) и (1,3). Вершина 2 не может быть помечена, так как пропускная способность дуги (1,2) исчерпана. Вершине 3 присваиваем метку [1,6]. Второй шаг. Выберем помеченную, но не просмотренную вершину. Это вершина 3. Повторяем действия. В результате вершина 4 получает метку [3,2]. Третий шаг. Выбираем вершину 4, только она помечена и не просмотрена. Вершине 6 присваиваем метку [4,1]. Почему только одна единица потока? На предыдущей итерации израсходованы две единицы пропускной способности данной дуги, осталась только одна. Вершина-сток достигнута. Найдена увеличивающая поток цепочка, это 1346, по которой можно ”протащить” единичный поток. Результирующий поток в сети равен 3.
Итак, в чем суть “техники меток” Форда и Фалкерсона? Первое. На каждой итерации вершины сети могут находиться в одном из трех состояний: вершине присвоена метка, и она просмотрена; вершине присвоена метка, и она не просмотрена, то есть не все смежные с ней вершины обработаны; вершина не имеет метки. Второе. На каждой итерации мы выбираем помеченную, но не просмотренную вершину v и пытаемся найти вершину u, смежную с v, которую можно пометить. Помеченные вершины образуют множество вершин сети G, достижимые из вершины-источника. Если среди этих вершин окажется вершина-сток, то это означает успешный результат поиска цепочки, увеличивающей поток, при неизменности этого множества работа заканчивается - поток изменить нельзя.
Алгоритм. Входные данные. Описание сети G=(V,E) матрицей пропускных способностей С[1..N,1..N], где N - количество вершин. Вершина-источник s и вершина-сток t. Выходные данные. Поток, описываемый матрицей F[1..N,1..N]. Рабочие переменные. Структура данных для хранения меток - P[1..N,1..2]. Элемент P[i,1] - номер вершины, из которой можно передать поток, равный P[i,2], в вершину с номером i. Логическая переменная Lg, значение true - есть цепочка, увеличивающая поток, false - нет.
Основная логика.
begin
<ввод данных и инициализация переменных(Lg:=true)>;
while Lg do begin
FillChar(P,SizeOf(P),0);
<процедура расстановки меток(Mark), если вершину t не смогли пометить, то Lg:=false; результат работы - значение P (метки вершин) >;
if Lg then <процедура Stream(t) - изменение потока по дугам найденной цепочки от вершины-стока t до вершины-источника s; входные данные - массив P, результат - измененный массив F>;
end;
<вывод потока F>;
end.{конец обработки}
Уточним логику расстановки меток (нелучший вариант).
procedure Mark;
var M:set of 1..N;i,l:integer;
begin
M:=[1..N]; {непросмотренные вершины}
P[s,1]:=s;P[s,2]:=maxint;{присвоим метку вершине-источнику}
l:=s;
while (P[t,1]=0) and Lg do begin
for i:=1 to N do {поиск непомеченной вершины}
if (P[i,1]=0) and ((C[l,i]<>0) or (C[i,l]<>0)) then
if F[l,i]<C[l,i] then begin{дуга прямая?}
P[i,1]:=l; if P[l,2]<C[l,i]-F[l,i] then P[i,2]:=P[l,2]
else P[i,2]:=C[l,i]-F[l,i]; end
else if F[i,l]>0 then begin{дуга обратная?}
P[i,1]:=-l;
if P[l,2]<F[i,l] then P[i,2]:=P[l,2] else P[i,2]:=F[i,l]; end;
M:=M-[l];{вершина с номером l просмотрена}
l:=1;{находим помеченную и непросмотренную вершину}
repeat Inc(l) until (l>N) or ((P[l,1]<>0) and (l in M));
if l>N then Lg:=false; end; end;
Логика изменения потока F имеет вид:
procedure Stream(q:integer);
begin
{определяем тип дуги - прямая или обратная, знак минус у номера вершины - признак обратной дуги}
if P[q,1]>0 then F[P[q,1],q]:=F[P[q,1],q]+P[t,2]
else F[q,abs(P[q,1])]:=F[q,abs(P[q,1])]-P[t,2];
{если не вершина-источник, то переход к предыдущей вершине цепочки}
if abs(P[q,1])<>s then begin
q:=abs(P[q,1]);Stream(q);end; end;
Итак, рассмотрение метода построения максимального потока в сети завершено.