Числа Фибоначчи и поиск экстремума

Рассмотрим следующую задачу. Имеются две величины x и y, связанные функциональной зависимостью. Известно, что когда x пробегает промежуток [ a, b ], величина y сначала убывает, затем возрастает и в некоторой точке принимает свое наименьшее значение. Более формально: на промежутке [ a, ] величина y убывает, на промежутке [, b ] возрастает, а в точке  принимает наименьшее значение. При этом не исключается, что a =  (величина y возрастает на всем промежутке) или  = b (величина y убывает на всем промежутке). Требуется указать оптимальный алгоритм определения минимума, т. е. приближенного нахождения точки минимума и значения функции в этой точке при условии, что разрешается произвести n наблюдений: можно произвольным образом выбрать n точек x 1, x 2, …, xn на промежутке [ a, b ] и получить соответствующие им значения y 1, y 2, …, yn.

Уточним понятие оптимальности. Пусть Ω – некоторый

алгоритм определения точки минимума. Параметрами, определяющими его работу, служат величины n, a, b. Алгоритм Ω может быть применен к любой функции y = f (x), определенной на промежутке [ a, b ], которая убывает на [ a, ] и

возрастает на [, b ], где  – некоторая (неизвестная) точка из

[ a, b ]. Будем для краткости называть такие функции функциями с одним минимумом (рис. 3).

a  b

Рис. 3

Множество всех функций с одним минимумом на промежутке [ a, b ] обозначим через V (a, b) (или просто V, если из контекста ясно, о каком промежутке идет речь). Результатом применения алгоритма Ω к функции f ∈ V является некоторая пара чисел (, ) такая, что  ∈ [ a, b ] – приближенное значение точки минимума, а  = f (). Мы будем писать  = Ω(f; n, a, b) или просто  = Ω(f), когда ясно, каковы значения параметров n, a, b. Качество алгоритма будем оценивать абсолютной величиной погрешности определения точки минимума в наихудшем случае:

(Ω) = sup {| – |: f ∈ V }.

Будем считать алгоритм Ω оптимальным, если он дает наименьшую ошибку, т. е. (Ω) ≤ (Ω′) для любого алгоритма определения минимума Ω′.

Таким образом, если положить

ф0  min

sup

щ− о,

Ω f

то 0 = (Ω′) для оптимального алгоритма Ω.

Вообще говоря, значение 0 зависит от числа допустимых наблюдений n и промежутка [ a, b ]. Легко понять, что при фиксированном числе наблюдений существенным является не сам отрезок [ a, b ], а его длина l = b – a, так что 0 = 0(n, l). Далее, относительно переменной l функция 0 = 0(n, l) является однородной первой степени: 0(n,  l) = 0(n, l) для  > 0 (оптимальность алгоритма не зависит от выбора единицы измерения длины). В оставшейся части параграфа будет

установлено, что

0(n, l) =

l,

Fn  2

где Fn +2 – число Фибоначчи. При этом в оптимальном алгоритме в качестве первых точек наблюдения берутся

«фибоначчиевы узлы»:

c  a 

Fn

Fn 2

 b − a ;

d  a 

Fn 1  b − a .

Fn 2

Начнем с анализа алгоритмов поиска минимума при малом числе наблюдений.

1. При n = 0 алгоритма поиска минимума не существует: чтобы указать (пусть и произвольным образом) точку и значение функции в ней, нужно произвести хотя бы одно

наблюдение – вычисление значения функции в этой точке. При n = 1 оптимальный алгоритм состоит в том, чтобы в качестве  указать середину отрезка [ a, b ]. В этом случае | – | ≤ l/2, где бы ни располагалась точка минимума . При этом одно наблюдение не дает никакой информации о расположении точки минимума. В частности, возможно  = a или  = b. Какова бы ни была точка , имеем | – | ≥ l/2 для функции с минимумом в точке a, или | – | ≥ l/2 для функции с минимумом в точке b. Значит,

sup {| – |: f ∈ V } ≥ l /2.

Таким образом,

0(1, l) = l /2.

