книги / Решение некоторых многоэкстремальных задач методом сужающихся окрестностей
..pdfВсе режимы, начиная со второго, аналогичны и отличаются друг От друга только величиной v радиуса окрестности. Режимы состоят 6 следующем. Случайным образом выбираются перестановки, лежащие в круге радиуса v с центром в точке р*. По окончании се рии так же, как и в первом режиме, определяется вероятность полу чения лучших, чем уже имеющиеся, значений функционала / (р). Действует то же правило, определяющее необходимость перехода
к новому режиму. Если лучшее значение /функционала, получен
ное после данного прохождения режима, такое, что / < /* , то в качестве перестановки р* далее используется перестановка р, для
которой / (р) = /.
Правила изменения радиуса v окрестности лучшей перестанов ки и правило выбора длины серии бросков рассматриваются в § 5 данной главы. Отметим лишь, что радиус v уменьшается, а длина серии бросков остается неизменной.
Процесс поиска по методу сужающихся окрестностей заканчи вается, когда при v = 1 появляется необходимость в уменьшении радиуса.
В предыдущих параграфах приведены строгие доказательства теорем об изменениях математического ожидания и дисперсии при специальном выборе перестановок в шаре заданного радиуса. Та кой выбор перестановок, оказывается, осуществить довольно просто. Тем самым у нас есть возможность управлять как математическим ожиданием, так и дисперсией. А это значит, что вероятность полу чения «плохих» значений функционала при переходе с одного режи ма на другой существенно уменьшается. К сожалению, это еще не означает, что вероятность получения «хороших» значений функцио нала увеличивается. Последнее надо понимать в том смысле, что авторам не известно строгое доказательство сходимости метода сужающихся окрестностей к глобальному экстремуму. Лучшим «оп равданием» использования этого метода являются эффективные ре зультаты его применения для решения прикладных задач. Со ответствующие примеры приведены в четвертой главе.
Отметим, однако, что метод сужающихся окрестностей вслед ствие своей структуры во всяком случае не менее эффективен, чем классический метод Монте — Карло, так как функционал / рассмат ривается на таких перестановках, что вероятность получения луч ших значений целевой функции по крайней мере не уменьша ется.
Важно и то, что при использовании метода сужающихся ок рестностей «результат» получается за конечное число шагов. В самом деле, переход к новым режимам поиска (а при v = 1 к окон чанию поиска) определяется поведением вероятности Рк. Между тем, как следует из формулы (3.62), эта вероятность неизбежно уменьшается, как только находятся лучшие, чем ранее, значения функционала /, т. е. при уменьшении Л.
lo t
Наконец, отметим, что речь идет о вероятностном методе поис ка и результат поиска не однозначен, а зависит от того, какие слу чайные числа генерируются. Вместе с тем при использовании того же датчика случайных чисел при прежнем взводе будут получены те же значения целевого функционала. Таким образом, метод сужающихся окрестностей дает вполне воспроизводимые результаты.
Рассмотрим алгоритм, реализующий метод сужающихся окре стностей. При этом предполагаются известными процедуры: LENGTH для выбора длины.# серии бросков, RADIUS для опреде ления радиуса v окрестности и AIM для построения значения функ ционала на данной перестановке. Способ метризации пространства перестановок считается известным, причем известна также проце дура NEIGHB построения перестановки, расстояние которой до фиксированной перестановки не превышает заданной величины.
Приведем алгоритм, в котором используется гипотеза о нормаль ном характере распределения значений функционала.
Алгоритм 3.1.
Ш а г 1. Применить процедуру LENGTH.
Ша г 2. Если длина N серии бросков найдена, перейти к шагу 4; иначе положить f* равным лучшему из полученных во время ра боты процедуры LENGTH значению функционала, ар* — равным соответствующей перестановке.
Ша г 3. Остановиться. Эта остановка означает, что исполь зование метода сужающихся окрестностей не эффективно.
Ш а г 4. Положить f = f* = 1018, <7 = 0.
Ша г 5. Положить Р — 0.
Ша г 6. Положить t = 1, т = 0, о = 0.
Ша г 7. Если q = 0, перейти к шагу 8; иначе перейти к шагу 9.
Ша г 8. С помощью датчика случайных чисел выбрать произ вольную перестановку р из п символов и перейти к шагу 10.
Ша г 9. С помощью процедуры NEIGHB построить перестанов ку р, для которой р (р, р*) < V.
Ша г 10. С помощью процедуры AIM вычислить значение функ ционала f (р).
Ш а г |
11. Если /(р) > /*, перейти к шагу 12; иначе положить |
|||
7 = /(р), |
P o p |
т + |
f (р), о = |
а + [/(р) ]*, i = t + 1. |
u l a r |
12. Положить т = |
|||
Ш а г 13. Если i > N, перейти к шагу 14; иначе перейти к шагу 7. |
||||
Ш аг |
14. Положить т = |
, |
а = "j/~ |
(о — m2N ), Р =» |
- FREQ |
• |
|
|
|
Ш а г |
15. Если f <. f*, положить f* =~f, |
p* = p. |
||
Ш а г 16. Если P > P, перейти |
к шагу |
17; иначе перейти к |
||
шагу 18. |
17. Положить Р = Р и перейти к шагу 6. |
|||
Ш а г |
102
Ш а г |
18. Положить <7=1. |
определить радиус |
|
Ш а г |
19. С помощью процедуры RADIUS |
||
v окрестности лучшей |
перестановки. |
|
|
Ш а г 20. Если v = |
0, перейти к шагу 21; иначе перейти к ша |
||
гу 5. |
21. Выдать |
на печать значения /* |
и р*. Остановиться. |
Ш а г |
Если используется гипотеза о логнормальном характере закона распределения, то предполагается известной еще процедура BORDER для определения нижней оценки т) значений функциона ла f. В алгоритм 3.1 вносятся следующие модификации. Добавляет ся шаг 0, на котором с помощью процедуры BORDER вычисляется нижняя оценка rj для глобального минимума функционала /. Кроме того, шаги 6, 12 и 14 заменяются соответственно следующими.
III а г 6. Положить г = |
1, р = |
0, s = 0. |
Ш а г 12. Положить р = |
р + |
In [/ (р) — т]) 1, s = $ + {In [/ (р) — |
— ’l l } 2, |
i = i + 1. |
|
Ш а г |
14. Положить |
|
И = |
s = fZ" ~N~ T (s — т2Ю>p = FREQ |
• |
Приведем фортранный текст программы SEARCH, реализующей метод сужающихся окрестностей.
п п п о п о о п п п о п п п п о п о о п п о п п о о п о п п о
SUBROUTINE SEARCH
**************************де*****************************************
ПРОГРАММА РЕАЛИЗУЕТ МЕТОД СУЖАЮЩИХСЯ ОКРЕСТНОСТЕЙ ОПИСАНИЕ РЕЖИМОВ РАБОТЫ ПРОГРАММЫ:
ФОРМА ПРЕДСТАВЛЕНИЯ РЕЗУЛЬТАТОВ ЕСЛИ К А = 1, ТО ПЕЧАТАЕТСЯ ТОЛЬКО ЛУЧШИЙ РЕЗУЛЬТАТ, ЕСЛИ КА = 0, ТО
ОТРАЖАЕТСЯ ТАКЖЕ ХОД ПОИСКА ПО СЕРИЯМ
КОНТРОЛЬНЫЙ РЕЖИМ ЕСЛИ КМ = 0, ТО НЕТ РАСЧЕТА ПО МЕТОДУ
МОНТЕ-КАРЛО, ЕСЛИ КМ = 1, ТО ЗАДАЧА РЕШАЕТСЯ ПО МЕТОДУ МОНТЕ-КАРЛО С ТЕМ ЖЕ ЧИСЛОМ БРОСКОВ
ГИПОТЕЗЫ О ЗАКОНЕ РАСПРЕДЕЛЕНИЯ ЕСЛИ КН = 0, ТО ЗАКОН НОРМАЛЬНЫЙ, ЕСЛИ КН = 1 ЗАКОН ЛОГНОРМАЛЬНЫЙ
ВЫБОР ДЛИНЫ СЕРИИ БРОСКОВ ЕСЛИ KLS = 0, ТО АПРИОРНЫЙ
ЕСЛИ KLS = I, АВТОМАТИЧЕСКИЙ
СПОСОБ ИЗМЕНЕНИЯ РАДИУСА ОКРЕСТНОСТИ
ЕСЛИ KR = —1, ТО ИСПОЛЬЗУЕТСЯ РЯД ФИБОНАЧЧИ ЕСЛИ KR = 0, ТО УМЕНЬШАЕТСЯ ВДВОЕ,
ЕСЛИ KR = 1, ТО УМЕНЬШАЕТСЯ НА ЕДИНИЦУ
108
o n n n o o n n n n n n o o n n n n
ВЫБОР МЕТРИЗАЦИИ ПРОСТРАНСТВА ПЕРЕСТАНОВОК
ЕСЛИ KN = |
1, ТО ЦЕПНАЯ, |
ЕСЛИ KN = |
2, ТО ЛЕКСИКОГРАФИЧЕСКАЯ, |
ЕСЛИ KN = |
3, ТО АЛФАВИТНАЯ, |
ЕСЛИ KN = |
4, ТО ИНВЕРСНАЯ, |
ЕСЛИ KN = |
5, ТО ТРАНСПОЗИЦИОННАЯ |
КРИТЕРИИ ОСТАНОВА ЕСЛИ КВ = О, ТО ОКОНЧАНИЕ ПЕРЕБОРА
*ЕСЛИ КВ = 1, ТО ПОЛУЧЕНИЕ РЕЗУЛЬТАТА
ВЫЗЫВАЕМЫЕ ФУНКЦИИ И ПОДПРОГРАММЫ: CTIME, INPUT, BORDER, RADIUS, OUTPUT, PERMUT, NEIQHB, AIM, LENGTH, MONTE, FREQ
*********************************************************************
COMMON /INNE/ N /NEME/ Z,
*/MENE/ IBP(300), IP(300) /NKSE/ NS /IR IN / LEN
./I I / IRAD.KR /RANE/ NR /NESE/ KN /LESE/ IS
./SELE/ KH /SEBO/ ETA /ADIN/ EPS
./KISE/BZ /RND/ IX DIMENSION ISTR (128), IBT(300) DATA (ISTR = 128('—'))
IX = 65539 READ 125, NZ DO 70 1 = 1, NZ
70R = RNDM (—1) PRINT 126,NZ CALL INPUT
CALL CTIME (Al, Bl)
READ 101,KLS.KHtKR,KM,KN,KA,KB
B Z = |
1 .E + 15 |
||
IS |
= |
|
0 |
ISS = |
0 |
||
PRINT 102 |
|||
IF |
(KLS) 1,1,2 |
||
1 PRINT |
103 |
||
GO TO |
3 |
2PRINT 104
3IF (KH) 4,4,5 -4 PRINT 105
GO TO 6
5PRINT 106
6IF (KR)7, 8,9
7PRINT 107 GO TO 10
8PRINT 108 GO TO 10
9PRINT 109
10IF (KM) 11,11,12
11PRINT 110 GO TO 13
12PRINT 111
13 |
IF |
(KN.NE.l) |
|
T- |
GO TO 14 |
|
PRINT 112 |
|
14 |
GO TO 15 |
|
IF |
(KN.NE.2) |
104
GO TO 16
PRINT 113
GO TO 15
16IF (KN.NE.3)
- GO TO 17 PRINT 114
17 |
GOTO 15 |
|
IF (KN.NE.4) |
||
|
- |
GO TO 18 |
|
115 |
|
18 |
GO TO |
15 |
PRINT 116 |
||
15 |
DO 213 I = 1,N |
|
213 ' IBP(I) = |
I |
|
|
IF (KH.EQ.l) |
|
|
- |
CALL BORDER |
|
IF (KLS) 19.19.20 |
19READ 125,NS PRINT 118,NS IRAD = 0 CALL RADIUS IRAD = 1
IQ = 0 GO TO 21
20 CALL LENGTH CALL CTIME (A,B)
A — A __ Д 1
PRINT 151,A JS = IS PRINT 152, IS PRINT 127,BZ
IF (LEN) 22,22,23 22 IRAD = 0
CALL RADIUS IRAD = 1
IQ — 1
21IF (KA.EQ.l)
- GOTO 60
119, (ISTR(K),K= 1,106) |
|
150 |
|
U9,(ISTR(K),K = 1,106) |
|
60 KQ =*= |
1 |
24PP = 0.
XX= 0.
NP = 0
25XM = 0.
S= 0.
BZZ = 1 .E + 15
IF (KH) 26,26,27
27YM = 0. YS = 0.
26DO 35 1 = 1 , NS IF (IQ) 28,28,29
28CALL PERMUT GO TO 31
29CALL NEIGHB
KQ = 0
31 CALL AIM IS = IS + 1
IF (Z — BZZ) 32,33,33
32 |
BZZ = |
Z |
1,N |
34 |
DO 34 К = |
||
IBT(K) = |
IP(K) |
||
|
IF(BZZ.GT.EPS) |
||
|
— |
|
GO TO 33 |
|
CALL CTIME (A,B) |
||
|
AB = |
A — A1 |
|
|
IF (ISS.NE.O) |
||
|
— |
|
GO TO 75 |
|
BZS = |
BZZ |
|
|
TQQ = |
IS |
|
75 |
IF (KB.EQ.O) |
||
|
— |
|
GO TO 33 |
62 |
DO 62 К = |
1,N |
|
IBP(K) = |
IBT(K) |
||
33 |
GO TO 51 |
|
|
XM = |
XM + Z |
s = s + z*z
IF (KH) 35,35,36
36Y = Z — ETA IF (Y) 37,37,38
37PRINT 120 RETURN
38Y = ALOG (Y) YM = YM + Y YS = YS + Y*Y
35 CONTINUE |
|
||
XM = |
XM/NS |
||
NP = |
NP + |
1 |
|
XX = |
XX + |
XM |
|
S = |
(S — XM*XM*NS)/(NS — 1) |
||
IF |
(S — l.E |
- 10) 205,205,206 |
205S = 0. GOTO 207
206S = SQRT (S)
207CONTINUE IF(BZZ.LT.BZ)
— BSL = BZZ
IF (KH) 39,39,40
39IF (S.LT.l.E—10)
—GO TO 41 P = FREQ ((BSL — XM)/S) GO TO 42
41P = 0. GO TO 42
40YM = YM/NS
YS = (YS — YM*YM*NS)/(NS — 1) IF (YS — l.E — 10) 215,215,216
215YS = 0. GO TO 41
216 YS = |
SQRT (YS) |
P = |
FREQ(ALOG(BSL — ETA) — YM)/YS) |
42IF (BZZ — BZ) 43,44,44
43BZ = BZZ BSL = BZ
DO 45 К = 1,N
45IBP(K) = IBT(K)
TS7= IS
44IF (KA.EQ.l)
— GO TO 48
106
IF(IQ) 46,46,47
46PRINT 121,BZZ,XM,S,P GO TO 48
47PRINT !22,NR,BZZ,XM,S,P
48IF (P — PP) 49,49,50
50 PP = P GO TO 25
49IQ = 1
XX = XX/NP
IF (KA.EQ.l)
—GO TO 61
PRINT 119,(ISTR(K), К = 1,106)
PRINT 123,XX
61CALL RADIUS IF <NR)5I,51,24
51IF (ISS.NE.O)
-PRINT 160,BZS,ISS,AB
PRINT 163,BZ,ISZ CALL OUTPUT
IF (KM) 52,52,53 53 CALL MONTE
23 CALL OUTPUT
52PRINT 124,IS CALL CTIME(A.B)
ДI = Д __ Д I
PRINT 162,A1 A1 = A RETURN
101 FORMAT (211,12,511)
102FORMAT (///45,X ,'РАБОТАЕТ МЕТОД', ♦'СУЖАЮЩИХСЯ ОКРЕСТНОСТЕЙ')
103FORMAT (//5Х,'ДЛИНА СЕРИИ',
♦'ВЫБИРАЕТСЯ АПРИОРНО')
104FORMAT (//5Х,'ДЛИНА СЕРИИ', ♦'ВЫБИРАЕТСЯ АВТОМАТИЧЕСКИ')
105FORMAT (5Х,'ИСПОЛЬЗУЕТСЯ НОРМАЛЬНЫЙ',
♦'ЗАКОН РАСПРЕДЕЛЕНИЯ')
106FORMAT (5Х,'ИСПОЛЬЗУЕТСЯ ЛОГНОРМАЛЬНЫЙ', ♦'ЗАКОН РАСПРЕДЕЛЕНИЯ')
107FORMAT (5Х,'РАДИУС УМЕНЬШАЕТСЯ'.
♦'ПО ЧИСЛАМ ФИБОНАЧЧИ')
108FORMAT (5Х,'РАДИУС УМЕНЬШАЕТСЯ ВДВОЕ')
109FORMAT (5Х,'РАДИУС УМЕНЬШАЕТСЯ',
♦'НА ЕДИНИЦУ')
НО FORMAT (5Х,'НЕТ ПРОВЕРКИ ПО', |
/ |
♦'МЕТОДУ МОНТЕ — КАРЛО') |
|
111FORMAT (5Х,'ЕСТЬ ПРОВЕРКА ПО', ♦'МЕТОДУ МОНТЕ — КАРЛО')
112FORMAT (5Х,'ЦЕПНАЯ МЕТРИКА')
ИЗ FORMAT (5Х,'ЛЕКСИКОГРАФИЧЕСКАЯ МЕТРИКА')
114FORMAT (5Х,'АЛФАВИТНАЯ МЕТРИКА')
115FORMAT (5Х,'ИНВЕРСНАЯ МЕТРИКА')
116FORMAT (5Х,'ТРАНСПОЗИЦИОННАЯ МЕТРИКА')
118FORMAT (//15Х,'ДЛИНА СЕРИИ',15,
.'БРОСКОВ'///)
119FORMAT (10Х,':', 106А1,':') 150 FORMAT (
110Х,': РЕЖИМ ПОИСКА : ЛУЧШ ЕЕ', 2'ЗНАЧЕНИЕ : СРЕДНЕЕ :', 3' МАТЕМАТИЧЕСКОЕ : ',
«'СТАНДАРТНОЕ : ВЕРОЯТНОСТЬ : ')
410Х,' : (РАДИУС ШАРА) : 5Х,'В СЕРИИ', 55Х': ПО РЕЖИМУ',5Х, 6 ': ',5Х,'ОЖ ИДАНИЕ',5Х,': ОТКЛОНЕНИЕ',
7 ' 4Х,' УЛУЧШЕНИЙ :')
120FORMAT (IX,'ОЦЕНКА СНИЗУ НЕ ВЕРНА')
121FORMAT (10Х/: СЛУЧАЙНЫЙ ПОИСК:',
12X.F13 6,2Х ,':',18Х /: \F12.6, 2' : '.F13.6,' :, F13.6,' : ')
122FORMAT (10Х,' : ',5Х ,16,5Х / : ', 1F13.6.2X,' : ',18Х,' : '.F12.6,
2': '; F13.6,' : '.F13.6,' : ')
123FORMAT (49X.F13.6)
124FORMAT (//5Х,'ОБЩЕЕ ЧИСЛО БРОСКОВ',1Б)
163FORMAT (//5Х, 'ЛУЧШИЙ РЕЗУЛЬТАТ', *F10.4,'BbUI ПОЛУЧЕН НА Ш АГЕ',16)
162 |
FORMAT (//5Х,'ВРЕМЯ СЧЕТА ВАРИАНТА', |
125 |
«ПО.ЗДСЕКУНД'//) |
FORMAT (13) |
|
126 |
FORMAT (5Х,'ДАТЧИК СЛУЧАЙНЫХ', |
127 |
«'ЧИСЕЛ ВЗВЕД ЕН ',15,'РАЗ') |
FORMAT (5Х,'ЛУЧШЕЕ ЗНАЧЕНИЕ ПОСЛЕ', |
|
|
«'РАБОТЫ LENGTH РАВНО',F10.3) |
151FORMAT (//5Х,'ВЫБОР ДЛИНЫ СЕРИИ', «'БРОСКОВ ЗАНЯЛ',F10.3,'СЕКУНД')
152FORMAT (/5Х,'СДЕЛАНО',16,'БРОСКОВ')
153FORMAT (//5Х,'СПУСК ЗАНЯЛ',F10.3,'СЕКУНД')
160FORMAT (//5Х,'УДОВЛЕТВОРИТЕЛЬНЫЙ РЕЗУЛЬТАТ', »F10.4/BbUI ПОЛУЧЕН',
«'НА Ш АГЕ',16,'ЗА ',F10.3,'СЕКУНД')
161FORMAT (/5Х, 16,'БРОСКОВ ПО МЕТОДУ',
«'МОНТЕ — КАРЛО ЗАНЯЛИ',F10.3',СЕКУНД) END
Замечания к программе SEARCH.
1.Программа CTIME предназначена для определения времени счета. Она входит в стандартное математическое обеспечение ЭВМ «БЭСМ-6». Ее текст содержится в [4].
2.Текст программы RADIUS приведен на с. 118.
3.Текст программы LENGTH приведен на с. 113,
4.Текст программы FREQ приведен на с. 80.
5.Текст программы PERMUT приведен на с. 43.
6.Ниже приводим текст программы NEIGHB.
п п п п п п п п
SUBROUTINE NEIGHB
****************4$****************************************************
ПРОГРАММА ПРЕДНАЗНАЧЕНА ДЛЯ ПОСТРОЕНИЯ ПЕРЕСТАНОВКИ ИЗ ШАРА В РАЗЛИЧНЫХ МЕТРИКАХ
•*••******»**•*«•**•**••••»*••*••«***»••*•••»**••••»****»*******«•**•
COMMON /NESE/ KN
IF (KN.GT.l) GOTO 1
CALL CHAIN
RETURN
1IF (KN.GT.2) GOTO 2 CALL LEXICO
108
RETURN
2IF (KN.GT.3) GO TO 3 CALL ALPHAB RETURN
3IF (KN.GT.4) GO TO 4 CALL INVERS RETURN
4CALL TRANSP RETURN
END
Программы CHAIN, LEXICO, ALPHAB, INVERS и TRANSP приведены на с. aa, бб, вв, гг, ее соответственно.
7. Ниже следует текст программы MONTE.
SUBROUTINE MONTE
С
с****#.*♦§***.***♦**********♦***»#***********.*..***..**.........
с
СПРОГРАММА ПРЕДНАЗНАЧЕНА ДЛЯ ПРОВЕДЕНИЯ
СПОИСКА ПО МЕТОДУ МОНТЕ-КАРЛО
С
СВЫЗЫВАЕМЫЕ ФУНКЦИИ И ПОДПРОГРАММЫ:
СAIM.PERMUT
С
с *********************************************************************
о
COMMON /KISE/ BZ /LESE/ IS
»/INNE/ N /NEME/ Z /MENE/ IBP(300),IP(300) BZ = l.E + 16
DO 4 1 = 1,IS
CALL PERMUT CALL AIM
IF (BZ—Z) 4,4,2 2 B Z = Z
DO 3 K = 1,N
3IBP(K) = IP(K)
4CONTINUE RETURN END
§5. Выбор длины серии
Как показано выше, в методе сужающихся окрестностей су щественно используется проведение серии испытаний в заданном ре жиме. Поэтому большой интерес представляет вопрос о том, как выбирать число бросков в серии.
Предлагаемый ниже способ основан на проверке критерия сог ласия между гипотетическим распределением вероятностей и ре зультатами испытаний. В качестве длины серии испытаний выбира ется минимальное число бросков, которое обеспечивает отсутствие значимых отклонений результатов испытаний от применяемой гипо тезы [14, 28].
При этом проверяется, насколько верно была принята гипотеза о характере распределения значений функционала / (р). Для этого задается максимально допустимое число Q бросков в серии. Если
109
Q испытаний, проведенных по методу Монте-Карло, не обеспечивают отсутствия значимых отклонений, то исходное предположение 0 характере закона распределения считается неверным. В таком слу чае использование метода адаптивного перебора не рационально, поскольку вероятностные характеристики, которые применяются при работе метода, будут недостоверными. Поэтому метод адаптив ного перебора не используется. После проведенных Q испытаний выбирается рекордная перестановка р*, и соответствующее значение функционала / (р*) считается лучшим приближением к глобальному минимуму.
Число Q определяется заранее, исходя из оценок затрат машин ного времени на поиск одного значения функционала и возможных улучшений. Считается, что если число бросков в серии превышает Q, то использование метода адаптивного перебора экономически не эффективно.
Определение числа N бросков в серии осуществляется с помощью метода дихотомии. Выбираются два конца интервала (М, N). Пер воначально М = 1, N = 10. Определяется наличие или отсутствие значимых отклонений в сериях из М и N бросков. Значения М и N удваиваются до тех пор, пока на правом конце интервала значимые отклонения будут отсутствовать. Далее происходит деление интер вала (М , N) пополам и выполняется серия из (М + N)/2 бросков. Один из концов интервала переносится в середину, причем так, чтобы на левом конце интервала значимые отклонения существова ли, а на правом отсутствовали. Последовательное деление интерва ла пополам продолжается до тех пор, пока не определится минималь ное число бросков в серии, гарантирующее отсутствие значимых отклонений.
Процесс выбора числа N бросков в серии |
удобно представить |
в виде следующего алгоритма. |
|
Алгоритм 3.2. |
10. |
Ш а г 1. Положить К = 1010, М = 1, N = |
Ша г 2. Провести Серию из N бросков.
Ша г 3. Если обнаружены значимые отклонения от гипотети ческого закона распределения, то перейти к шагу 4; иначе пере йти к шагу 10.
Ша г 4. Положить М = 2N.
Ш а г 5. Если М < Q, перейти к шагу 6; иначе перейти к ша гу 9. - *
Шаг 6. Провести серию из М бросков.
Ша г 7. Бели обнаружены значимые отклонения от гипотети
ческого закона распределения, перейти к шагу 8; иначе перейти к шагу 10.
Шаг-8. Положить N = М к перейти к шагу 4.
Ша г 9. Остановиться. Такой останов означает, что метод сужа ющихся окрестностей не будет использоваться, поскольку он тре бует слишком большого числа бросков в серии.
Ша г 10. Положить L = entier [(N + М)!2].
но