Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Топ:
Оснащения врачебно-сестринской бригады.
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2020-05-07 | 100 |
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).
|
|
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!