Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2020-05-07 | 102 |
5.00
из
|
Заказать работу |
|
|
Существуют несколько классов задач, которые удовлетворяют общей задаче динамического программирования. Каждый из классов имеет свой метод решения, обычно представляется наиболее характерной задачей. Простейшие задачи связаны с выбором на каждом шаге одного из двух возможных решений.
Задача о числе траекторий
В прямоугольной таблице, разбитой на клетки (n строк и m столбцов), из левого верхнего угла с координатами (1, 1) нужно переместиться в правый нижний (n, m), перемещаться на каждом шаге можно только вниз или вправо. Составить программу для определения числа всех возможных траекторий. На Рис. 5 показаны некоторые возможные траектории.
Обозначим L(i, j) число траекторий до клетки (i, j). Таким образом, L(n, m) – число возможных траекторий, которое требуется найти.
Рис. 5. Возможные траектории в задаче о числе траекторий
1 | 2 | m -1 | m | ||
1 | |||||
2 | |||||
n |
Все траектории в клетку (n, m) ведут или из (n, m-1), или из (n‑1, m), поэтому их можно сосчитать как сумму этих траекторий:
L(n, m) = L(n-1, m) + L(n, m-1)
Таким образом, решение задачи разделено на решение этой же задачи для меньших значений параметров.
При этом в любую клетку первой строки и первого столбца можно попасть только по одной траектории.
L(i, 1) = L(1, j) = 1
Текст программы, которая подсчитывает число траекторий для произвольных n и m (Рис. 6), и результат ее работы (Рис. 7) представлены ниже.
Рис. 6. Программа подсчета числа траекторий
# include <iostream>
using namespace std;
// Подсчет числа траекторий для прямоугольника n x m
int L(int n, int m)
{
return (n==1 || m==1)? 1: L(n-1,m) + L(n,m-1);
}
// Подсчет числа траекторий
|
int main ()
{
cout << L(10,10) << " " << L(15,15) << "\n";
return 0;
}
Рис. 7. Листинг программы подсчета числа траекторий
48620 40116600
Задание: составив программу, вычислить число траекторий для (8, 3).
Таким образом, если по какой-то причине нужно перебрать все траектории для выбора в каком-то смысле наилучшей, то уже для прямоугольника 15 x 15 объем вычислений определен обработкой 40116600 траекторий. Программа (Рис. 6) подсчитывала число траекторий около 6 секунд. После изменения программы подсчета, как это показано на Рис. 8, получается таблица значений (Таблица 1).
Большой объем вычислений можно объяснить многократным выполнением одних и тех же операций. Например, L (i, j) нужно вычислять и при вычислении L (i +1, j), и при вычислении L (i, j +1). Однако, можно поступить и по-другому: если мы запомним найденное значение L (i, j), то второй раз его находить не будем, это и представляет основную идею методов динамического программирования.
Рис. 8. Программа для построения зависимости числа траекторий от размера таблицы
// Таблица числа траекторий
int main ()
{
int n, m;
for (n = 1; n <= 11; n++)
{
cout << "\n";
for (m = 1; m <= 11; m++)
cout << L(n, m) << "\t";
}
return 0;
}
Таблица 1. Зависимость числа траекторий от размера таблицы
n/m | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
3 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 | 66 |
4 | 1 | 4 | 10 | 20 | 35 | 56 | 84 | 120 | 165 | 220 | 286 |
5 | 1 | 5 | 15 | 35 | 70 | 126 | 210 | 330 | 495 | 715 | 1001 |
6 | 1 | 6 | 21 | 56 | 126 | 252 | 462 | 792 | 1287 | 2002 | 3003 |
7 | 1 | 7 | 28 | 84 | 210 | 462 | 924 | 1716 | 3003 | 5005 | 8008 |
8 | 1 | 8 | 36 | 120 | 330 | 792 | 1716 | 3432 | 6435 | 11440 | 19448 |
9 | 1 | 9 | 45 | 165 | 495 | 1287 | 3003 | 6435 | 12870 | 24310 | 43758 |
10 | 1 | 10 | 55 | 220 | 715 | 2002 | 5005 | 11440 | 24310 | 48620 | 92378 |
11 | 1 | 11 | 66 | 286 | 1001 | 3003 | 8008 | 19448 | 43758 | 92378 | 184756 |
Мы могли заполнить таблицу, приведенную выше, начиная с угла (1,1) по тому же рекуррентному соотношению:
L(n, m) = L(n-1, m) + L(n, m-1)
Ход такого вычисления называется обратным (нисходящим). Программа, которая выполняет такие вычисления, представлена на Рис. 9, ее листинг совпадает с представленным на Рис. 7. Она использует промежуточную память размером (n+1) ´ (m+1), однако выполняется очень быстро.
|
Рис. 9. Программа подсчета числа траекторий обратным ходом
#include <iostream>
using namespace std;
// Обратный ход подсчета числа траекторий
# define A(i,j) a[(i)*m+(j)]
int din (int n, int m)
{
int i,j, *a = new int [(n+1)*(m+1)];
for (i = 1; i<=n; i++)
for (j = 1; j<=m; j++)
A(i,j) = ((i==1)||(j==1))? 1: A(i-1,j) + A(i,j-1);
i = A(n, m);
free (a);
return i;
}
// Подсчет числа траекторий
int main ()
{
cout << din(10,10) << " " << din(15,15);
return 0;
}
Например, для вычисления числа траекторий L(8,3) будут получены только значения в затененной части (Таблица 1).
|
|
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!