Организация строительства и управление качеством (стр. 14 из 22)
** Размер сооружений.
Оглавление
Алгоритмы построения 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, 3, 4, 5) | 4 | (4, 5) - | ––> (5, 4) |
| 2 | (1, 2, 3, 5, 4) | 3 | (3, 5, 4) - | —>• (4, 3, 5) |
| 3 | (1, 2, 4, 3, 5) | 3 | (3, 5) - | ––> (5, 3) |
| 4 | (1, 2, 4, 5, 3) | 4 | (4, 5, 3)- | ––> (5, 3, 4) |
| 5 | (1, 2, 5, 3, 4) | 3 | (3, 4) - | ––> (4, 3) |
| 6 | (1, 2, 5, 4, 3) | 2 | (2, 5, 4, 3) - | —>(3, 2, 4, 5) |
Нетрудно убедиться в том, что Алгоритм-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
| № | Перестановка | Вращаемая часть | Результат вращения | ||||||
| 1 | (1, 2, 3, 4, 5) | т | =5:(1, 2, 3, 4, 5) | (2, 3, 4, 5, 1) | |||||
| 2 | (2, 3, 4, 5, ) | т | =5: (2, 3, 4, 5, 1) | (3, 4, 5, 1, 2) | |||||
| 3 | (3, 4, 5, ), 2) | т | =5:(3, 4, 5, 1, 2) | (4, 5, 1, 2, 3) | |||||
| 4 | (4, 5, 1, 2, 3) | т | =5:<4, 5, 1, 2, 3) | (5, 1, 2, 3, 4) | |||||
| 5 | (5, 1, 2, 3, 4 | т | =5: (5, 1, 2, 3, 4) | (1, 2, 3, 4, 5) | |||||
| т | =4:(1, 2, 3, 4) | (2, 3, 4, 1) | |||||||
| 6 | (2, 3, 4, 1, 5) | т | =5:(2, 3, 4, !, 5) | (3. 4, 1, 5, 2) | |||||
У п р .а ж н е н и е II*. Понравилось ли вам изложение Алгоритма-1? Могли бы вы улучшить его разъяснение? Могли бы вы доказать, что по Алгоритму-2 действительно получают все n-перестановки?
Упражнение 12*. Не могли бы вы предложить алгоритм получения всех n-перестановок, отличный от изложенных? Уверены ли вы, что по этому алгоритму можно получить действительно все перестановки? Оглавление
Табличный метод расчёта сетевых моделей (графиков)
(Временные указания по составлению сетевых графиков и применению их в управлении строительством
Стр. 32…37)
Приложение 4
РАСЧЕТ СЕТЕВЫХ ГРАФИКОВ ВРУЧНУЮ
А. МЕТОДИКА РАСЧЕТА ГРАФИКА В ТАБЛИЧНОЙ ФОРМЕ
Рис.1.
Расчет критического пути и резервов времени ведется в табличной 'форме (таблица 1).
Для ручного счета события в сетевом графике нумеруются следующим образом: номер предшествующего собатия должен быть меньше номера последующего события. После нумерации событий шифр (код) работ заносится в графу 8, Причем шифр работ заносится в возрастающем порядке (выписываются все работа, "выходящие" из первого события, затем из второго и т.д.). В графу 1 таблицы заносится количество работ, предшествующих данной работе, т.е. количество работ, "входящих" в ее начальное событие. Продолжительность работ проставляется на основании исходных данных.