Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf

Назначение операторов:

1.«Сжатие» вершин каждого полного контура в узел

(операторы 1— 13 блока 4) или контур-вершину. В результа­ те в рабочем массиве L\ будут зафиксированы новые связи— дуги графа с контур-вершинами.

Рис. 6.5.

2. Упорядочение вершин нового графа. Алгоритм упоря­ дочения рассмотрен в шестом блоке, где каждому полному контуру или контур-вершине присвоен новый порядковый номер. Полные контуры на графе анализируем согласно установленной нумерации. Новые номера фиксируем в мас­ сиве F.

3.Организация цикла для просмотра кодов в массиве контуров К.

4.Просмотр очередного кода (±000, 000,1) в массиве пол­

ных контуров К и анализ его на знак.

5. При знаке «минус» из (/+г)-й ячейки рабочего масси­ ва F выделяется новый порядковый номер и заносится в

148

вляется перенумерация вершин исходного графа. Присвое­ ние новых номеров П кодам массива К и стирание знаков

«минус ».

9.Сортировка мас­ сива полных контуров К по увеличению но­ меров вершин П и и

10.Просмотр ко­ дов массива К и уда­ ление новых номеров П. Присвоение знака

«минус» первому коду каждого полного кон­

тура.

11. Запись кодов массива К на магнит­ ную ленту.

Б л о к 6. Упорядо­ чение вершин на гра­ фе. В основу алгорит­ ма, реализованного в блоке 6, положен из­ вестный метод Форда. Порядковые номера присваиваем тем вер­ шинам графа, у кото­ рых не оказывается входящих дуг. Дуги вычеркиваем только у тех вершин, кото­ рым присвоен очеред­ ной порядковый но­ мер.

Схема вычислений показана на рисунке

6. 6.

Назначение опера­ торов:

1.Очистка нулями ячеек рабочего массива F.

2.Сортировка массива L по возрастанию номеров вер­ шин i и j.

3.Просмотр кодов массива L и накопление в (/+у)-х ячейках массива F числа т, где т — количество дуг, входя­ щих в вершину

4.Миноранте го присваивается по второму адресу в (f-f-

—|—1)-й ячейке порядковый номер, равный единице, и знак

149

4tминус» — признак вычеркивания дуг. Новые номера, при­ сваиваемые вершинам графа, фиксируются в рабочей ячей­ ке Д -fO. В ячейку # + 0 добавляется единица после присвое­ ния очередного нового номера.

5.Организация цикла для просмотра ячеек массива F.

6.Выбор на сумматор содержимого очередной ячейки (/+& ) из F. Для содержимого (f-\-k) проверяем выполнение

оператору 7, в противном случае — к оператору 12.

7.Организация цикла для просмотра кодов массива L.

8.Выделение из очередного кода (i, j, d%) номера i. Ана­

лизируется знак выбранного кода и проверяется условие i= k , где k — номер ячейки (/+& ). При знаке «плюс» и ра­ венстве i = k выполняется оператор 9.

9.В массиве L из кода (i, j, dt ) выделяется индекс j, а в ячейке (/-И ) из F вычитается единица из т. Коду в L и ячейке (/+ ;) из F присваиваются знаки «минус».

10.Анализ на конец кодов массива L. Если в L просмот­

рены не все коды, переходим к оператору 8, в противном слу­ чае — к оператору 11.

11.Ячейке (/+& ) из F присваивается знак «плюс».

12.Анализ на конец массива F. При окончательном про­ смотре всех ячеек из F выполняется оператор 13, в против­

ном случае — оператор 6.

13.Организация цикла для просмотра ячеек массива F.

14.Просмотр очередной ячейки массива F и анализ на

выполнение следующих трех условий: знак «минус», т =

— 0 и iVH0B = 0 . При соблюдении этих условий переходим к оператору 15, в противном случае — к оператору 16.

