Одномерные задачи

Одномерные задачи

Одномерные задачи

Гамильтониан частицы в одномерном, свободном движении (для стационарных состояний) равен:

Тогда уравнение (1) приобретает вид:

где $E_n$ — собственные значения энергии, $\Psi_n$ — собственные функции — решения уравнения (2). Преобразуем уравнение (2) к виду:

где $k2=\frac{2mE}{{\hbar }2}>0.$ Из уравнения (3) получается, что собственному значению $E$ соответствуют следующие функции:

На волновой вектор $(k)$ ограничений не наложено, следовательно, система имеет непрерывный спектр.

Существуют два состояния, которые отвечают одному значению энергии. Это вырожденные состояния. С кратностью вырождения два. Существование вырождения дает возможность строить бесконечное количество состояний, имеющих одно значение энергии.

Прямоугольная потенциальная яма

Допустим, что потенциальная энергия поля задана:

При этом стационарное уравнение Шредингера для одномерногослучая принимает вид:

Задача состоит в поиске значений энергии ($E$) при которых уравнение (4) имеет ненулевое решение, и соответствующих волновых функций. Разумно допустить, что частица не будет находиться в области потенциала равного бесконечности ($\Psi(\left|x\right|>\frac{a}{2})\equiv 0$). Исходя вышесказанного предположения уравнение (4) перепишем как:

Ничего непонятно?

Попробуй обратиться за помощью к преподавателям

где $x\in \left[-\frac{a}{2},\frac{a}{2}\right].$ Для соблюдения условия непрерывности функции $\Psi$, выдвигается требование равенства нулю волновой функции на границах ямы:

Общее решение уравнения (5) запишем в виде:

где $k2=\frac{2mE}{{\hbar }2}$. Использовав условия (6), найдем:

В таком случае для энергии получаем:

где решение при $n=0$ отброшено. Из уравнения (9) следует, что в потенциальной яме с бесконечно высокими стенками, появляется дискретный спектр энергий.

Система собственных функций гамильтониана для частицы в яме имеет вид:

где из условия нормировки получают $A_n=\sqrt{\frac{2}{a}.}$

Гармонический осциллятор

Гармонический осциллятор в квантовой механике определим как частицу имеющую массу $m$ и потенциальную энергию $U=\frac{\varkappa x2}{2}$, где $\varkappa ={\omega }2m=const.$ Запишем уравнение Шредингера для нашего одномерно случая:

Уравнение (11) имеет конечные, однозначные и гладкие собственные функции при соответствующих собственных значениях $E$, которые равны:

Из уравнения (12) следует, что уровни энергии эквидистантны. Нулевая энергия равна $E_0=\frac{\hbar \omega }{2}$. То, что частица не может лежать на дне потенциальной ямы, связано с принципом неопределенности.

Для квантового осциллятора возможны переходы только между соседними «стационарными» уровнями, при этих переходах квантовое число изменяется на единицу. Это так называемое правило отбора для квантового гармонического осциллятора.

При каждом из таких переходов излучается или поглощается фотон, энергия которого равна $\hbar \omega .

$ Надо отметить, что говорить, что в стационарных состояниях квантовый осциллятор испытывает колебания с частотой $\omega \ $не верно.

Пример 1

Задание: Какова вероятность найти частицу в левой трети потенциальной ямы, если прямоугольная потенциальная яма имеет ширину $l$ и бесконечно высокие «стенки»? Частица находится в основном состоянии.

Решение:

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

\[\Psi_1\left(x\right)=\sqrt{\frac{2}{l}}sin\frac{\pi x}{l},0\ \le x\le \frac{l}{3}\left(1.1\right).\]

Вероятность можно найти как:

