Оглавление
Введение. 3
1. Теоретическая часть. 5
1.2 Основные определения и теоремы.. 5
1.2 Нахождение максимального пропускного потока. 8
1.3 Сводимость некоторых задач о максимальном потоке в сети к
рассматриваемой 10
1.4 Алгоритм Форда-Фалкерсона. 12
2. Практическая часть. 16
2.1 Алгоритм решения. 16
2.2 Работа с программой. 18
2.3 Расчёт потока. 20
2.4 Тестирование. 22
Заключение. 26
Задача о максимальном
потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной
практической значимостью этой проблемы. Методы решения задачи применяются на
транспортных, коммуникационных, электрических сетях, при моделировании
различных процессов физики и химии, в некоторых операциях над матрицами, для
решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве
крупнейших университетов мира.
60 лет назад, эта задача
решалась simplex методом линейного программирования,
что было крайне не эффективно. Форд и Фалкресон
предложили рассматривать для решения задачи о максимальном потоке
ориентированную сеть и искать решение с помощью итерационного алгоритма. В
течение 20 лет, все передовые достижения в исследовании данной задачи
базировались на их методе. В 1970г. наш соотечественник, Диниц,
предложил решать задачу с использованием вспомогательных бесконтурных
сетей и псевдомаксимальных потоков, что намного
увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница,
введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и
исследования Форда и Фалкерсона, внесли огромный
вклад в решение данной проблемы. На основе их методов 15 лет достигались
наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод,
который также без раздумий можно отнести к
фундаментальным. Этот метод был разработан Голдбергом
и Таряном, и получил название Push-Relabel метода. Для нахождения максимального
потока, он использует предпотоки и метки, изменяемые
во время работы алгоритма. Push-Relabel алгоритмы очень
эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную
длину. Это самый современный из всех известных мне алгоритмов. Асимптотическая
оценка его быстродействия превзошла O(nm), о такой скорости многие годы можно
было только мечтать. Уверен, что за прошедшие годы алгоритм Голдберга
и Рао тщательно изучался и улучшался.
К сожалению, в России, в
настоящее время, передовые алгоритмы освещаются слабо. Во всех русскоязычных
учебниках, рассматривающих задачу о максимальном потоке в сети, вы вряд ли
встретите что-либо, кроме метода пометок Форда-Фалкерсона
60-летней давности. В то время как в зарубежной литературе им редко
ограничиваются.
В этой работе рассматривается
и применение метода Форда-Фалкерсона для выделения Web-групп в WWW.
В этой главе приведены
определения и теоремы без доказательства.
Рассмотрим орграф G = (V, E), где V – множество вершин, E – множество ребер. |V| = n, |E| = m. Под сетью понимается пара S = (G, c), где c: ER – функция, ставящая каждой дуге в соответствие положительное
вещественное число – пропускную способность.
Вы делим в сети 2
вершины: s (источник) и t (сток).
Назовем функцию f: ER потоком в сети
S, если она удовлетворяет следующим
условиям:
1.(v, u)E, 0 f(v, u) c(v, u) – ограничение, накладываемое пропускной способностью дуги.
2.vV \ {s, t},
- закон сохранения потока,
, .
Величиной потока f, назовем Div(s).
Под максимальным
потоком сети понимается поток из s в t максимальной величины.
Разрезом P(W) сети S, где WV (W, WV), назовем множество дуг (u, v)E, таких, что u V и vV\W.
Поток через разрез
определяется так: f(W, V\W) .
Под пропускной
способностью разреза понимается .
Минимальным разрезом сети называется произвольный разрез P(W), sW и tV\W с минимальной
пропускной способностью.
Дадим следующие теоремы
без доказательства:
1.
Если sW и tV\W, то величина
потока из s в t равна
f(W, V\W) – f(V\W, A).
2.
Величина каждого потока из s в t не превосходит пропускной
способности минимального разреза, разделяющего s и t,
причем существует поток, достигающий этого значения. (Теорема
Форда-Фалкерсона).
Допустимой дугой e = (u, v) относительно
потока f назовем дугу, для которой
выполняется одно из двух следующих условий:
а). e = (u, v) и f(e) < c(e).
б). e = (v, u) и f(e) > 0.
Если для допустимой дуги
выполнено первое условие, назовем ее согласованной, иначе не
согласованной.
Увеличивающей цепью (длины l) из s в t называется произвольная
знакопеременная последовательность (попарно различных) вершин и дуг: v0, e1, v1, e2, v2, …, vl-1, el, vl , где v0 = s, vl = t, для всех il. Все дуги должны быть допустимы.
Зная
увеличивающую цепь, мы можем увеличить поток в этой цепи на
,
где
Чтобы увеличить поток,
необходимо увеличить его значение на в каждой согласованной дуге цепи и уменьшить
в каждой несогласованной.
Следующие 3 условия
эквивалентны:
1.
Поток из s в t максимален.
2. Не
существует увеличивающей цепи для f.
3.
Величина потока равна c(W, V\W) для некоторого WV, такого, что sW, а tW.
Теорема о
Декомпозиции.
Любой поток из s в t можно разделить на следующие примитивы:
а). Цепь из s в t с потоком величины .
б). Циклы с потоком
величины .
Поток может распасться не
более чем на m примитивов.
Заметим,
во-первых, что это задача линейного программирования, так что ее можно решать
симплекс-методом. Более того, теорема о максимальном потоке и минимальном
разрезе - в точности теорема двойственности для задачи линейного
программирования.
Но для этой конкретной задачи есть
более просто описываемый алгоритм - алгоритм Форда-Фалкерсона (в сущности, это
и есть симплекс-метод, примененный в конкретной ситуации).
Алгоритм
требует большого количества итераций. Найдем сначала хоть какой-то поток
ненулевого веса (нужно найти путь из истока в сток, желательно, с максимальным
весом (чтобы алгоритм быстрее работал); можно для этого применить
соответствующим образом модифицированный алгоритм Дейкстры).
После этого
на каждом шаге алгоритма смотрим, можем ли мы модифицировать наш поток так,
чтобы его вес стал больше. Если так модифицировать нельзя, то мы нашли
максимальный поток.
Модификация
заключается в следующем. Попытаемся "прибавить" к нашему потоку
новый. Для этого рассмотрим новый граф с теми же вершинами, но новыми
пропускными способностями ребер: если пропускная способность ребра от вершины A
к вершине B равна c, а в нашем потоке по этому ребру пущено x, то в новом графе
есть ребро от A к B с пропускной способностью c-x и ребро от B к A с пропускной
способностью x (грубо говоря, мы можем увеличить поток по этому ребру максимум
на c-x или уменьшить максимум на x).
После этого в
новом графе ищем какой-нибудь поток из истока в сток ненулевого веса (снова
можно применить что-нибудь вроде Дейкстры). Если такого нет - ура, тот поток,
который у нас был - максимальный. Если есть - складываем эти два потока,
получаем новый, с большим весом. Повторяем процесс.
К сожалению,
этот алгоритм (как и симплекс-метод) не гарантирует, что время работы
полиномиально (если нет ограничений на пропускные способности). В подавляющем
большинстве случаев это так, но можно придумать "плохие" примеры, для
которых время работы будет экспоненциальным (но в практических задачах они вряд
ли встретятся).
Если
известно, что пропускные способности ребер - "небольшие" целые числа,
то алгоритм действительно работает за O(N3).
Большинство разнообразных
сетей и условий существования потока в них, которые могут возникнуть при
рассмотрении различных приложений задачи о максимальном потоке, сводятся к
поиску максимального потока в ориентированной сети с одним источником и стоком,
и заданными вещественными верхними границами пропускных способностей дуг сети.
Рассмотрим наиболее распространенные частные случаи, которые могут быть
приведены к оригинальной постановке задачи.
Случай нескольких
источников и стоков.
В этом случае все узлы
сети делятся на 3 группы: S - множество источников, T – множество стоков и R - множество промежуточных узлов. Поток может следовать из
любого источника в любой сток. В этом случае сеть модифицируется следующим
образом:
Добавим новую вершину S* и соединим ее дугами со всеми вершинами из множества S. Вершина S* называется суперисточником.
Добавим новую вершину T* и соединим ее дугами со всеми
вершинами из множества T.
Вершина T* называется суперстоком.
Пропускные способности всех новых дуг положим равными ∞.
Очевидно, что поиск
максимального потока из вершин множества S в вершины множества T равносилен поиску максимального потока из S* в T*.
Случай ограниченной
пропускной способности вершин.
Если пропускные
способности наряду с дугами имеют и узлы сети, то каждую вершину v, имеющую пропускную способность c(v), следует заменить двумя (v’ и v’’),
соединенными дугой (v’, v’’) и c(v’, v’’) = c(v).
Случай существования
нижних границ пропускных способностей дуг.
Если рассматриваемой
задаче поток, проходящий по дуге u,
может принимать значения l(u) ≤ f(u) ≤ c(u), то функция l(u) рассматривается как уже имеющийся в
сети поток и поиск максимального потока следует начинать не с нулевого потока,
а с потока l(u).
Случай
неориентированных и смешанных сетей.
Поток по неориентированной
дуге (v, w) должен удовлетворять следующим условиям:
f(v, w) ≤ c(v, w)
f(w, v) ≤ c(v, w)
f(v, w)*f(w, v) = 0
В этом случае замена
неориентированной дуги двумя противоположно направленными ориентированными
дугами с одинаковой пропускной способностью c(c, w) сведет задачу к эквивалентной
задаче на орграфе. Аналогично ориентированные сети сводятся к неориентированным. (Кроме сетей с единичными пропускными
способностями).
Пропускные способности
различных типов.
Различаются случаи
целочисленных, вещественных и единичных пропускных способностей.
Предполагается, что приводимые далее алгоритмы рассматриваются на сетях с
вещественными пропускными способностями, кроме специально оговоренных случаев.
Впервые был предложен в 1956г.
До этого времени задача решалась с помощью методов линейного программирования,
что было крайне не эффективно. Алгоритм является псевдополиномиальным и имеет
оценку O(nm log U), где m = |E|, n = |V|, U = max(Cij).
Алгоритм начинает свою
работу с нулевого потока и на каждой своей итерации увеличивает поток в сети.
На каждом шаге находится увеличивающая величину потока цепь. Поток
увеличивается вдоль дуг этой цепи, пока она не станет насыщенной.
Увеличивающей цепью
является цепь из источника в сток, все дуги которой допустимы. Дугу из вершины
a в вершину b назовем допустимой, если выполняется одно из следующих условий:
1. f(e) < c(e) и
дуга согласованна
2. f(e) > 0 и
дуга несогласованна
По увеличивающей цепи
можно пустить поток величины Q, где Q = min{q(ei), 1 ≤ i
≤ l} и q(e) = {с(e) – f(e), если дуга согласованна, f(e), если дуга не
согласованна}. Для того, чтобы увеличить величину потока сети на Q, необходимо
увеличить на Q поток на каждой согласованной дуге цепи и уменьшить на каждой
несогласованной.
В своей работе Форд и
Фалкерсон (Ford and Fulkerson) доказали, что поток в сети, для которой нельзя
построить увеличивающую цепь, является максимальным.
Для нахождения
увеличивающей цепи ими был предложен “Метод расстановки пометок”. Процесс расстановки
меток начинается в источнике сети и заканчивается в ее стоке. Как только сток
оказался помеченным, мы можем говорить о существовании увеличивающей цепи из
источника в сток. Метка, “наносимая” на вершины сети, содержит необходимый
минимум информации, достаточный для того, чтобы восстановить эту цепь и
определить величину, на которую можно изменить поток в ней. Вершина сети может
находиться в одном из 3-х состояний: “непомеченная”, “помеченная” и
“просмотренная”.
Этап 1. Расстановка
меток.
Все вершины получают
статус непомеченных.
Процедура расстановки
меток.
Возьмем произвольный
помеченный, но не просмотренный узел x. Пусть он имеет пометку [i, +, e(x)],
где i – вершина из которой был помечен x; флаг, показывающий, что дуга (i,x)
согласованна; e – величина потока, который можно пропустить по этой дуге.
Рассмотрим все непомеченные смежные вершины y, такие что дуга (x, y)
согласованна. Пометим вершину y меткой [x, +, e(y)], где e(y) = min{e(x) , c(x,
y) – f(x, y)}. Затем рассмотрим все непомеченные смежные вершины y, соединенные
с ней несогласованной дугой. Пометим их меткой [x, -, e(y)], где e(y) =
min{e(x), f(y,x)}. Теперь все рассмотренные узлы y имеют статус помеченных, а
узел x - просмотренный.
Эта общая для всех узлов
сети процедура. Пометим источник меткой [~, ~, ∞] и будем последовательно
вызывать ее для всех смежных узлов, постепенно двигаясь по сети. Как только
процедура будет вызвана для стока, будет получена увеличивающая цепь и следует
перейти ко второму этапу. В противном случае процедура будет вызываться, пока
все помеченные вершины не станут просмотренными, и если сток сети не был
достигнут – увеличивающая цепь не может быть построена и по теореме
Форда-Фалкерсона имеющийся поток сети является максимальным.
Этап 2. Изменение
потока.
Процедура изменения
потока дуги.
Возьмем узел x. Если он
имеет метку [y, +, e], то увеличим поток по дуге (y, x) на e. Если он имеет
метку [y, -, e], то уменьшим поток по дуге (y, x) на e. Если y не является
источником, то вызовем процедуру для узла y.
Эта процедура, будучи
вызвана для стока сети, позволяет пройти по найденной увеличивающей цепи к
стоку, изменяя поток на ее дугах.
Следует особо отметить,
что узлы, имеющие статус “помеченных”, больше не участвуют в процессе поиска
увеличивающей цепи, весьма эффективно с вычислительной точки зрения.
Алгоритм Форда-Фалкерсона
гарантирует нахождение максимального потока только в сетях с целочисленными
пропускными способностями. На практике “чистый” алгоритм Форда-Фалкерсона не
применяется, т.к. оценка его производительности зависит от величины пропускных
способностей дуг сети. Все дело в том, что в нем не дается каких либо правил
выбора увеличивающей цепи.
Рассмотрим сеть на
рисунке 1. Предположим, что реализован алгоритм, отдающий предпочтение
увеличивающим цепям максимальной длины. В этом случае на первом шаге мы пустим
дополнительный поток по цепи (0,1),(1,2),(2,3).
Рисунок 1 –
Исходные данные
Рисунок 2 –
Шаг 1
На втором шаге выберем
цепь (0,2),(2,1),(1,3). Так как дуга (2,1) несогласованна, величина пущенного
по ней потока будет вычитаться из величины потока, полученного на предыдущем
шаге. Мы получили сеть (рисунок 3) практически эквивалентную исходной.
Рисунок 3 –
Шаг 2
Очевидно, что для
нахождения максимального потока понадобиться 1000 итераций! В то время, как
если бы мы на первом шаге выбрали цепь (0,1),(1,3), то результат был бы получен
за одну итерацию! На практике, величина пропускных способностей часто зависит
от единиц измерения, и может принимать огромные значения. Если же допустить
иррациональные пропускные способности дуг, то можно привести пример
невычислимой сети. Величина потока в такой сети не превысит даже четверти
истинного значения. Подобная неопределенность длилась не долго, уже в начале
70-х г. были предложены сразу 2 правила выбора увеличивающих цепей, которые
существенно улучшают алгоритм Форда-Фалкерсона.
Для решения задачи была
выбрана среда программирования Delphi
7 Studio.
С помощью неё была
разработана программа, автоматически определяющая максимальный поток в заданном
в условии задачи графе (см. рис 1).
Рисунок 4 –Исходный граф
Ниже приведён алгоритм решения задачи.
Рисунок 5 – Алгоритм решения задачи
Для работы с программой
запустите файл potok.exe. После запуска программы будет
показано окно следующего вида:
Рисунок 6 - окно программы.
Окно программы состоит:
1.
Рисунок графа с
элементами установки пропускных значений.
2.
Матрица дуг графа
и их пропускных способностей (является представлением графа в табличном виде).
3.
Матрица текущего
потока (представление вычисляемого потока итерации в табличном виде).
4.
Таблица
просчитанных и тупиковых ветвей потока.
5.
Индикатор
просчитываемой дуги.
1.
Значение
максимального общего потока на данном этапе вычислений.
6.
Кнопка «Принять»
(кнопка получение исходных данных ).
2.
8.Кнопка расчёт
(кнопка запуска автоматического расчёта максимального потока в графе).
Для того чтобы рассчитать поток
необходимо выполнить следующие действия:
- указать значения пропускных
способностей графа (по умолчанию установлены контрольные значения проверочного
счёта);
- нажать кнопку «Принять». Данные из
графа будут занесены в матрицу (см. рисунок 7)
Рисунок 7 – Занесение данных в матрицу.
- Нажать кнопку «Расчёт»
В течение некоторого
времени программа будет выполнять вычисления. Следить заходом вычисления можно,
наблюдая изменения значений матриц и таблицы рассчитанных потоков.
Об окончании вычисления
программа сообщить характерным звуком.
После окончания
вычислений можно просмотреть просчитанные потоки и полученное максимальное
значение общего потока (см. рисунок 8).
Рисунок 8- Вычисление окончено.
2.4 Тестирование
В качестве тестирования, проведем
контрольный просчет. Начальный граф представлен на рисунке 1:
Рисунок 9 – Начальный граф
Итерация 1.
Движение начинается из вершины 1 по дуге с максимальной
пропускной способностью, т.е. по дуге (1;3) в вершину 3. Из вершины 3 вновь
проводится выбор дуги с наибольшей пропускной способностью. Такой дугой
является дуга с пропускной способностью b32=6, ведущая в вершину 2. Из вершины 2 выходят две дуги: (2;5)
и (2;6) – с равными пропускными способностями. Выбираем вершину 5, из которой
выходит лишь одна дуга – дуга, ведущая в вершину 7. Поток F1 равен наименьшей пропускной способности из
пройденного пути, т.е.
F1 = min (1-3-2-5-7) = min (10;6;2;15)=2.
Переписываем граф в соответствии с введенным потоком:
Рисунок 10 – Итерация 1
Итерация 2.
Вновь движемся из вершины 1 в вершину 7, выбирая путь так,
чтобы пропускная способность дуг была максимальной, и вычисляем значение потока
по этому пути:
F2 = min (1-3-2-6-7)
= min (10;4;2;7) = 2
Fmax= F1+
F2=2+2=4
Вновь переписываем граф, вычитая из пропускных способностей
пройденных дуг размер потока текущей итерации:
Рисунок 11 – Итерация 2
Итерация 3.
По такому же принципу выбираем новый путь из вершины 1 в
вершину 7, и находим размер потока:
F3 = min (1-3-6-7) = min
(8;3;5) = 3,
Fmax=4+3=7.
Переписываем граф, вычитая из пропускных способностей
пройденных дуг, размер пропущенного через них потока х1-7=3:
Рисунок 12 – Итерация 3
Итерация 4.
Следующий путь проходит через вершины 1, 3, 4, 5, 7. Для него
пропускная способность будет равна
F4 = min (1-3-4-5-7) = min (5;2;3;13) = 2,
Fmax =7+2=9
Переписываем граф, изменяя пропускные способности:
Рисунок 13 – Итерация 4
Итерация 5.
Выбираем следующий путь: 1-4-5-7.
Находим размер потока:
F5 = min (1-4-5-7) = min (4;1;11) = 1,
Fmax=9+1=10.
Вновь переписываем граф:
Рисунок 14 – Итерация 5
Больше не осталось путей, ведущих из вершины 1 в вершину 7,
поэтому решение можно считать законченным, а максимальный размер потока из начальной
вершины в конечную – найденным.
Fmax = 10.
В результате работы над
решением данной задачи была спроектирована и реализована программе наглядно
демонстрирующая работу алгоритма нахождения максимального потока в графе.
Правильность найденного решения подтверждают контрольные вычисления.
Среди достоинств
программы следует отметить, что она может рассчитать максимальный поток для
любых пропускных способностей дуг данного графа. Также следует отметить
достоинство реализованного алгоритма в том, что при небольшой модернизации, а
именно добавлении возможности задать переходы между вершинами поставив нули,
где переход не существует, есть возможность получить универсальную программу
позволяющую рассчитать в максимальный поток в любом графе из семи вершин.
Список литературы
1. Вентцель Е.С. Исследование операции:
задачи, принципы, методология.
2. Аронович А.Б., Афанасьев М.Ю.,
Суворов Б.П. Сборник задач по исследованию операций.
3. Морозов В.В., Сухарев А.Г., Федоров
В.В. Исследование операций в задачах и упражнениях.
4. Шикин Е.В., Чхартишвилли А.Г.
Математические методы и модели управления.
Приложение А . Листинг программы
unit Unit1;
interface
uses
Windows,
Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs,
StdCtrls, ExtCtrls, Grids;
type
TForm1 =
class(TForm)
Panel1:
TPanel;
Image1:
TImage;
Edit1:
TEdit;
Edit2:
TEdit;
Edit3:
TEdit;
Edit4:
TEdit;
Edit5:
TEdit;
Edit6:
TEdit;
Edit7:
TEdit;
Edit8:
TEdit;
Edit9:
TEdit;
Edit10:
TEdit;
Edit11:
TEdit;
Edit12:
TEdit;
Button1:
TButton;
StringGrid1: TStringGrid;
StringGrid2: TStringGrid;
Label1:
TLabel;
Label2:
TLabel;
Edit13:
TEdit;
Label3:
TLabel;
Edit14:
TEdit;
Edit15:
TEdit;
Label4:
TLabel;
StringGrid3: TStringGrid;
Button2:
TButton;
Timer1:
TTimer;
procedure
FormCreate(Sender: TObject);
procedure
Button1Click(Sender: TObject);
procedure
Button2Click(Sender: TObject);
procedure
Timer1Timer(Sender: TObject);
private
{ Private
declarations }
public
{ Public
declarations }
end;
var
Form1:
TForm1;
var
a:array[1..7,1..7] of integer;
z:array[1..7,1..7] of integer;
x:array[1..100,1..7,1..7] of integer;
i,j,mx,dug,dugl,dugll, potmax,df:integer;
implementation
{$R *.dfm}
procedure
refreshmx();
var
ri,rj:integer;
//Обновить
begin
for rj:=1 to
7 do
for ri:=1
to 7 do
form1.StringGrid1.Cells[rj,ri]:=inttostr(a[rj,ri]);
for rj:=1 to
7 do
for ri:=1
to 7 do
form1.StringGrid2.Cells[rj,ri]:=inttostr(z[rj,ri]);
end;
procedure
tupik(tp:integer);
var
ti,tj:integer;
//поиск тупиковых потоков
begin
mx:=mx+1;
form1.StringGrid3.RowCount:=mx;
df:=0;
for ti:=1
to 7 do
a[ti,tp]:=0;
dug:=1;
dugl:=1;
for tj:=1 to
7 do
for ti:=1
to 7 do
z[tj,ti]:=0;
end;
procedure
cr_potok;
//поиск максимального потока
var
ri,rj,crm:integer;
begin
df:=0;
crm:=100000;
for rj:=1 to
7 do
for ri:=1
to 7 do
if
(z[rj,ri]<crm)and(z[rj,ri]>0) then
begin
crm:=z[rj,ri];
end;
for rj:=1 to
7 do
for ri:=1
to 7 do
if
(z[rj,ri]<>0) then
begin
a[rj,ri]:=a[rj,ri]-crm;
z[rj,ri]:=crm;
end;
mx:=mx+1;
form1.StringGrid3.RowCount:=mx;
for rj:=1 to
7 do
for ri:=1
to 7 do
begin
x[mx,rj,ri]:=z[rj,ri];
z[rj,ri]:=0;
end;
dug:=1;
dugl:=1;
df:=0;
potmax:=potmax+crm;
form1.Edit2.Text:=inttostr(a[1,2]);
form1.Edit1.Text:=inttostr(a[1,3]);
form1.Edit4.Text:=inttostr(a[1,4]);
form1.Edit9.Text:=inttostr(a[2,5]);
form1.Edit12.Text:=inttostr(a[2,6]);
form1.Edit5.Text:=inttostr(a[3,2]);
form1.Edit3.Text:=inttostr(a[3,4]);
form1.Edit7.Text:=inttostr(a[3,6]);
form1.Edit6.Text:=inttostr(a[4,5]);
form1.Edit10.Text:=inttostr(a[5,7]);
form1.Edit8.Text:=inttostr(a[6,5]);
form1.Edit11.Text:=inttostr(a[6,7]);
end;
procedure
TForm1.FormCreate(Sender: TObject);
begin
for i:=1 to
7 do
begin
form1.StringGrid1.Cells[0,i]:=inttostr(i);
form1.StringGrid1.Cells[i,0]:=inttostr(i);
form1.StringGrid2.Cells[0,i]:=inttostr(i);
form1.StringGrid2.Cells[i,0]:=inttostr(i);
end;
end;
procedure ref;
//Обновление данных
var
imax,jmax,max:integer;
begin
j:=dug;
dugll:=dugl;
dugl:=dug;
max:=0;
for i:=1 to 7
do
begin
if
a[j,i]>max then
begin
max:=a[j,i];
imax:=i;
jmax:=j;
dug:=i;
end;
//refreshmx;
end;
form1.Edit13.Text:=inttostr(dug);
form1.Edit14.Text:=inttostr(dugl);
if dug=dugl
then
if
dug<>7 then tupik(dug)
else
cr_potok
else
begin
z[jmax,imax]:=max;
form1.StringGrid3.Cells[df,mx]:=inttostr(jmax)+'-'+inttostr(imax);
df:=df+1;
end;
form1.Edit15.Text:=inttostr(potmax);
refreshmx;
end;
procedure
TForm1.Button1Click(Sender: TObject);
begin
form1.Timer1.Enabled:=true;
form1.Enabled:=false;
end;
procedure
TForm1.Button2Click(Sender: TObject);
begin
a[1,2]:=strtoint(form1.Edit2.Text);
a[1,3]:=strtoint(form1.Edit1.Text);
a[1,4]:=strtoint(form1.Edit4.Text);
a[2,5]:=strtoint(form1.Edit9.Text);
a[2,6]:=strtoint(form1.Edit12.Text);
a[3,2]:=strtoint(form1.Edit5.Text);
a[3,4]:=strtoint(form1.Edit3.Text);
a[3,6]:=strtoint(form1.Edit7.Text);
a[4,5]:=strtoint(form1.Edit6.Text);
a[5,7]:=strtoint(form1.Edit10.Text);
a[6,5]:=strtoint(form1.Edit8.Text);
a[6,7]:=strtoint(form1.Edit11.Text);
mx:=0;
dug:=1;
dugl:=1;
refreshmx();
end;
procedure
TForm1.Timer1Timer(Sender: TObject);
var
g,ch,f:integer;
begin
timer1.Enabled:=true;
ref;
ch:=0;
for g:=1 to
7 do
ch:=ch+a[1,g];
if ch=0
then
begin
form1.Enabled:=true;
timer1.Enabled:=false;
beep();
end;
end;
end.