Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
 2020-05-07 |
 179 |
из
5.00
|
Заказать работу |
|
|
|
|
Математики подсказали для предыдущей задачи и другой путь решения. Любая траектория состоит из (n-1 + m-1) шагов, из которых (n-1) – вниз, (m-1) – вправо. Общее количество способов, которыми можно выбрать среди (n-1 + m-1) шагов те (n-1), которые направлены вниз, будет 
.
Биномиальные коэффициенты могут быть получены тремя путями:
– по формуле 
– на основе рекуррентного соотношения: 
– обратным ходом метода динамического программирования
Второй способ может быть запрограммирован так
(http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html):
Рис. 10. Биномиальный коэффициент, прямой ход
function bin_coeff (n: integer; m: integer) return integer is begin if m = 0 or m = n then return 1; else return bin_coeff(n-1, m-1) + bin_coeff(n-1, m); end if; end bin_coeff;
В противоположность этому, метод динамического программирования использует это же отношение, но конструирует таблицу всех (n+1)(m+1) биномиальных коэффициентов 
для каждого значения i от 0 до n и каждого значения j от 0 до m.
Рис. 11. Биномиальный коэффициент, обратный ход
function bin_coeff (n: integer; m: integer) return integer is
type table is array (0..n, 0..n) of integer;
C: table;
i, j: integer;
Begin
for i in 0..n loop
C(i, 0):= 1;
C(i, i):= 1;
for j in 1..i-1 loop
C(i, j):= C(i-1,j-1)+C(i-1,j);
end loop;
end loop;
return C(n, m);
end bin _ coeff;
Задания:
1. Для второго алгоритма с учетом того, что нам не нужны промежуточные значения C, определить, нельзя ли использовать память только размером m +1.
2. Переписать алгоритмы на языке C++ с учетом первого задания.
Рис. 12. Решение задачи на языке C++
int bin_coeff (int n, int m){ int i, j, *C = new int [ (m = min (m, n-m)) +1 ]; C [0] = 1; for (j = 1; i <= m; j++) C[j] =0; for (i = 1; i <= n; i++) { for (j = min(i, m); j > 0; j --) { C[j] += C[j-1]; } } return C [ m ];}
Видимо, это наиболее быстрый и точный алгоритм вычисления биномиальных коэффициентов (исключая табличный метод). Быстрота достигается тем, что отсутствуют операции умножения и деления, они заменены m ´ n/2 более быстрыми операциями сложения. Точность определяется только разрядностью используемых чисел. При умножении же понадобится контроль за переполнением, если арифметика целочисленная, или использование плавающей арифметики, в любом случае разрядность при той же точности, как при сложении, должна быть как минимум в два раза больше.
|
|
Полученный при выполнении задания вывод важен для сокращения используемой памяти при решении некоторых задач метода динамического программирования, в которых не используются значения для всех промежуточных результатов. А для данной задачи m = min (m, n- m) использует соотношение: C(n, m) == C(n, n- m).
1.4.3. Задача о выборе траектории [3]
В прямоугольной таблице в клетках расставлены целые неотрицательные числа. Из левого верхнего угла нужно переместиться в правый нижний, перемещаться на каждом шаге можно только вниз или вправо. Среди всех допустимых траекторий движения нужно выбрать такую, при которой сумма чисел в клетках, через которые она проходит, максимальна.
Рис. 13. Решение задачи о выборе оптимальной траектории
| n/m | 1 | 2 | 3 |
| 1 | 2 | 1 | 3 |
| 2 | 4 | 1 | 3 |
| 3 | 1 | 2 | 2 |
| 4 | 2 | 1 | 1 |
Для представленного примера (Рис. 13) оптимальная траектория выделена серым цветом, сумма чисел в ней равна 13. Для этого примера перебрать возможные траектории просто, их всего десять. Число возможных траекторий растет очень быстро с ростом размера доски. Например, для доски 10 x 10 число траекторий будет 48 620, для доски 15 x 15 – 40 116 600 (см. 1.4.1. Задача о числе траекторий на с.12). Добавление единицы в число строк или столбцов увеличивает число траекторий примерно в два раза. Перебрать все варианты для большой таблицы не позволит и очень быстродействующий компьютер.
Обозначим w(i, j) число, стоящее в клетке (i, j), а W(i, j) – сумму оптимальной траектории из клетки (1, 1) до клетки (i, j). Величины находятся в таком соотношении:
W(i, j) = w(i, j) + max (W (i-1, j), W (i, j-1))
|
|
Действительно, в клетку (i, j) можно попасть или сверху, из клетки (i‑1, j) – или слева, из (i, j-1). Максимальную сумму даст одна из двух траекторий, она и будет оптимальной. Таким образом, задача разделена на две части, каждая из которых решается так же, как и сама задача.
Для граничных клеток суммы будут строиться так:
W(1, 1) = w(1, 1), так как для этой клетки нет ни верхней, ни правой.
W(1, j) = w(1, j) + W(1, j-1),
W(i, 1) = w(i, 1) + W(i-1, 1) – в этих случаях траектория придет из одного направления.
Соответственно для поиска суммы оптимальной траектории прямым ходом можно использовать программу (Рис. 14).
Рис. 14. Программа определения суммы для оптимальной траектории
#define w(i,j)...
int W(int n, int m)
{
return
(n==1 && m==1)? w(1, 1) :
(n==1)? w(1, m)+W(1, m-1):
(m==1)? w(n, 1)+W(n-1, 1):
w(n, m) + max (W(n-1,m), W(n,m-1));
}
Метод динамического программирования обратным ходом для этой задачи использует число операций, пропорционально размеру таблицы. Построение оптимальной траектории начинается с клетки (1, 1). Для каждой из клеток (i, j) определяется W(i, j), в таблице ниже она записана справа.
Таблица 2. Построение суммы для оптимальной траектории в клетках
| w | W | ||||||
| n/m | 1 | 2 | 3 | n/m | 1 | 2 | 3 |
| 1 | 2 | 1 | 3 | 1 | 2 | 3 | 6 |
| 2 | 4 | 1 | 3 | 2 | 6 | 7 | 10 |
| 3 | 1 | 2 | 2 | 3 | 7 | 9 | 12 |
| 4 | 2 | 1 | 1 | 4 | 9 | 10 | 13 |
После построения таблицы W оптимальная траектория находится тривиально в обратном направлении, начиная с клетки (n, m): в каждой ячейке выбирается направление (вверх или влево) в ячейку, где сумма W больше – 13, 12, 10, 7, 6, 2. При равных суммах выбор произволен: оптимальной – с одинаковой суммой может оказаться не одна траектория, а две или несколько.
|
|
|
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!