\[P=\int\limits{\frac{l}{3}}_0{{\left|\Psi_1\right|}2dx=\frac{2}{l}}\int\limits{\frac{l}{3}}_0{{sin}2\frac{\pi x}{l}dx=}\frac{2}{l}\int\limits{\frac{l}{3}}_0{\frac{1}{2}(1-cos\frac{2\pi x}{l})dx=\frac{1}{l}\int\limits{\frac{l}{3}}_0{dx-\frac{1}{l}}}\int\limits{\frac{l}{3}}_0{cos\frac{2\pi x}{l}}dx=\frac{1}{3}-\frac{1}{l}\frac{l}{2\pi }sin{\left.\frac{2\pi x}{l}\right|}{\frac{l}{3}}_0=\frac{1}{3}-\frac{1}{2\pi }sin\frac{2\pi }{3}\approx 0,195.\]

Ответ: $P=0,195.$

Пример 2

Задание: Частица находится в бесконечно глубокой потенциальной яме, ширина которой $l$. Состояние частицы описывается волновой функцией вида:

$\Psi\left(x\right)=Ax(x-l)$. Каково распределение вероятностей разных значений энергии $(p\left(E_0\right),\ p\left(E_1\right),\dots $)?

Решение:

Прежде всего, следует нормировать волновую функцию на единицу, вычислить коэффициент A:

\[A2\int\limitsl_0{x2{(x-l)}2}dx=A2\int\limitsl_0{x2(x2-2xl+l2)dx}=A2\left\{\int\limitsl_0{x4}dx-2l\int\limitsl_0{x3}dx+l2\int\limitsl_0{x2}dx\right\}=A2\left\{\frac{l5}{5}-2l\frac{l4}{4}+l2\frac{l3}{3}=\frac{12-30+20}{60}l5\right\}=\frac{A2l5}{30}(2.1).\]

Волновая функция имеет вид:

\[\Psi\left(x\right)=\sqrt{\frac{30}{l5}}x\left(x-l\right)\left(2.2\right).\]

Разложение волновой функции в ряд по собственным функциям $\Psi_n\left(x\right)=\sqrt{\frac{2}{l}}\ sin\frac{\pi (n+1)x}{l}\ {\rm при}{\rm \ }0\[\Psi\left(x\right)=\sum{C_n\Psi_n\left(x\right)(2.3),}\]

где коэффициенты $C_n$ найдем как:

\[C_n=\sqrt{\frac{60}{l6}}\int\limitsl_0{x\left(x-l\right)sin\frac{\pi(n+1)x}{l}}dx=-\frac{\sqrt{240}}{{\pi }3}\frac{1+{\left(-1\right)}n}{{\left(n+1\right)}3}\left(2.4\right).\]

Вероятность нахождения частицы в квантовом состоянии номер n равна:

\[p_n={\left|C_n\right|}2\left(2.5\right).\]

Используем результат, полученный в (2.4), имеем:

\[p\left(E_0\right)={\left(\frac{\sqrt{240}}{{\pi }3}\frac{1+{\left(-1\right)}0}{{\left(0+1\right)}3}\right)}2=\frac{960}{{\pi }6}\approx 0,999.\] \[p\left(E_1\right)\approx 0,001\]

Ответ: $p\left(E_0\right)\approx 0,999,\ p\left(E_1\right)\approx 0,001$ и т.д.

Источник: https://spravochnick.ru/fizika/predmet_i_zadachi_atomnoy_fiziki/odnomernye_zadachi/

Задачи оптимизации

Одномерные задачи

Лекция 12

Явно или неявнозадачи оптимизации возникают постояннов любой сфере деятельности. Экономическоепланирование , управление, распределениеограниченных ресурсов , анализпроизводственных процессов, проектированиесложных объектов всегда связано споиском наилучшего варианта.

НО ! Прежде чемвоспользоваться математическим аппаратом, надо сформулировать проблему какматематическую задачу , и математическизаписать смысл оценок «хуже» и «лучше».

Численнаяоптимизация – поиск наилучшего вариантауправляемых параметров с точки зрениянекоторого критерия.

Многие задачиоптимизации сводятся к отысканиюэкстремального значения некоторой функции , которую принято называтьцелевой функцией.

Постановка задачии методы исследования зависят от свойствцелевой функции. Если функция задаетсяявной формулой и при этом дифференцируема,то это наиболее простой , в математическойпонимании , случай. Продифференцировав такую функцию , можно найти точки еелокальных экстремумов, направлениявозрастания и убывания .

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