2. Рассмотрим случай, когда допустимы два наблюдения, n = 2. Пусть x 1 и x 2 – точки, в которых производились наблюдения, а y 1, y 2 – значения функции в точках x 1 и x 2 соответственно. Для определенности будем считать, что x 1 < x 2. Если y 1 ≤ y 2, то можно утверждать, что точка

минимума расположена на отрезке [ a, x 2] (рис. 4).

a x 1 

x 2 b

a  x 1 x 2 b

Рис. 4

Так как лимит наблюдений (вычислений значения функции) исчерпан, лучшим претендентом на роль точки минимума в этом случае служит x 1. Наибольшее отклонение 1 от настоящей точки минимума получится в том случае, когда минимум достигается в концевой точке отрезка [ a, x 2], наиболее удаленной от x 1, то есть

1 = max { x 1 – a, x 2 – x 1 }.

Аналогично при y 2 ≤ y 1 лучшим претендентом на роль точки минимума служит x 2. Отклонение от настоящей точки минимума в «наихудшем» случае составляет

2 = max { b – x 2, x 2 – x 1 }.

Положим

 = max {1, 2 } = max { x 1 – a, b – x 2, x 2 – x 1 }.

Так как

(x 1 – a) + (b – x 2) + (x 2 – x 1) = b – a,

то  принимает наименьшее значение 0 в случае, когда

x 1 – a = b – x 2 = x 2 – x 1 = (b – a)/3,

и при этом 0 = (b – a)/3. Следовательно,

0(2, l) = l /3.

3. Случай трех наблюдений, n = 3, особенно поучителен.

Покажем, что в этом случае 0 = l /5, а в оптимальном алгоритме две точки наблюдения суть

3223

x 10

 5 a  5 b,

x 20

 5 a  5 b,

а третья точка определяется как

41

при f (x 10) ≤ f (x 20),и

x 30

 5 a  5 b

14

при f (x 10) > f (x 20).

x 30

 5 a  5 b

Если f (x 30) ≤ f (x 10) ≤ f (x 20) (в этом случае ∈[ a, x 10]), то полагаем  = x 30. Если f (x 10) ≤ f (x 20), но f (x 30) > f (x 10) (в этом

случае ∈[ x 30, x 20]), то полагаем  = x 10.

a x 30 x 10 x 20

b a x 30 x 10 x 20 b

Рис. 5

Погрешность в худшем случае составит x 30 – a = x 20– x 10 = l /5 (рис. 5).

Аналогично, если f (x 10) > f (x 20), полагаем  = x 20 при f (x 20) ≤ f (x 30), или  = x 30 при f (x 20) < f (x 30). Здесь погрешность в худшем случае также равна l /5.

Покажем теперь, что при ином выборе точек наблюдения погрешность (в неблагоприятном случае) окажется больше чем l /5.

Предположим, что произведены два наблюдения в точках x 1

и x 2, для определенности пусть x 1 < x 2. Если f (x 1) ≤ f (x 2), то

можно утверждать, что точка минимума расположена на отрезке [ a, x 2]. Погрешность, с которой можно, произведя два наблюдения, найти точку минимума на отрезке длины x 2 – a,

оценивается величиной

0(2, x 2 – a) =

2

x 2 − a l

3

ф0 (2, l) =

x 2 − a l

⋅1=

x 2 − a.

3 l

Если

x 2  x 20

5 a 5 b, то 0(2, x 2 – a) > (b – a)/5 = l /5.

Аналогично можно показать, что и при x 2 < x 20 погрешность определения точки минимума в худшем случае превосходит l /5. Таким образом, если x 2 ≠ x 20, погрешность в определении минимума превосходит l /5. Точно так же доказывается, что и при x 1 ≠ x 10 погрешность в определении минимума превосходит l /5.

Тем самым описанный в начале этого пункта алгоритм оказывается оптимальным алгоритмом определения минимума

при трех наблюдениях, и

0(3, l) = l /5.

Приведем теперь общее рекурсивное описание оптимального алгоритма поиска минимума.

