149310 (Организация строительства и управление качеством), страница 8

** Показатель емкостей сооружений, м³;

*** Размер сооружений в плане.

Оглавление

Мобильные ( инвентарные ) сооружения канализации заводского изготовления.

* Показатель мощности сооружений, м³/сут.

** Размер сооружений.

Оглавление

Алгоритмы построения n-перестановок.

(Из кн. В.В. Шкурба Задача трёх станков, стр. 23…27) σ_n

Однако, чтобы «улучшать» метод перебора, нужно, прежде всего, уметь им пользоваться—для задач поиска эк­стремальных перестановок это означает уметь строить все возможные «-перестановки, другими словами, надо знать алгоритм построения всех n-перестановок.

Нетрудно после некоторых попыток «нащупать» элементарный регулярный прием получения последо­вательности всех n!-перестановок (чем мы уже неявно воспользовались при формировании табл. 3 из преды­дущего пункта), начиная с начального упорядочения чисел 1, 2, ..., п по возрастанию (пусть п=5):

1, 2, 3, 4, 5

1, 2, 3, 5, 4

1, 2, 4, 3, 5

1, 2, 4, 5, 3

1, 2, 5, 3, 4

1, 2, 5, 4, 3

1, 3, 2, 4, 5

Чтобы попроще описать найденный прием, введем некоторые понятия.

Пару соседних чисел (в перестановке) назовем упорядоченной, если первое число в паре меньше

второго.

Рассмотрим некоторую перестановку Оп. Найдем первую с конца перестановки упорядоченную пару. Так в перестановке σ_n =(1, 3, 5, 4, 2) первая с конца упорядоченная пара есть пара (3, 5). Первое число такой пары назовем обрывающим. Перестановочный хвост в σ_n образует последовательность чисел, начи­ная с обрывающего.

Реупорядочить перестановочный хвост означает:

1) заменить обрывающее число на наименьшее из перестановочного хвоста число, превосходящее обрывающее;

Рис. 7. Блок-схема Алгоритма-1 получения всех n-перестановок.

2) все остальные числа из перестановочного хво­ста (вместе с обрывающим) расположить в порядке возрастания.

Так в нашей перестановке σ_n= (1, 3, 5, 4, 2) об­рывающее число есть 3, перестановочный хвост есть последовательность (3, 5,4, 2).

Заметим, что обрывающего числа не найдется только в перестановке, в которой все числа располо­жены в порядке убывания. В нашем алгоритме это сигнал того, что решение закончено.

Введение понятий «обрывающего числа», «пере­становочного хвоста», «реупорядочения» позволяет упростить описание алгоритма построения всех га-пе-рестановок. Этот алгоритм — назовем его Алгоритмом-1—представлен блок-схемой на рис. 7. Получе­ние первых нескольких перестановок по этому алго­ритму отображено в табл. 4.

Таблица 4

Первые 6 перестановок, полученные согласно Алгоритму-1

Нетрудно убедиться в том, что Алгоритм-1 дей­ствительно решает поставленную задачу. Этот факт очевиден для п == 1, можно проверить и для га == 2. Пусть это верно для (n— 1), т.е. алгоритм действи­тельно получает все различные перестановки в случае п — 1 элементов. Но если применить этот алгоритм для п элементов, то цифра 1, стоящая на первом ме­сте в исходной перестановке, будет заменена на 2, только когда она станет обрывающим числом, т. е. когда будут получены все (п—1)! различных пере­становок остальных чисел. Точно так же цифра 2 на первом месте в перестановках будет заменена на 3 только после получения всех (п— I)! различных пе­рестановок остальных элементов и т. д. Это и озна­чает, что алгоритм получает все п-(п—1)! переста­новок, при этом среди них не будет совпадающих.

Другой алгоритм — Алгоритм-2 — получения всех n-перестановок представлен блок-схемой на рис. 8.

Рас. 8. Блок-схема Алгоритма-2 получения всех n-перестановок.

Только один термин в блок-схеме рис. 8 нуждается в пояснении.

Назовем «вращением» некоторой последователь­ности А чисел замену ее другой последовательностью В, где число, стоящее в А на первом месте, оказы­вается в В на последнем месте, взаимное расположение других чисел не меняется. Так вращение (1, 2, 3) приводит к (2,3, 1).

Табл. 5 поясняет ход решения по этому алгоритму при получении первых нескольких перестановок.

Таблица 5

Первые перестановки, полученные согласие Алгоритму-2

У п р .а ж н е н и е II*. Понравилось ли вам изложение Ал­горитма-1? Могли бы вы улучшить его разъяснение? Могли бы вы доказать, что по Алгоритму-2 действительно получают все n-перестановки?

Упражнение 12*. Не могли бы вы предложить алго­ритм получения всех n-перестановок, отличный от изложенных? Уверены ли вы, что по этому алгоритму можно получить дей­ствительно все перестановки? Оглавление

Табличный метод расчёта сетевых моделей (графиков)

(Временные указания по составлению сетевых графиков и применению их в управлении строительством

Стр. 32…37)

Приложение 4

РАСЧЕТ СЕТЕВЫХ ГРАФИКОВ ВРУЧНУЮ

А. МЕТОДИКА РАСЧЕТА ГРАФИКА В ТАБЛИЧНОЙ ФОРМЕ

Рис.1.

Расчет критического пути и резервов времени ведется в табличной 'форме (таблица 1).

Для ручного счета события в сетевом графике нумеруются следующим образом: номер предшествующего собатия должен быть меньше номера последующего события. После нумерации событий шифр (код) работ заносится в графу 8, Причем шифр работ заносится в возрастающем порядке (выписываются все работа, "выходящие" из первого события, затем из второго и т.д.). В графу 1 таблицы заносится количество работ, пред­шествующих данной работе, т.е. количество работ, "входящих" в ее начальное событие. Продолжительность работ проставляется на основании исходных данных.

Таблица 1

После заполнения первых трех граф переходят к опреде­лению раннего начала и раннего окончания работ.

Раннее начало работ, "выходящих" из первого события равно нулю. Раннее окончание любой ра&оты равно сумме ее раннего начала и продолжительности.