Далее рассмотримрешение одномерных и менее подробномногомерных задач оптимизации

  • Одномерные задачи наиболее просты , на них легче понять постановку вопроса , методы решения и возникающие трудности
  • В ряде случаев одномерные задачи имеют самостоятельный интерес
  • Алгоритм решения многомерных задач часто можно свести к последовательному многократному решению одномерных задач

Самый простойпример задачи оптимизации:

Задача о консервной банке

Указать наилучшийвариант консервной банки фиксированногообъема V, имеющей форму простого круговогоцилиндра.

Вопрос: По какомупризнаку банка считается лучшей ?

Могут быть дваварианта:

  1. Наименьшая поверхность ( расход жести)

  2. Наименьшая длина ( сварной шов )

Таким образом надоисследовать полученные функции наминимум .

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

Имеем:

для оптимизациипо варианту 1:

Получаемрешение или ( подставляя в h)

Тогда оптимальная поверхность будет

Для оптимизациипо варианту 2:

или

Видно , что приизменении самой постановки критерияоптимизации решение задачи различно.

Таким образомвсегда существуют стратегия и тактикавычислительной оптимизации.

Тактика-выбор конкретного варианта при выполненииопределенных этапов решения.

Стратегия– выбор принципа поиска оптимизации.

Одномерные задачи оптимизации

Постановка задачи:

Найти наименьшее( или наибольшее) значение целевойфункции f, заданной на множестве D,принадлежащем арифметическому множествучисел Rn.

Точки множестваDназывают допустимыми точками, D–допустимое множество, f — целевая функция задачи.

Определение:

Точка называется глобальным решением задачи, если

И точка есть локальное решение задачи , если найдется окрестность Uточки , в которой .

Точки экстремума еще называют стационарными.

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

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

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

Скорость измененияфункции в стационарных точках равнанулю.

Правилорешения оптимизации для рассматриваемогокласса функций:

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

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

Значитрешать надо численно.

Определяя значениянепрерывной функции f(x) в некотором конечном числе точекзаданного отрезка [a,b], нужно приближенно найти наименьшее (наибольшее) значение на данном отрезке.

Чаще всего допустимоемножество задачи задается в следующемвиде:

P– прямые ограничения, F,G–функциональные ограничения .Такоеделение весьма условно и в каждомконкретном случае решается исходя изусловий задачи.

Источник: https://studfile.net/preview/8494803/

Одномерные задачи оптимизации

Одномерные задачи

Задача о наилучшей консервной банке

Задачи оптимизации

Проектирование сложных РЭС всегда должно быть направлено на поиск наилучшего варианта с точки зрения намеченной цели.

Многие задачи оптимизации сводятся к отысканию наименьшего (или наибольшего) значения некоторой функции, которую принято называть ЦЕЛЕВОЙ. Постановка задачи и методы исследования существенно зависят от свойств целевой функции и той информации о ней, которая может считаться доступной в процессе решения, а также, которая известна априори (до начала решения задачи).

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

Однако, во многих случаях, целевая функция не задается формулой, ее значения могут быть получены в результате сложных расчетов, браться из эксперимента и о. д. Такие задачи являются более сложными, поэтому для них нельзя провести исследование целевой функции с помощью производной.

Следует также отметить, что сложность задачи существенно зависит от размерности целевой функции, т. е. от числа ее аргументов.

Тем не менее, рассмотрим сначала случай одномерной оптимизации, во-первых, на нем легче понять постановку вопроса, методы решения и возникающие трудности. Во-вторых, алгоритмы решения многомерных задач оптимизации часто сводятся к последовательному, многократному решению одномерных задач.

Пусть перед нами поставлена задача: указать наилучший вариант консервной банки фиксированного объема V, имеющий обычную форму прямого кругового цилиндра.

Рассмотрим два варианта целевой функции (критерия оптимизации):

1) наилучшая банка должна иметь наименьшую поверхность S (на ее изготовление уйдет наименьшее количество жести);