Обозначим описанные выше оптимальные алгоритмы поиска минимума при одном, двух или трех допустимых наблюдениях через 1, 2, 3 соответственно. Мы дадим рекурсивное описание последовательности алгоритмов 1, 2, 3, …, в которой  k – алгоритм поиска минимума при k допустимых наблюдениях. Параметрами алгоритма  k служат

концы отрезка [ a, b ], на котором ищется минимум, аргументом

– функция y = f (x), определенная на отрезке [ a, b ]. Результатом работы алгоритма является пара чисел  и  = f ().

Предположим, что уже имеются описания алгоритмов 1,

2, …,  n. При этом алгоритмы удовлетворяют следующим требованиям:

1) при исполнении алгоритма  k значения функции f

вычисляются k раз;

2) если k ≥ 2, первые два вычисления производятся в точках

Fk 1

Fk 2

a  Fk b,

Fk 2

Fk

Fk 2

a  Fk 1 b;

Fk 2

3) погрешность определения точки минимума в худшем случае составляет  k (l) = l / Fk +2, где l = b – a – длина отрезка;

4) алгоритм  k является оптимальным алгоритмом поиска минимума с числом наблюдений, не превосходящим k.

Дадим теперь описание алгоритма  n +1. Положим

x  Fn  2 a 

Fn 1 b, x

 Fn 1 a  Fn  2 b.

1 Fn 3

Fn 3

2 Fn 3

Fn 3

Вычисляем f (x 1) и f (x 2). Пусть сначала f (x 1) ≤ f (x 2).

Применим алгоритм  n для поиска минимума на отрезке [ a, x 2]. Пусть  и  = f () – результат этого применения. Примем пару чисел  и  = f () в качестве результата применения алгоритма  n +1 к отрезку [ a, b ]. При исполнении

алгоритма  n применительно к отрезку [ a, x 2] первые два

вычисления должны производиться в точках

Fn 1

Fn 2

a  Fn

Fn  2

x 2,

Fn

Fn 2

a  Fn 1

Fn  2

x 2.

Используя тождество

2 2 2

Fn Fn 3  Fn 1 =

получаем

(Fn  2 − Fn 1)(Fn  2  Fn 1)  Fn 1  Fn  2,

F F

x 2 =

Fn a 

Fn 1

 Fn 1 a 

Fn 2

b =

n 2

n 2

Fn 2

Fn 2

Fn 3

Fn 3

F F  F 2

= n n 3 n 1 a 

Fn 2 Fn 3

Fn 1

Fn 2

Fn 2 b =

Fn 3

Fn 2 Fn 3

Fn 1

Fn 2

Fn 2 b =

Fn 3

= Fn 2 a 

Fn 3

Fn 1 b 

Fn 3

x 1,

так что одно из двух вычислений уже выполнено, и для последующего исполнения алгоритма  n потребуется n – 1 вычисление. В общей сложности (с учетом вычислений f (x 1) и f (x 2)) выполнено n + 1 вычисление значений функции f. Таким образом, алгоритм  n +1 удовлетворяет первым двум требованиям, предшествующим его описанию. Оценим теперь

возникающую погрешность  =  n (x 2 – a). Так как

F F F − F F

x 2 – a =

n 1 a  n 2 b − a = n 1 n 3 a  n 2 b =

Fn 3

Fn 3

Fn 3

Fn 3

= − Fn 2 a  Fn 2 b = Fn 2 (b − a),

Fn 3

то

Fn 3

Fn 3

 =  n (x 2 – a) = (x 2 – a)/ Fn +2 = (b – a)/ Fn +3.

Следовательно, третье условие для  n +1 также выполняется.

Пусть теперь f (x 1) > f (x 2). Применим алгоритм  n для поиска минимума на отрезке [ x 1, b ]. Пусть  и  = f () – результат этого применения. Примем пару чисел  и  = f () в качестве результата применения алгоритма  n +1 к отрезку [ a, b ]. Так же,

как и в предыдущем случае, имеем:

Fn 1 x 

Fn b =

Fn 1  Fn 2 a 

Fn 1 b 

Fn b =

