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

Здравствуйте , кому ни трудно помогите не с простой задачкой . Задача сделана по предмету Математические методы . Задачу необходимо решить одним из трёх способов : Delphi ,Pascal , Excel .

Напишу условие и ход решения задачи .
Условие: Проложить трубопровод между двумя пунктами А и В так, чтобы суммарные затраты на его изготовление были минимальные.
Решение задачи:Разделим расстояние между пунктами А и В на шаги (отрезки). На каждом шаге можем
двигаться либо строго на восток (по оси X), либо строго на север (по оси Y). Тогда путь от А в В
представляет ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей.
Затраты на сооружение каждого из отрезков известны на рисунке в млн р.

Разделим расстояние от А до В в восточном направлении на 4 части, в северном – на 3 части. Путь
можно рассматривать как управляемую систему, перемещающуюся под влиянием управления из
начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет
характеризоваться двумя целочисленными координатами х и у. Для каждого из состояний системы
(узловой точки) найдем условное оптимальное управление. Оно выбирается так, чтобы стоимость всех
оставшихся шагов до конца процесса была минимальна. Процедуру условной оптимизации проводим в
обратном направлении, т.е. от точки В к точке А.
Найдем условную оптимизацию последнего шага:

В точку В можно попасть из B1 или В2. В узлах запишем стоимость пути. Стрелкой покажем минимальный путь.

Рассмотрим предпоследний шаг:

Min (8+8,10+7)=min(16,17)=16
т.е. по оси Y.
Условную оптимизацию проводим для всех остальных узловых точек

Получим Xопт=(в,в,с,c,в,c), где с — север, в —восток.
Минимальные затраты составляют: 4+4+5+6+8+8=35 млн р.

О т в е т : Прокладывать путь целесообразно по схеме: в, в, с, с, в, с при этом затраты будут минимальные и составят 35 млн р.

Итого мне нужно сделать такую задачку на одном из трёх : паскаль , делфи , ексель . Но врятле кто то возьмется т.к сдать нужно в понедельник .

0

почитайте, что такое графы...

0

Графы тут не причем. Это задача на использование метода, который называется "динамическое программирование".
Сам метод изложен. Алгоритм описан.
Но не совсем до конца. Можно заметить что шагать нужно по диагоналям.
Точка B - это последняя диагональ.
Например последний шаг - B1, B2 - это предпоследняя диагональ.
Предпоследний шаг - B3, B4, B5 - это предпредпоследняя диагональ.
И так далее.
Второй шаг - это вторая диагональ ( две точки прилегающие к вершине A ).
Первый шаг - это первая диагональ ( сама точка A ).

Собственно осталось только программу написать

0

Сообщение от odip Графы тут не причем. Это задача на использование метода, который называется "динамическое программирование". Сам метод изложен. Алгоритм описан. Но не совсем до конца. Можно заметить что шагать нужно по диагоналям. Точка B - это последняя диагональ. Например последний шаг - B1, B2 - это предпоследняя диагональ. Предпоследний шаг - B3, B4, B5 - это предпредпоследняя диагональ. И так далее. Второй шаг - это вторая диагональ ( две точки прилегающие к вершине A ). Первый шаг - это первая диагональ ( сама точка A ). Собственно осталось только программу написать

спасибо то что помог , но еслиб я знал как написать (

0

Ну, и что здесь сложного? Повернем рисунок на 45 градусов влево, получим массив из 7 строк, первая строка - точка B, потом 2 соседние точки, потом 3, 4, 3, 2,1. Дальше добавляем к элементам второй строки значение первой, потом к элементам 3 строки минимальное из двух элементов предыдущей и т д. В итоге найдём минимальное значение.
Кстати, в excel это гораздо проще - прибавить min двух соседних элементов из предыдущей строки

0

По другому эта задача называется "О наборе высоты"
[Тут была ссылка на другой форум]

0

Сообщение от alexevt Ну, и что здесь сложного? Повернем рисунок на 45 градусов влево, получим массив из 7 строк, первая строка - точка B, потом 2 соседние точки, потом 3, 4, 3, 2,1. Дальше добавляем к элементам второй строки значение первой, потом к элементам 3 строки минимальное из двух элементов предыдущей и т д. В итоге найдём минимальное значение. Кстати, в excel это гораздо проще - прибавить min двух соседних элементов из предыдущей строки

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

0

Есть эта задача на форумах, набери в гугле "задача о наборе высоты", это только другое название

0

Сообщение от alexevt Есть эта задача на форумах, набери в гугле "задача о наборе высоты", это только другое название

набрал в поиске ... ничего не нашел путного ) кинь лучше ссылку в личку

0

Заказ выполнил.

1

Stepler
Спасибо тебе. Выручил! Сделал все в короткие сроки, очень качественно, за небольшие деньги. Всем рекомендую Степлера! Еще раз огромное спасибо!

Теперь я застрял на этой задаче.
Самый первый вопрос, который возник, это как хранить такую структуру. Завести 2 матрицы - одна хранит горизонтальные пути, а вторая вертикальные? Или можно придумать, что-нибудь более хитрое? Подскажите, если не сложно.

0

Я тогда делал на делфи, вся таблица хранилась в StringGrid.

0

То есть узлы отмечались нулями и в последствии заполнялись нужными результатами? Если так, то задача кажется все менее простой.

0

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

0