2) наилучшая банка должна иметь наименьшую длину швов (швы нужно сваривать и мы хотим минимизировать трудоемкость этой операции).

Для решения этой задачи запишем формулы для объема банки, ее поверхности и длины швов:

V = πr2h, S = πr2+ 2πrh, ℓ=4πr + h (5.1)

Объем банки задан, это устанавливает связь между радиусом r и высотой h. Выразим высоту через радиус: h = V/(πr2) и подставим полученное выражение в формулы для поверхности и длины швов. В результате получим:

S (r) = 2πr2 + 2V/r, 0 < r < ∞ (5.2)

ℓ (r) = 4πr + V/πr2, 0 < r < ∞ (5.3)

Таким образом, с математической точки зрения, задача о наилучшей консервной банке сводится к определению такого значения r, при котором достигает своего наименьшего значения в одном случае функция S (r), в другом – функция ℓ (r).

Рассмотрим первый вариант задачи. Вычислим производную функции S’ (r):

S’ (r) =4πr — 2V/r2 = 2/r2 (2πr3 – V) (5.4)

Своего наименьшего значения эта функция достигает в точке r = r1, в которой ее производная обращается в нуль. Как не трудно убедиться:

; (5.5)

При этом

(5.6)

Рассмотрим теперь задачу во второй постановке. Продифференцируем функцию ℓ (r).

ℓ’ (r) = 4π – 2V/πr3 = 2/ πr2(2 π2r2 – V) (5.7)

Приравняв производную нулю, получим, что радиус и высота банки, наилучшие с точки зрения критерия минимальности ℓ(r), определяются формулами

, h2 = 2πr2, (5.8)

при этом

. (5.9)

Мы видим, что при разных критериях оптимизации получаются существенно разные ответы.

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

Найти наименьшее (или наибольшее) значение целевой функции f(x), заданной на множестве Х. Определить значение переменной , при котором она принимает свое экстремальное значение.

В математическом анализе при изучении свойств функций, непрерывных на отрезке, доказывается следующая теорема.

ТЕОРЕМА ВЕЙЕРШТРАССА. Всякая функция f(x), непрерывная на отрезке [a, b], принимает на этом отрезке свое наибольшее и наименьшее значение, т. е. на отрезке [a, b] существуют такие точки x1, x2, что для любого выполняются неравенства

f(x1) ≤ f(x) ≤ f(x2) (5.10)

Не исключается, в частности, возможность того, что наименьшее или наибольшее значение достигается сразу в нескольких точках.

В этом легко убедиться, рассмотрев в качестве примера функцию y = sin (x) на отрезке [0, 4π]. Она достигает своего минимального значения, равного -1, сразу в двух точках x = 3π/2, x = 7π/2.

Наибольшее значение, равное 1, достигается также в двух точках: x = π/2, x = 5π/2.

Теорема Вейерштрасса играет в данном случае роль теоремы существования: согласно этой теореме задача оптимизации, в которой целевая функция f(x) задана и непрерывна на отрезке, всегда имеет решение.

Теперь нам предстоит обсудить методы решения задач оптимизации. При их исследовании мы будем предполагать, что целевая функция f(x) дифференцируема на отрезке [a, b] и имеется возможность найти явное выражение для ее производной f’(x).

Функция f(x) может достигать своего наименьшего или наибольшего значения либо в одной из двух граничных точек отрезка [a, b], либо в какой-нибудь его внутренней точке. В последнем случае такая точка обязательно должна быть экстремальной. Учитывая изложенное, можем сформулировать следующее правило решения задачи оптимизации для рассматриваемого класса функций.

Для того чтобы определить наибольшее и наименьшее значение дифференцируемой на отрезке [a, b] функции f(x), нужно найти все ее экстремальные точки на данном отрезке, присоединить к ним граничные точки a, b и во всех точках сравнить значения функции. Наименьшее и наибольшее из них дадут наименьшее и наибольшее значения функции для всего отрезка.