Fn 2 1

Fn 2

Fn 2

Fn 3

Fn 3

Fn 2

F F 2  F F

= n 1 a  n 1 n 3 n b =

F F 2  (F  F)(F − F)

n 1 a  n 1 n 2 n 1 n 2 n 1 b =

Fn 3

Fn 2 Fn 3

Fn 3

Fn 2 Fn 3

= Fn 1 a 

b = Fn 1 a  Fn 2 b  x,

Fn 3

Fn 2 Fn 3

Fn 3

Fn 3 2

так что для исполнения алгоритма  n потребуется n – 1 вычисление. Как и в предыдущем случае, алгоритм  n +1 удовлетворяет обоим требованиям, предшествующим его

описанию. Третье требование тоже выполняется. Так как

b – x 1 = b –

Fn 2 a −

Fn 1 b =

− Fn 2 a

 Fn 3

− Fn 1 b =

Fn 3

Fn 3

Fn 3

Fn 3

− Fn 2 a  Fn  2 b = Fn 2 (b − a),

Fn 3

то

Fn 3

Fn 3

 =  n (b – x 1) = (b – x 1)/ Fn +2 = (b – a)/ Fn +3.

Осталось доказать, что алгоритм  n +1 является оптимальным при условии, что используется не более n + 1 наблюдения.

Пусть t 1 и t 2, t 1 < t 2, – точки первых двух наблюдений. Если f (t 1) ≤ f (t 2), точку минимума нужно искать на отрезке [ a, t 2], в противном случае – на отрезке [ t 1, b ]. Поскольку минимум

может оказаться в одной из концевых точек этих отрезков,

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

t 1 

Fn 2 a 

Fn 3

Fn 1 b.

Fn 3

При f (t 1) > f (t 2) требуется найти точку минимума на отрезке [ t 1, b ], произведя не более n – 1 наблюдения. Можно, правда воспользоваться тем, что значение в точке t 2 ∈ [ t 1, b ] уже вычислено. По индуктивному предположению оптимальным алгоритмом определения минимума за n наблюдений служит  n. Если точка t 2 выбрана в соответствии с алгоритмом  n, то применение этого алгоритма обеспечит

погрешность

 =  n (b – t 1) = (b – t 1)/ Fn +2.

Применение любого другого алгоритма даст большую погрешность. Если

t 1 

то

Fn 2 a 

Fn 3

Fn 1 b,

Fn 3

и, значит,

b – t > F n 2 (b − a)

> (b – a)/ Fn +3.

Следовательно, в оптимальном алгоритме должно быть

t 1 ≥

Fn 2 a 

Fn 3

Fn 1 b.

Fn 3

Если точка минимума  находится на отрезке [ a, t 1], то на ее поиск остается n – 1 наблюдение (знание f (t 1) не дает в этом случае никакой дополнительной информации о расположении точки минимума). По индуктивному предположению оптимальным алгоритмом определения минимума за n – 1 наблюдение является  n –1. Этот алгоритм обеспечивает определение минимума с погрешностью

 =  n –1(t 1 – a) = (t 1 – a)/ Fn +1.

Если

то

t 1 

Fn 2 a 

Fn 3

Fn 1 b,

Fn 3

t 1 – a >

Значит, и в этом случае

F n 1 (b − a).

Fn 3

 > (b – a)/ Fn +3.

Следовательно, в оптимальном алгоритме

t 1 

Fn 2 a 

Fn 3

Fn 1 b.

Fn 3

По симметрии в оптимальном алгоритме должно также

выполняться и равенство

t  Fn 1 a  Fn 2 b.

2 Fn 3

Fn 3

Но справедливость последних двух равенств и означает, что алгоритм  n +1 является оптимальным.

Графы. Основные понятия

Понятие графа

Линейность является характерной чертой большинства современных естественных и искусственных языков. Линейное представление информации (в виде последовательности символов) не является естественным с точки зрения человеческого восприятия. Использование нелинейных форм во многих случаях существенно облегчает понимание. В математике главным средством нелинейного представления информации служат чертежи. Один из видов чертежей – графы, которые, сохранив присущую чертежам наглядность, допускают точное теоретико-множественное описание и тем самым становятся объектом математического исследования.

