5. Программа «жадного» алгоритма

Жадный алгоритм (greedy algorithm) — это алгоритм, который на каждом шагу делает локально наилучший выбор в надежде, что итоговое решение будет оптимальным.

Условия применимости.

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

Принцип «жадного» выбора.

Говорят, что к оптимизационной задаче применим принцип «жадного» выбора, если последовательность локально оптимальных выборов даёт глобально оптимальное решение. В типичном случае доказательство оптимальности следует такой схеме:

̶ доказывается, что «жадный» выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с «жадным» выбором и не хуже первого.

̶ показывается, что подзадача, возникающая после «жадного» выбора на первом шаге, аналогична исходной.

̶ рассуждение завершается по индукции.

Оптимальность для подзадач.

Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач.

Procedure Init; { Переназначение меток вершин }

Var

I,j,m :Integer; begin

for i:-l to 2*nU do Uo[i]:=l; for i:=l to 2*nU do

for j:=i+l to 2*nU do if Uo[j]=l then if U[j]=U[i] then Uo[j]:=0;

Программа жадного алгоритма

Program HungryOstov; {Остовное дерево. Жадный алгоритм)

uses CRT,DOS;

Const

nVertex=50; {Максимальное количество вершин} nRib=1000; {Максимальная количество ребер}

Туре

TypeVertex=array[1..nVertex] of Integer; TypeRib=array[1..nRib] of Integer;

Var

2 Разработка структурной схемы и расчёт основных характеристик

автоматизированной системы управления в ЧС

Определим необходимое количество операторов в центре автоматизированной системы управления в ЧС. Время занятости оператором обслуживанием одного вызова (заявки) определяется выражением:

, (4)

где время переговоров с абонентом (1,5 мин.);

время обработки заявки в АСУ;

время передачи приказа.

= 1,5+1,4+1,2 = 4,1мин = 0,0683 ч.

Определим полную нагрузку на всех операторов за смену длительностью 12 часов по формуле:

У , (5)

= 0,1 ; ч-зан.,

Определим допустимую нагрузку на одного диспетчера за смену с учётом коэффициента его занятости:

ч-зан., (6)

Определим необходимое число диспетчеров:

. (7)

Принимаем один диспетчер на центре АСУ в ЧС.