Поскольку граничные точки a, b искать не надо, то с технической точки зрения все сводится к определению экстремальных точек, которые являются корнями уравнения

f’(x) = 0. (5.11)

Для иллюстрации изложенного правила решения задачи оптимизации рассмотрим на отрезке [-2, 3] функцию

f(x) = 3×4 – 4×3 – 12×2 + 2 (5.12)

Вычислим ее производную:

f’(x) = 12×3 – 12×2 – 24x

Таким образом, уравнение (2.62) для определения экстремальных точек принимает вид

x3 – x2 – 2x = 0 (5.13)

Все корни этого уравнения: x1 = -1; x2 = 0; x3 = 2 принадлежат исходному отрезку. Добавляя к ним граничные точки: a = -2 и b = 3, вычислим соответствующие значения функции (2.63):

f(-2) = 34, f(-1) = -3, f(0) = 2, f(2) = -30, f(3) = 29.

Из сравнения этих чисел следует, что наименьшее значение функции f(x) достигается в одной из экстремальных точек х = 2, а наибольшее – в граничной точке х = -2, причем

fmin = f(2) = -30,

fmax = f(-2) = 34.

График функции иллюстрирующий проведенное исследование, изображён на рисунке 5.1.

Рисунок 5.1.

5.3. Численное решение одномерных задач оптимизации

Рассмотрим следующий пример. Химический завод производит некоторое вещество. Выход интересующего нас продукта определяется температурой: y = f(T). Температуру можно варьировать в определенных пределах: T1 ≤ T ≤ T2.

Вид функции f заранее неизвестен, но зависит от используемого сырья. Получив очередную партию сырья, нужно найти температуру T, при которой наиболее выгодно вести производство, т. е.

функция f(T) достигает своего наибольшего значения.

С математической точки зрения мы имеем типичную одномерную задачу оптимизации. В то же время между этой задачей и задачей о консервной банке имеется существенное различие. В данном случае нет никакой формулы для целевой функции f(T).

Чтобы определить ее значение при некоторой температуре Т, нужно провести опыт в лаборатории (если это возможно), либо прямо в производственных условиях.

Совершенно ясно, что возможно лишь конечное число измерений и тем самым функция f(T) будет известна нам в конечном числе точек. Значений ее производных мы вообще определить не можем. Остается добавить, что каждое измерение требует времени, а задерживать производство нельзя.

Поэтому необходимо получить ответ на поставленный вопрос после небольшого числа измерений, т. е. по значениям функции y = f(T) в нескольких точках.

Итак, обсудим математические вопросы, связанные со следующей постановкой одномерной задачи оптимизации, определяя значение непрерывной функции f(х) в некотором конечном числе точек отрезка [a, b], нужно приближенно найти ее наименьшее (или наибольшее) значение на данном отрезке.

Рассмотрим разные подходы к решению этой задачи.

Источник: https://studopedia.su/2_47196_odnomernie-zadachi-optimizatsii.html

Большая Энциклопедия Нефти и Газа

Одномерные задачи

Cтраница 1

Одномерная задача оптимизации в общем случав формулируется следующим образом.