В разных задачах удобно использовать чертежи разных типов. Соответственно определенные вариации допускает и определение графа. Неотъемлемыми атрибутами графов (при всем разнообразии определений) являются вершины и соединяющие их ребра или дуги.

Граф G = (V, E) состоит из конечного множества вершин (или узлов) V и конечного множества ребер E. Каждое ребро связывает (соединяет) пару вершин. Если ребро a соединяет вершины x и y, то говорят, что ребро a и вершины x, y инцидентны.

Например, на рис. 1

1 a 2

b e g c

f 6

4 h 5 d 3

Рис. 1

изображен граф с шестью вершинами, обозначенными цифрами

1, 2, 3, 4, 5, 6, и восемью ребрами, обозначенными буквами a, b, c, d, e, f, g, h. Ребро a связывает вершины 1 и 2; ребра e и f связывают вершины 1 и 4; ребро g связывает вершину 2 саму с собой; вершина 1 инцидентна ребрам a, b, e, f; ребро c инцидентно вершинам 2 и 3.

Два ребра, связывающие одну и ту же пару вершин (как e и f), называют параллельными (или кратными); ребро, связывающее вершину саму с собой (как g), называют петлей. Иногда в определении графа запрещают наличие параллельных ребер и/или петель, иногда нет. Мы не будем жестко фиксировать определение, оговаривая специально, если это оказывается существенным, какого типа граф рассматривается.

Пусть G = (V, E) – некоторый граф. Граф G ′ = (V ′, E ′), вершины и ребра которого являются вершинами и ребрами графа G, т.е. V ′⊂ V, E ′⊂ E называется подграфом графа G.

Степенью вершины графа называется число ребер графа, инцидентных этой вершине (петли считаются дважды). Степень вершины v обозначается (v). Вершина степени 0 называется изолированной, вершина степени 1 – висячей. Так, для графа на рис. 1 имеем: (1) = (2) = (3) = 4, (4) = 3, (5) = 1, (6) = 0; вершина 5 – висячая, вершина 6 – изолированная.

Несложно убедиться в справедливости следующего

соотношения:

∑д(v)  2 m,

v ∈ V

где m – число ребер графа G = (V, E). В самом деле, ребро, соединяющее вершины x и y, вносит вклад по единице в слагаемые: (x) и (y) (при x = y ребро является петлей и в соответствии с определением вносит вклад 2 в одно слагаемое (x)).

В некоторых случаях рассматриваются направленные ребра,

которые называют дугами. Для дуги, соединяющей две вершины, указывают, из какой вершины она выходит (начало дуги), и в какую входит (конец дуги). На рисунке направление дуги указывают стрелкой. Если все ребра графа направлены, его называют ориентированным графом, или орграфом. В орграфе параллельными считаются дуги, соединяющие одинаковые вершины и имеющие одинаковое направление, то есть дуги, имеющие общее начало и общий конец. Когда мы, имея в виду

ориентированный граф, говорим, что дуга a соединяет вершины

x и y, предполагается, что дуга a направлена от x к y.

На рис. 2 изображен орграф. Из вершины 1 выходят дуги a

и b, в нее входит дуга e.

1 a 2

b e c

4 3

d

Рис. 2

Полустепенью исхода вершины орграфа называется число дуг графа, начинающихся в этой вершине; полустепенью захода

– число дуг графа, заканчивающихся в ней. Полустепени исхода и захода вершины v обозначаются соответственно через +(v) и –(v). Так, для графа на рис. 2 имеем +(1) = 2, –(1) = 1.

Для ориентированного графа G = (V, E), содержащего m дуг,

выполняется следующее соотношение:

∑д (v)  ∑д− (v)  m.

v ∈ V

v ∈ V

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

Подграфом орграфа G называют любой орграф, вершины которого составляют часть множества вершин графа G, а дуги – часть множества его дуг.

Не нашли, что искали? Воспользуйтесь поиском: