Файл: Основы теории алгоритмов учеб. пособие.pdf

N 1

N a Ф • ■ • ф N m

вероятность Р ;

появления операции

L-ro типа для класса

задач зависит от

соотношения их оложноотей я равна

специальные команды, которые позволяют изменять длину програм­

f

мы вычислений и время реализации алгоритма в ту или другую

сторону, изменять конструкцию УМ. По окончании составления

■?

каждой программы вычисления простой операции производится чис­

ленная, оценка параметров алгоритма.-Эти оценки записываются в

виде кортежей. В связи с этим каждый алгоритм одного и того

же набора будет отличаться от другого значением параметров.

Разумеется, что алгоритм управления, составленный из проотых

подалгрритмов, определяется параметрами, которые являются функ­

циями параметров простых подалгоритмов. .

При решении задачи выбора появляются определенные труд­

ности, так как обеспечение необходимой эффективности алгорит­

ма управления связано с выполнением противоречивых требова­

ний [79] .

Из множества простых алгоритмов можно выбрать такие,

которые позволяют получить наименьшим один из параметров ал­

горитма управления..Например, для того, чтобы получить мини

мальное время реализации алгоритма, необходимо выбрать из каж­

дого набора по одному алгоритму с ;' 'амал-ннм гремевсм релда,-

эации. Однако по другим параметра, (дл я.а программ- , оиотема

где W -общее

число операций (наборов);

j - номер

операции (набора).

Каждая операция

может быть реализована несколькими алго­

ритма»®, отличающимися своими параметрами:

^ ЭЕ[Ajt],

— ’

(2.2)

где

H j-

число алгоритмов в

наборе

f-j

;

I - номер алгоритма в

J j .

•

•

Так как

в евою очередь является множеством элемен­

тов

А]1 , то в дальнейшем будем

именовать как подшожеот-*

ва

р

:

|

1.

d

р

«(2.3)

' !

—

г

•

Тогда, ооглаоно (2.3) и определениям (2.1)

и (2 .2 ),

Ajt € F.

(2.4)

Из

(2 .3)

вытекают два частных

случая:

с

F

и

) |

-

F .

Для второго случая имеем, что множество Fсостоит

из

одного подмножества

и,

.согласно

(2.4),

F =

{ A i l ,

A i z , . . . ,

A lH i} .

(2.5)

Выражение

(2.5)

соответствует

случаю, когда шожеотво,

состоит из множества простых алгоритмов

одной и той же опера­

дом перебора.

Рассмотрим случай

СП р

при

Ж > 2

.

j

Пусть множество операций F

4используется для составления не4

которого алгоритма

Ь\ ,

Если каждая

j -ая операция харак­

теризуется набором алгоритмов Е jl

,

представленных простыми

кортежами, то для алгоритма

М может быть составлена система

сложных матриц

УХр,

которая затем может быть преобразована

,

в оистему проотых ^матриц

j

(2. 6).

Для получения некоторого

- решения необходимо из

каждого набора (колонки)

E j

матриц

X?

выбрать по одной

компоненте

. Над выбранными Ш компонентами каждой мат­

рицы проводится операция

0

, которая позволит

получить

■

значение некоторого параметра алгоритма

И :

^

ЭСрн e

0

C ^ i)-

кортежа алгоритма

И

, Данный кортеж будет характеризовать'

эффективность алгоритма

М В

-м варианте.

Предположим,

что нам удалось получить кортежи воех 6

ти в

% -мерном пространстве.

|

На рис. 2.1

изобразим множество решений в виде дискрет­

а х

точек, которые

являются концами вектора

эффективности.

Для удобства выбора оптимального варианта,

по оси абсцисс от­

ложим значения минимизирующего параметра, а

по оси ординат -

ставленные прямой, параллельной оси абоцисс.

Пусть алгоритм И

имеет кортеж о

£ = 4.

Среди ком­

понент кортежа

^необходимо минимизировать пара­

метр X t

при наложении на компоненты

Х х ,

Хх, Х а

ограни­

чений

X i ^ X I t Х х ^ Х х

»

Х а & Х а

Пусть число решений

8 = 8 ,

тогда множество

его

будет

иметь вид,изображенный на рио.

2 .1 .__________________ __

!

I

- 46 -

Ограничения, наложенные на параметры

Х а

,

ного алгоритма, выбирается третий с

win t

а оптимальными

EjL будут те, которые составляют алгоритм

М в третьем

варианте. Если несколько вариантов

содержат компоненты Хзтш ,

Таким образом , для больших

H j

и

число в се в о з­

можных вариантов S

может достигать

значительной величины,

что затрудняет выбор оптимального варианта. В этих случаях

следует

применять специальные формальные методы, позволяющие

о меньшей трудоемкостью строго

находить оптимальные решения.

2 .2 . Методы перебора и последовательных

приближений

Метод перебора заключается в последовательном переборе

всех S

вариантов.

Для каждого

^

-

решения составляется

поставленным требованиям, мы из оставшихо:

вариантов выбира­

ем тот, у которого минимизирующая компонег а имеет

минималь­

ное значение. При. этом получим алгоритмы

Е- j i

,

составля­

!зовать

при отыокании оптимальных алгоритмов для небольшого

|чиола вариантов

S

.

j

Близким к методу перебора является метод

последова­

тельных приближений.

Пусть система приоритетов^по

шраметрам

алгоритма М

составлена так,

что первым следует минимизиро-

вать 0Cj>M =*

,

Тогда последовательно перебираются в а -

»

рианты

)С\

,

начиная с

, который имеет Х?°н

наи­

меньший, до варианта

,

у которого X f n min

,

а зое

-

Если Х р м ( Jfj )

- параметр алгоритма И

в

в |

-м

]

варианте, a X f *

параметр в ^ н - о и варианте,

то

при

i-

*

n.viWhkV.v

I