Найти наименьшее ( или наибольшее) значение целевой функции Сѓ / ( С…, заданной РЅР° множестве Р°, Рё определить значение проектного параметра С… & Р°, РїСЂРё котором целевая функция принимает экстремальное значение. Существование решения поставленной задачи вытекает РёР· следующей теоремы.  [1]

Одномерная задача оптимизации РІ общем случае формулируется следующим образом.  [2]

В настоящей работе для решения одномерной задачи оптимизации воспользуемся предложенным в [1] подходом, в основе которого лежит использование свойств скользящих режимов.

Суть подхода заключается в следующем.

Выход оптимизируемого объекта сравнивается с подобранным специальным образом задающим воздействием, которое является монотонно убывающей функцией времени.

Входное воздействие объекта формируется на основе сигнала рассогласования между выходом объекта и задающим воздействием и должно свести это рассогласование к нулю.

Специфика построения такой следящей системы заключается РІ том, что объект управления является нелинейным статическим звеном, локальный коэффициент усиления которого неизвестен Рё меняется как РїРѕ величине, так Рё РїРѕ знаку.  [3]

Представляет интерес сравнительный анализ решений одномерной задачи оптимизации РІ различных постановках.  [4]

Первые три параграфа данной главы посвящены одномерным задачам оптимизации, в двух последних рассматриваются многомерные задачи. Выделение и подробный разбор одномерных задач имеет определенный смысл.

Эти задачи наиболее просты, на них легче понять постановку вопроса, методы решения и возникающие трудности. В ряде случаев, хотя и очень редко, одномерные задачи имеют самостоятельный практический интерес.

Однако самое главное заключается РІ том, что алгоритмы решения многомерных задач оптимизации часто сводятся Рє последовательному многократному решению одномерных задач Рё РЅРµ РјРѕРіСѓС‚ быть поняты без умения решать такие задачи.  [5]

Подставив (5.92) РІ (5.91) Рё используя ограничения, получим одномерную задачу оптимизации.  [6]

Р�так, РѕР±СЃСѓРґРёРј математические РІРѕРїСЂРѕСЃС‹, связанные СЃРѕ следующей постановкой одномерной задачи оптимизации: определяя значения непрерывной функции / ( С…) РІ некотором конечном числе точек отрезка [ Р°, Р¬ ], нужно приближенно найти ее наименьшее ( или наибольшее) значение РЅР° данном отрезке.  [7]

Задачу решают, понижая размерность методом последовательного приближения Рё последующего расчета одномерной задачи оптимизации РљРЎ согласно логико-комбинаторному методу.  [8]

Метод покоординатного СЃРїСѓСЃРєР° РЅРµ требует вычислений производных функции качества Рё РЅР° каждом шаге предполагает решение одномерной задачи оптимизации.  [9]

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

Движение РїРѕ ДН РЅР° малый шаг РЅРµ выводит Р·Р° пределы допустимой области, движение РїРѕ ПДН одновременно улучшает зачение РЇ0, Р° движение РїРѕ НПДН обеспечивает максимальное улучшение значения РЇ0 без нарушения ограничений.  [10]

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

Движение РїРѕ ДН РЅР° малый шаг РЅРµ выводит Р·Р° пределы допустимой области, движение РїРѕ ПДН одновременно улучшает зачение РќРѕ, Р° движение РїРѕ НПДН обеспечивает максимальное улучшение значения РЇ0 без нарушения ограничений.  [11]

� хотя окончательное решение задачи оптимизации не получено, соотношение (4.

133) СЃРІРѕРґРёС‚ решение ( СЏ — 1) — мерной задачи Рє одномерной: подобрать всего лишь РѕРґРЅСѓ концентрацию, после первого реактора РЎ1 СЃ тем, чтобы РёР· цепочки соотношений (4.

133) получить РЎРї РЎРє. Конечно, решение одномерной задачи оптимизации РјРЅРѕРіРѕ легче многомерной.  [12]

� хотя окончательное решение задачи оптимизации не получено, соотношение (2.

174) СЃРІРѕРґРёС‚ решение ( Рї — 1) — мерной задачи Рє одномерной: подбирают концентрацию только после первого реактора РЎ так, чтобы РёР· цепочки соотношений (2.174) получить РЎ РЎРє.

Конечно, решение одномерной задачи оптимизации гораздо легче, чем многомерной.  [13]

В § 2 мы рассмотрели одномерные задачи оптимизации, в которых целевая функция зависит лишь от одного аргумента.

Однако РІ большинстве реальных задач оптимизации, представляющих практический интерес, целевая функция зависит РѕС‚ РјРЅРѕРіРёС… проектных параметров.  [15]

Страницы:      1    2

Источник: https://www.ngpedia.ru/id25696p1.html

Динамическое программирование. Классические задачи

Одномерные задачи

Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа.

Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

Во многих олимпиадных задачах по программированию решение с помощью рекурсии или полного перебора требует выполнения очень большого числа операций. Попытка решить такие задачи, например, полным перебором, приводит к превышению времени выполнения.

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Последовательности

Классической задачей на последовательности является следующая.

Последовательность Фибоначчи Fn задается формулами: F1 = 1, F2 = 1,

Fn = Fn – 1 + Fn – 2 при n > 1. Необходимо найти Fn по номеру n. Один из способов решения, который может показаться логичным и эффективным, — решение с помощью рекурсии: int F(int n) { if (n < 2) return 1; else return F(n - 1) + F(n - 2);}
Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n, пока не дойдем до известных значений.

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования: int F(int n) { if (A[n] != -1) return A[n]; if (n < 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; }} Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение: F[0] = 1;F[1] = 1;for (i = 2; i < n; i++) F[i] = F[i - 1] + F[i - 2];
Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F3), потом следующее и т.д., пока не дойдем до нужного.

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все Fi для i< n), затем, зная решения подзадач, нашли ответ (Fn = Fn – 1 + Fn – 2, Fn – 1 и Fn – 2 уже найдены).

