книги из ГПНТБ / Основы теории алгоритмов учеб. пособие

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

последовательном переборе должно выполняться условие

X f eM

^

■

В каждом

Щ -ом варианте

подсчитываются все

параметры

алгоритма, и если один из вариантов не удовлетворяет

постав­

ся

переход к

tfj+i

варианту.

Этот

процеоо продолжается

до

тех

пор,

пока не будет найден

tfj® -

оптимальный вариант.

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

имеют Х ? ‘м

, то

после

- варианта следует продолжать раочет еще ряда

( Х{#+н

,

}S^®+2 ) вариантов до тех пор, пока в

некотором варианте

бу­

дет

1

X j>*m (

K'i 'w

) >

Х ^ вм wi-fi.

Это частное решение следует минимизировать теперь по

другому параметру,

исключив

Х р и

из дальнейшего рассмотрения

Так как все

at

вариантов

удовлетворяют требованиям,

то н а - j

хождение новых частных решений овязано

с перебором всех ot ва­

риантов, минимизирующих параметр с меньшим приоритетом, чем

I

предыдущий.

Боли

dt

=

I ,

то

оптимальный вариант

найден и алго -

!

ритмы

E ji ,

составляющие данное решение,

являются наилучшими.

Для большого

числа решений

8

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

, •

приближений являетоя предпочтительнее метода перебора, так

как

здесь не рассматриваются варианты

о

Х р м

> X f “n min

,

,

число которых может быть большим.

Последовательные приближения (рио.

2 .2) показаны от

д о

)Г|» = 5 .

Для вариантов

XV, XV XV

ВЫПОЛНЯЮТСЯ уоловия

j

( j f s ) “

( к < ) ~

( у ? )

!

Из трех вариантов

(

V * ,

У«

,

XV

)

можно выбрать

ОДИН,

если минимизировать

по одному из

параметров X i

, Хг.

,

г

- 48

- .............

. . '

i

Х а . Для йктлвыбирается вариант

V? , дляХаипм-Ут,

для

Х*тй1 - Х*5 •

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

црограшн

с! и времени реализации Ь . Однако

d

совмест­

но

о Л

составляют единую долговременную шмять

D

маши­

ны,

Поэтому для минимизации D можно поступить

следующим об­

$ |«

, минимизирующий параметр d

, а остальные параметры

(кроме

А

) должны удовлетворять заданным требованиям. Для

этого варианта

определяется

I

D j *

-

+

.

где

A j* определяется после операций,

проведенных над выбран­

ными компонентами-множествами матрицы К

. После этого пере­

ходим к

вычислению следующих вариантов 1)

. Для сокращения за­

писи обозначим

= V®

>

тогда

следующие варианты есть

I

$ 2

(

<Ь =

0 , 1 , 2 , . . . , ) .

Для каждого варианта определяют­

ся

Т )0 ,

D

i , .

. . .

В процессе этих вычислений последующие зна-

IDi.e > T)*»ni»t. Процеос

продолжается до

получения D d°> j)xm in .

^Очевидно, что вое последующие варианты

.

)

дадут

i

Если минимизируется параметр b

г т

ограничении d+A=«

j

=*Т)огр , то здесь

будут отличия в

там,

что после операций

: Q над компонентами матрицы d

и матрицы К « после которой

определяется Л , в

каждом варианте вычисляется d + А , для

которой выполняется

d + A ^ Т)ог,р . При выполнении этого

условия осуществляется переход к

следующему варианту.

;

2 .3 . Методы исключения вариантов и линейного

i

программирования

|

Метод исключения вариантов предполагает исключение тех