15. Вершине с номером k по второму адресу в ячейке (/-\-k) из F присваивается новый номер из Д+О. Содержи­ мое ячейки R-j-О увеличивается на единицу. Проводится анализ: (R +0)=2V -f-l (N — количество вершин на графе). Если (# + 0 ) = ЛЧ-1, выполняется оператор 17, в противном случае — оператор 16.

16. Анализ на конец массива F. Если в F просмотрены все ячейки, управление передается оператору 5, в против­ ном случае — оператору 14.

17. Равенство (R + 0 )= iV + l, проверяемое оператором 15, говорит о том, что всем вершинам графа уже даны новые номера. На печать выдаются новые и старые номера для всех вершин графа.

18. Массив L просматривается один раз и все первона­ чальные номера вершин г и j заменяются на новые, зафик­ сированные в ячейках (/+ г) и (/+ ;) массива F.

150

личения и уменьшения номеров вершин i и у, используются в блоке основного счета.

Назначение операторов:

1.Формирование из входной информации кодов массива L: i, у, dt.

2.Осуществление упорядочения вершин на графе, т. е. выполнение операторов бло­

ка 6.

3.Формирование массива L с новыми но­ мерами вершин i и у.

4.Сортировка массива L по возраста­

1.Считывание с МЛ массива L по возрастанию индекса г. Очистка ячеек рабочего массива F.

2.Просмотр кодов (г, у, dt) массива L и запись парамет­

dt. Величины dj находятся в ячейках массива F .

4.Организация цикла для анализа кодов массива К по индексной ячейке 0001.

5.Значение индексной ячейки 0001 фиксируется в 0002. Очередному коду из К присваивается знак «плюс» вместо прежнего знака «минус», свидетельствующего о начале пол­ ного контура.

6.Анализ на знак кодов из массива К. При знаке «плюс» переходим к оператору 7, в противном случае (в момент на­ чала следующего полного контура) — к оператору 9.

7.Для вершин рассматриваемого полного контура на­ капливается сумма временных оценок ti— di.

8.Анализ на конец кодов массива К , уход на операторы

6 или 9.

9.Восстановление первоначального состояния индекс­ ной ячейки 0001 (0002->-0001).

151

10. Анализ знака кода в массиве К по индексной ячей ке 0001. При знаке «плюс» выполняется оператор 12, в про­ тивном случае — оператор 11.

11.Знак «минус» говорит о начале нового полного кон­ тура. В этом случае восстанавливается знак «минус» перед началом предыдущего полного контура по индексной ячей­ ке 0002. Далее переходим к оператору 5.

12.В рабочую ячейку (/-И)» соответствующую вершине

полного контура, записывается код (— 0, iVK0H, 2d*), где 2с?г —

152

сумма величин dt для всех вершин полного контура, 2VK0H— номер контура (номера контурам присваиваются в порядке их следования).

13.Анализ на конец кодов в К. Если все коды из К про­ смотрены, выполняется оператор 14, в противном случае — оператор 10.

14.Восстановление знака «минус» перед началом по­ следнего полного контура. Организация цикла для просмот­ ра кодов массивов L и L". Массив L " включает те же коды, что и массив L, с той лишь разницей, что из дуг, входящих

вконтур-вершину из i, оставлен в массиве L " код только од­ ной вершины. В исходном массиве L вершина i может быть связана сразу с несколькими вершинами одного полного контура. Поэтому после «сжатия» полного контура в узел может оказаться несколько одинаковых кодов. Массив L" формируется как промежуточный рабочий для того, чтобы при получении массива V не пришлось многократно про­ сматривать коды из L и К.

Индекс i первого кода из L записывается в рабочей ячей­

ке .R+0.

15. Просмотр очередного кода (ik, 7ь djk) в L. Индекс ik сопоставляется с номером i из (R-{-0). При сравнении вы­ полняется оператор 17, в противном случае — оператор 16.

16.Очистка ячеек рабочего массива I, в котором фикси­ руется признак входа в каждый полный контур. Массив I занимает только кодовую часть ячеек массива F,

17.Анализ: входит ли в состав полного контура верши­

(см. оператор 12). Если jk принадлежит полному контуру, то выполняется оператор 18, в противном случае — опера­ тор 19.

18.Проверка: была ли входящая дуга из ik-й вершины

вполный контур, которому принадлежит вершина 7*. В дан­ ном случае в ячейке (I-\-NKOu) в кодовой части должен сто­ ять признак входа в контур (единица). Если это условие со­ блюдается, то рассматриваемый в операторе 15 код (ik, 7ь djk) в массив L " включать не надо. При этом выполняется оператор 21, в противном случае — оператор 22.

19.Пересылка кода (ik; 7*> djk) из L в массив L ".

20.Переадресация ячеек массива L".

21.Анализ на конец массива L. Если просмотрены в L все коды, то массив L " сформирован и переходим к операто­ ру 23, в противном случае — к оператору 15.

22.В массив 1 в ячейку (I-\- iVK0H) заносится признак входа в контур с номером iVK0H. Далее выполняется опера­ тор 19.

153