Одномерное динамическое программирование

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

Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n1, n2, …, nk. То есть мы можем говорить о функции T(n1, n2, …

, nk), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи

T(i1, i2, …, ik) при i1 < n1, i2 < n2, …, ik< nk.

Далее мы будем о говорить об одномерном, двумерном и многомерном динамическом программировании при k = 1, k = 2, k > 2, соответственно.

Следующая задача одномерного динамического программирования встречается в различных вариациях.

Задача 1. Посчитать число последовательностей нулей и единиц длины n, в которых не встречаются две идущие подряд единицы.

При n< 32 полный перебор потребует нескольких секунд, а при n = 64 полный перебор не осуществим в принципе. Для решения задачи методом динамического программирования сведем исходную задачу к подзадачам.

При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли Kn – 1, Kn – 2 — число таких последовательностей длины n – 1 и n – 2.

Посмотрим, какой может быть последовательность длины n. Если последний ее символ равен 0, то первые n – 1 — любая правильная последовательность длины

n – 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего Kn – 1. Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые
n – 2 символа — любая правильная последовательность длины n – 2, число таких последовательностей равно Kn – 2.

Таким образом, K1 = 2, K2 = 3, Kn = Kn – 1 + Kn – 2 при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

Двумерное динамическое программирование

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

Приведем пару формулировок таких задач:

Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз.

Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

Задача 3. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

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

Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i,j) можно прийти только сверху или слева, то есть из клеток с координатами (i – 1, j) и (i, j – 1):

Таким образом, для клетки (i, j) число маршрутов A[i][j] будет равно

A[i – 1][j] + A[i][j – 1], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании. Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A[0][0] необходимо поместить число 1.

В задаче 3 в клетку с координатами (i, j) мы можем попасть из клеток с координатами

(i – 1, j), (i, j – 1) и (i – 1, j – 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[i – 1][j], W[i][j – 1],
W[i – 1][j – 1]. Чтобы найти минимальный вес для (i, j), необходимо выбрать минимальный из весов W[i – 1][j], W[i][j – 1], W[i – 1][j – 1] и прибавить к нему число, записанное в текущей клетке: W[i][j] = min(W[i–1][j], W[i][j – 1], W[i – 1][j – 1]) + A[i][j]; Данная задача осложнена тем, что необходимо найти не только минимальный вес, но и сам маршрут. Поэтому в другой массив мы дополнительно для каждой клетки будем записывать, с какой стороны в нее надо попасть. На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма. В каждую из уже пройденных клеток ведет ровно одна стрелка. Эта стрелка показывает, с какой стороны необходимо прийти в эту клетку, чтобы получить минимальный вес, записанный в клетке. После прохождения всего массива необходимо будет проследить сам маршрут из последней клетки, следуя по стрелкам в обратную сторону.

Задачи на подпоследовательности

Рассмотрим задачу о возрастающей подпоследовательности.

Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности.

Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i. Пусть исходная последовательность хранится в массиве A.

В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1

Источник: https://habr.com/post/113108/

Booksm
Добавить комментарий