Тема 7 Методы разработки алгоритмов

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

7.1. Метод частных целей

Этот метод имеет общую формулировку "Необходимо свести трудную задачу к последовательности более простых задач". С одной стороны, это естественно и разумно, а, с другой стороны, в конкретной задаче часто трудно указать способ ее разбиения на набор более простых задач. Все зависит от опыта и искусства программиста. Несмотря на общность метода и отсутствие рецептов его применения, важно освоить этот метод, поскольку он лежит в основе решения многих задач и по сути является основой алгоритмизации и программирования. Разработка любого алгоритма должна начинаться с ответа на вопрос "Можно ли задачу разбить на последовательность более простых задач?". Рассмотрим метод на задаче сетевого планирования.

Задача. Имеется комплекс взаимосвязанных работ. Для каждой из N работ задана ее трудоемкость в человеко-часах. Необходимо расставить K имеющихся работников так, чтобы длительность выполнения всего комплекса работ была минимальной. При этом запрещено перемещать работников с одной работы на другую в ходе выполнения работ.

Взаимосвязь работ задается сетевым графиком, представляющим собой ориентированный граф без петель и контуров и состоящий из конечного множества вершин и попарно соединяющих их дуг (i, j). Вершины графа – события, а дуги – работы. Работа – трудовой процесс, требующий затрат времени и ресурсов, характеризуется трудоемкостью. Событие – факт окончания всех предшествующих ему работ и возможность начать следующие за ним работы. Работа сетевого графика определяется i-ым событием, предшествующим началу работы, и j-ым событием, указывающим на окончание работы. Работа обозначается (i, j), продолжительность ее выполнения - t_ij, а трудоемкость - r_ij. К числу особых событий относятся исходное 0-ое событие, соответствующее началу выполнения работ, и M-ое завершающее событие, отражающее завершение всех работ. Остальные события нумеруются исходя из требования, чтобы не существовало некоторой работы (i, j), для которой i > j. Путь сетевого графика – любая непрерывная последовательность событий и работ по направлению стрелок. Множество путей, соединяющих два события i и k, обозначим, как L(i, k). Наибольший интерес представляют полные пути, т.е. пути из 0 в M – (0, M). Полный путь с наибольшей продолжительностью I_кр называется критическим.

I_кр = I  (0, M), max T(I),

г де T(I) –продолжительность I -го пути. Рассмотрим конкретный комплекс работ, заданных сетевым графиком, в котором N = 7, K = 10, а множество работ задано графом (рис. справа) A = {(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (3, 5), (4, 5)}. Числа над дугами графа - трудоемкости работ. Множество полных путей - L(0, 5) = {I₁, I₂, I₃}, где I₁ = {(0, 1), (1, 3), (3, 5)}, I₂ = {(0, 1), (1, 4), (4, 5)}, I₃ = {(0,2), (2,4), (4,5)}.

Для K = 7 задача имеет тривиальное решение, так как на каждую работу приходится по одному работнику. При K = 8 появилась бы возможность поставить "лишнего" работника на одну из работ комплекса. Тогда вариантов такой расстановки было бы 7 по количеству работ. При K = 9 вариантов расстановки было бы уже 7², а в нашем случае – 7³. Количество вариантов с ростом размерности задачи быстро растет и решение ее путем полного перебора неэффективно.

Один из простых путей решения задачи состоит в том, чтобы разбить задачу на три шага. На первом шаге решить задачу, куда поставить 8-го работника. Зафиксировав рабочего, на втором шаге решать задачу, куда поставить 9-го работника и т.д. Таким образом, сложная задача свелась к трем последовательным более простым задачам. В общем случае число таких простых задач равно (K - N). Каждая из этих однотипных задач формулируется так.

Необходимо принять решение о добавлении одного работника на одну из работ комплекса так, чтобы время выполнения всего комплекса по полученной расстановке было минимальным.

При конкретной расстановке работников по каждой работе время выполнения отдельной (i, j)-ой работы составит t_ij = r_ij / k_ij, где k_ij - количество работников на (i, j)-ой работе. В нашей задаче при исходной расстановке семи работников по одному на каждую работу времена их выполнения численно равны трудоемкостям, а длительности полных путей составят

T(I₁) = t₀₁ + t₁₃ + t₃₅ = 1 + 2 + 4 = 7,

T(I₂) = t₀₁ + t₁₄ + t₄₅ = 1 + 2 + 1 = 4,

T(I₃) = t₀₂ + t₂₄ + t₄₅ = 2 + 3 + 1 = 6.

Продолжительность выполнения комплекса работ определяется продолжительностью самого длинного из полных путей (критического пути) I₁ и равна 7 часам. Очевидно, чтобы уменьшить эту длительность, следует поместить "лишнего" 8-го работника на одну из работ критического пути. Ставя работника на каждую работу этого пути (0,1), (1,3), (3,5) и сравнивая получающиеся варианты, выбираем из них вариант с наименьшей продолжительностью выполнения комплекса работ. В нашем случае это вариант с размещением работника на работу (3,5). Таким образом, задача размещения одного работника решена и переходим к следующей задаче последовательности. В общем случае, при поиске решения по данному алгоритму придется проанализировать не более (K-N)N вариантов.