выбор оптимального маршрута перевозки грузов , алгоритм + структуры данных

Всем хай! Сходу к делу!
Есть сеть дорог, соединяющих города. Известны стоимости перевозки груза между городами. Используя метод динамического программирования, найти самый экономный маршрут доставки груза из города №1 в город №10: вывести все города, входящие в маршрут + общую стоимость перевозки. На рис.показана сеть городов и стоимость перевозки грузов.

Прикреплённая картинка

Поштудировал описание задачи в инете.
Вот чисто математически + графически я понимаю, как это решается. Т е на бумаге все легко посчитаю, нарисую стрелочки оптимального маршрута и пр. С этим проблем нет. Проблема в том, как это ПРАВИЛЬНО закодировать, а если быть более точным, нужен норм.алгоритм + правильные структуры данных для всего этого.

Пусть входные данные задаются в виде весовой матрицы, т е матрицы размером N * N (N = 10). На пересечении строки и колонки стоит стоимость перевозки, если между этими городами есть связь.
1. Ищем решение от конца в начало, т е анализ начинается от города №10 и продвигаемся к №1.
2. Мне казалось, что здесь пригодится структура данных ОЧЕРЕДЬ.

Помещаем в очередь вершину №10.
На следующем этапе помещаем в очередь все вершины, смежные с №10. Это вершины №7, №8 и №9. Одновременно с этим считаем расстояние до каждой из этих вершин из №10. После этого вершину №10 удаляем из очереди и помечаем ее как обработанную.
На следующем этапе нужно рассмотреть ВСЕ СМЕЖНЫЕ вершины с любой из вершин №7, №8 и №9.
Тут есть проблемка, т к, например, вершина №5 является одновременно смежной и для №7 и для №8, т е если вершины {7, 8, 9} обрабатываются последовательно, то вершина №5 будет учитываться ДВАЖДЫ, что приведет к чему-то нехорошему). Я прекрасно понимаю, что для вершины №5 рассматривается МИН(5-7, 5-8). Для вершины №6 = МИН(6-8, 6-9).
ТО ЕСТЬ ОЧЕРЕДЬ ЗДЕСЬ ДЛЯ АНАЛИЗА НЕ НУЖНА, ТАК?? или нужно заводить 2 очереди для разных "групп" вершин. думаю, что это бредовая затея) В принципе, на каких-то переборах очередей в циклах, это все можно реализовать, но, скорее всего, будет крайне неэффективно и неправильно с позиции структур данных.

Также ведь еще нужно найти все города, входящие в маршрут, т е куда их записывать в процессе анализа.
И, собственно, про динамическое программирование. Насколько понимаю, ДП требует, чтобы было использовано:
1. зависимость элементов динамики друг от друга
2. значение начальных состояний

ну с п.2 вроде понятно. Стоим в вершине №10 и стоимость перевозки равна 0.
с п.1, хм. Ну есть зависимость ведь, чтобы перейти к анализу, например №5, сначала анализируем №7 и №8. При анализе №7 анализируем №10.
Также хочется понять, нужна ли в коде какая-то ядровая функция, которая, на вход принимает номер обрабатываемой вершины, а на выходе, например, выдает минимум затрат для этой вершины или вообще все делается в циклах на стартовой весовой матрице.

подскажите как быть-то, буду признателен

Итак, у нас есть множество вершин Vi, множество ребер Eij, для каждого ребра, соединяющего Vi и Vj, задан неотрицательный вес w(i, j), необходимо найти и вывести кратчайший путь из V1 в указанную вершину.

Поскольку веса ребер неотрицательные, можно использовать алгоритм Дейкстры. Тогда для каждого Vi получим d(i) - стоимость минимального пути V1 -> Vi. Затем нужно построить список узлов, входящих в этот путь.

Строим путь от конца к началу. Заведем список, состоящий из одной вершины (конечной). Затем в цикле:
- смотрим на первую вершину в списке (Vk), ищем все вершины Vi, для которых есть ребро Eik;
- для каждой Vi вычисляем стоимость d(i) + w(i, k), если эта сумма равна d(k), значит мы пришли в Vk именно из этой вершины Vi, заносим ее в начало списка (может получиться, что это условие выполняется для нескольких вершин Vi, тогда неважно, какую из них включать в путь - стоимость результата будет одна и та же);
- продолжаем, пока в списке не окажется V1 - тогда список и будет искомым путем.

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

если можно заюзать Дейкстру, тогда мне все сразу понятно и все смогу найти, т к уже не один раз его УСПЕШНО кодировал на практике)

ТО ЕСТЬ ИСПОЛЬЗОВАТЬ ДЕЙКСТРУ МОЖНО, ДА??)

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

Странные какие-то задачи. Во всех вместо эффективного метода решения предлагается использовать что-то не совсем подходящее.

А каковы принципы динамического программирования?

Ну и алгоритм, отвечающий названным принципам
Конкретно этот граф можно разбить на слои (точнее он уже разбит).
В первом слое три города (2, 3, 4).
Считаем минимальные стоимости доставки до узлов первого слоя из начального узла.
Во втором слое города 5 и 6.
Считаем минимальные стоимости доставки до них из городов первого слоя (плюс стоимости доставки до этих городов).
То же делаем для третьего слоя (7, 8, 9) и для целевого города (10).

Ну и требования к графу, чтобы динамическое программирование на нём работало:
Граф должен разбиваться на слои так, чтобы:
1. Вершины каждого слоя были связаны с вершинами предыдущего и следующего слоя. Не должно быть рёбер внутри слоя или прыгающих через слой.
2. В двудольном подграфе содержащем соседние слои не должно быть цепей с суммарным весом меньше ребра, соединяющего концы цепи.
Из-за этих требований обычно динамическое программирование на графах не применяется - проверка условий оказывается сложнее, чем обычные алгоритмы. Однако бывают задачи в которых можно сразу сгенерировать граф, удовлетворяющий этим условиям.
Первое условие можно немного ослабить в плане перескакивающих рёбер, вставив дополнительную вершину.

Добавлено 03.05.20, 16:57
Если вершины перенумерованы послойно, как в этой задаче, можно их обрабатывать последовательно

Cost[1] = 0

Cost[2] = Cost[1] + 7 = 7 # Путь 1-2
Cost[3] = Cost[1] + 5 = 5 # 1-3
Cost[4] = Cost[1] + 6 = 6 # 1-4

Cost[5] = min(Cost[2] + 4, Cost[3] + 6, Cost[4] + 10) = min(11, 11, 16) = 11 # 1-2-5 или 1-3-5
Cost[6] = min(Cost[2] + 8, Cost[3] + 3, Cost[4] + 9) = min(15, 8, 15) = 8 # 1-3-6

Cost[7] = Cost[5] + 6 = 17 # 1-2-5-7 или 1-3-5-7
Cost[8] = min(Cost[5] + 8, Cost[6] + 5) = min(19, 13) = 13 # 1-3-6-8
Cost[9] = Cost[6] + 4 = 12 # 1-3-6-9

Cost[10] = min(Cost[7] + 9, Cost[8] + 7, Cost[9] + 11) = min(26, 20, 23) = 20 # путь 1-3-6-8-10

amk, т е алго Дейкстры использовать нельзя (из-за требований в условии про ДП), так??

Сообщение отредактировано: FasterHarder - 03.05.20, 17:10

FasterHarder, а что вообще такое - "динамическое программирование"? Как именно формулирует этот термин тот, кто задает задачи? Каковы четкие критерии определения "вот тут динамическое программирование, а вот тут - не динамическое (или не программирование)"? Если четких критериев нет, то смело используй Дейкстру с дополнениями, а все возражения посылай в /dev/null.

Цитата amk @ 03.05.20, 16:12

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

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

но вернемся к структурам данных.
на 1-ом этапе нужно получить эти зоны/группы/слои. В этом поможет обход графа В ШИРИНУ (+очередь). "Выпишем" все вершины в графа в одномерный массив по возрастанию/убыванию номеров групп.
затем обрабатываем вершины из каждой группы последовательно + параллельно отслеживаем связи этих вершин из предыдущей группы.

это, если коротко и самую суть.

Добавлено 03.05.20, 17:21

Цитата AVA12 @ 03.05.20, 17:11

а что вообще такое - "динамическое программирование"?

, ну, я думаю, что ты много раз и сам видел всякие определения и рассуждения на эту тему + понимаешь это гораздо лучше меня. В вики целая статья посвящена ДП)
Кто-то говорит, что ДП - один из методов оптимизации.
Мне вот эта статейка понравилась

Добавлено 03.05.20, 17:33

Цитата amk @ 03.05.20, 16:12

Не должно быть рёбер внутри слоя или прыгающих через слой.

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

Алгоритм Форда-Беллмана тоже метод динамического программирования. Инфа 100%, в какой-то книге читала.
Собственно, Беллман и ДП придумал, и этот алгоритм.
Граф нужно представить списками инцидентности типа "пред", т.к. для каждой вершины нужно знать список предыдущих "соседок".

Добавлено 03.05.20, 17:45
Всем привет!
Я - Swetlana, я вернулась
Даже припомнила, почему там можно применять ДП.

ДП основано на чём: на отсутствии у системы последействия.
То есть, мы находимся в текущем состоянии и из него ищем оптимальное продолжение.
А историю, как мы попали в это состояние - мы не помним.
То есть, если кратчайший путь между s и t проходит через вершину v, то он делится на кратчайший путь от s до v и кратчайший путь от v до t.
Это не всегда так.
Если выполнение поворота требует времени, т.е. удлиняет путь, то на перекрёстке нужно помнить, из какой вершины мы попали в текущую, придётся выполнять поворот или нет.

Цитата FasterHarder @ 03.05.20, 17:15

на 1-ом этапе нужно получить эти зоны/группы/слои. В этом поможет обход графа В ШИРИНУ (+очередь).

Для графов общего вида это не работает.

Цитата swf @ 03.05.20, 17:38

Алгоритм Форда-Беллмана

да, кстати, точняк), правда там не должно быть отрицательных циклов.

Цитата swf @ 03.05.20, 17:38

Беллман и ДП придумал

тоже верно, в 50-е годы

https://foxford.ru/wiki/informatika/algoritm-forda-bellmana
Алгоритм тот же (что и везде), но вводят функцию с двумя аргументами.

Сообщение отредактировано: swf - 03.05.20, 18:13

Цитата

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

Это все хвилософия. Про смысл жизни, к примеру, много тонн макулатуры понаписано, а четкого определения и критериев все нет. В википедии то же самое. Читаю "определения" и в упор не понимаю, как можно применить их на практике для разделения "вот тут - да, а вот тут - нет". Что такое, к примеру, "подзадача меньшего размера"? Та же задача, только использующая часть входных данных? Или же другая задача, выход которой подается на вход переформулированной задачи? Или что?

Вот, к примеру, предложенное мной решение состоит из двух этапов: нахождение кратчайших расстояний и построение кратчайшего пути. Второй этап получает на вход данные, полученные на первом - это и есть две "подзадачи меньшего размера" или еще нет? Каждый этап строит решение постепенно, один узел за другим, на каждом шаге мы получаем все увеличивающуюся часть требуемого на этом этапе результата - это и есть "подзадачи меньшего размера"? Чего не хватает этому решению, чтобы можно было гордо налепить бирку "dynamic programming inside"? Или же тут всего хватает? Но оба приема - и поэтапное преобразование входных данных, и постепенное построение результата - используются в программировании повсеместно. Тогда получается, что любой алгоритм - даже, например, решение квадратного уравнения - можно относить к динамическому программированию?

Сообщение отредактировано: AVA12 - 03.05.20, 18:39

Я так понимаю, где ДП:
1. Система без последействия и обратной связи.
2. Решение находят с помощью многошагового процесса принятия решения (строгое определение всех этих слов - в книге Беллмана "Динамическое программирование и современная теория управления", 1969 года издания.).

Цитата

Принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):
Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление таким образом, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.

Как я это понимаю.
1. Чтобы выбрать оптимальное управление из текущего состояния на текущем шаге не нужно помнить историю процесса, как мы попали в текущее состояние.
Или другими словами. Задача раскладывается на подзадачи, которые можно решать независимо и параллельно, затем объединять их.
(В логике это всю жизнь называлось "разложимая система продукций" вообще-то, но не будем приплетать сюда логику.)
То есть можно найти оптимальное решение от начала до некоего фиксированного состояния, затем найти оптимальное решение от фиксированного состояния до конечного, сложить их и получить оптимальное решение при условии, что оно проходит через это фиксированное состояние.
2. Отсутствие обратной связи, вроде, управление на текущем шаге не меняет предыдущие состояния. Но про обратную связь точно не скажу.

Таких задач (без последействия и обратной связи) на самом деле не очень много, все они хорошо изучены и все решаются ДП.
Пример, когда одна и та же задача может решаться ДП или не ДП.
Набор заданной суммы из заданных слагаемых.
ДП за псевдополиномиальное время находит ровно одно решение;
алгоритм с возвратом за экспоненциальное время находит все решения.

на мой дилетантский взгляд ДП там ярко применимо, где:
1. нужно запомнить какое-то решение, чтобы при необходимости извлечь сразу ответ (мемоизация) без повторного решения
2. большую задачу можно разбить НА РЯД НЕБОЛЬШИХ, и что самое важное эти подзадачи должны решаться рекурсивно

Рекурсией можно что угодно написать, даже сортировку "пузырёк"

Я выяснила, к ДП в "узком" смысле относят "табличный" способ решения задачи. Там вообще нет рекурсии.
И по поводу задания. Чего там хотят.
Может, там хотят не оптимизированный алгоритм Ф.-Б., а как здесь первый вариант, с двумерной табличкой
https://foxford.ru/wiki/informatika/algoritm-forda-bellmana

Сообщение отредактировано: swf - 03.05.20, 20:01

Цитата

Я так понимаю, где ДП:

Вот и еще одно определение.

Цитата

Чтобы выбрать оптимальное управление из текущего состояния на текущем шаге не нужно помнить историю процесса, как мы попали в текущее состояние.

Что значит "помнить историю процесса"? Например, при построении кратчайшего пути (после использования алгоритма Дейкстры) на каждом шаге нужны только входные данные для задачи и последний добавленный в список пути узел. Какие еще узлы есть в списке и как они туда попали - для алгоритма несущественно. Можно даже не хранить этот список, а просто отправлять каждый очередной узел куда-нибудь. Значит ли это, что в данном алгоритме мы не помним историю процесса?

Цитата

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

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

Цитата AVA12 @ 03.05.20, 20:23

Вот и еще одно определение.

В вики ДП описано четко и понятно.

Цитата

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

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

1. Да. Во всех задачах о нахождении кратчайшего пути на взвешенных орграфах (Ф.-Б.,Дейкстра, Флойд) предполагается, что система без последействия, т.е. если в оптимальном пути от s до t взять любую промежуточную вершину v, то пути от s до v и от v до t будут также оптимальными. То есть мы предполагаем, что "система" не имеет последействия.
А вот в исходной задаче о штрафах за повороты последействие есть. НАМ НАДО ПОМНИТЬ историю процесса, т.е из какой вершины мы попали в текущую, чтобы знать, будет у нас поворот или нет.
Но если перестроить граф и включить стоимости поворотов в стоимости новых ребер, то в этой конкретной задаче можно избавиться от последействия. Обычно от него избавиться нельзя, конечно.

2. Необходимо, чтобы не было последействия и обратной связи. Иначе задачу нельзя решать ДП.
Сам способ решения ДП - мношаговый процесс принятия решений, см. книгу Беллмана, там он даёт все определения.
В узком смысле (как часто преподы могут формулировать заданье) ДП - табличный способ решения.

3. Штопором в самоизоляции не пользуюсь, чёто все вина попадаются с откручивающимися крышками

Сообщение отредактировано: swf - 03.05.20, 20:47

Цитата JoeUser @ 03.05.20, 20:39

Задача сводится к поиску всех путей от вершина старта до вершины стопа, и выборе наилучшего варианта.

идея понятна!
т е ты хочешь сделать ПОЛНЫЙ ПЕРЕБОР всех возможных траекторий от стартовой до заданной. Полный перебор необходим, т к мы не знаем, что данный маршрут оптимальный, пока не переберем всевозможные...

представим, что городов около 1000 и существует порядка 17 млн траекторий. Львиная доля из них будет иметь одинаковое "начало" и отличаться лишь "хвостиком". Запомнить ранее вычисленные значения "начал" не представляется возможным (мемоизации нет) и придется КАЖДЫЙ раз все пересчитывать с нуля.

Вообще, вроде ведь подоходит алго Беллмана-Форда, даже в вики написано, что для заполнения таблицы будем использовать ДП. Может на этом варианте и остановиться??

Добавлено 03.05.20, 20:52

Цитата swf @ 03.05.20, 20:46

ДП - табличный способ решения.

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

Всех путей между двумя вершинами в полном графе порядка n!
Если n=250, то это больше чем число атомов в видимой нами части вселенной.

Добавлено 03.05.20, 20:57
В стандартном Ф.-Б. алгоритм ДП оптимизирован, вместо таблицы храним одну-единственную текущую строку, так называемый вектор расстояний.
Но может препод хочет как раз неоптимизированный алгоритм с двумерной таблицей - он есть по ссылке, которую я дала (фоксфорд какой-то). Конечно, не проверяла, как это работает.

Сообщение отредактировано: swf - 03.05.20, 20:58

Цитата

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

Угу, предрасчет, кэширование, нахождение дискриминанта квадратного уравнения - это все динамическое программирование.

Цитата

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

То есть, без рекурсии никуда. Если вместо рекурсии сделать итерацию - все, это уже не динамическое программирование? И оговорка "включает в себя" настораживает - что, может и не включать? Или должно включать что-то еще? "Динамическое программирование" обязано иметь оба признака - и "сверху", и "снизу" (кстати, нет ли еще какого-нибудь "динамического программирования сбоку"?)? Или хватит одного варианта? Это вообще необходимые признаки или достаточные?

А в остальном - да, все четко и понятно.

Так, ребята. Я тут кой-чего если не вру, то не договариваю.
Похоже, необходимо, чтобы целевая функция системы была аддитивна, чтобы можно было ДП решать.

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

Область применения динамического программирования
Динамическое программирование применяется для систем, которые характеризуются следующими признаками.
1. Процесс функционирования системы можно представить как последовательность n этапов, на каждом этапе происходит смена состояния системы. В начальный момент система находится в начальном состоянии S0. Затем на первом этапе управляющее воздействие x1 переводит систему из состояния S0 в состояние S1 и т. д. На последнем n – 1 шаге система находится в состоянии Sn-1, управляющее воздействие переводит её в конечное состояние Sn:
S₀ -> S₁ -> … -> S_n-1 -> S_n.
2. Для системы выполняется принцип отсутствия последействия. Суть этого принципа заключается в следующем. Состояние системы на i-м этапе S_i зависит только от состояния системы на предыдущем этапе и управляющего воздействия x_i. И не зависит от состояний системы и управляющих воздействий на более ранних этапах. Свойство отсутствия последействия называют также свойством отсутствия памяти. Это принцип записывается в виде уравнений
Sk = φ(Sk-1, x_k), (1)
которые называются уравнениями состояний.
Например, для задачи поиска длины кратчайшего пути между двумя фиксированными вершинами s и t на нагруженном орграфе рассмотрим две модели, с последействием и без.

Модель без учёта последействия.
Сначала находим все вершины, смежные с t, т.е. вершины v_i, i = 1 … k, которые соединены с t ориентированной дугой (v_i -> t). Решение исходной задачи (найти длину кратчайшего пути от s и t) разбивается на две подзадачи меньшего размера, одна из которых решается тривиально, а другую тоже можно разбить на подзадачи: найти длину кратчайшего путь от s до v_i и найти вес дуги от v_i до t. Затем из решений подзадач конструируется решение исходной задачи: длина условно-оптимального пути от s и t, при условии, что путь проходит через вершину v_i, равна длине кратчайшего пути от s до v_i плюс вес дуги от v_i до t. И, наконец, из всех полученных условно-оптимальных решений выбираем минимальное (через какую вершину vi лучше всего пойти). По такому принципу работает алгоритм Форда-Беллмана.
В этой модели мы исходим из следующего предположения: если кратчайший путь от s до t проходит через вершину v, то его отрезок от s до v будет кратчайшим путем от s до v и отрезок от v до t будет кратчайшим путем от v до t. Это предположение и означает, что у системы нет последействия: неважно, как мы попали в вершину v, нам достаточно знать, что v – наша текущая вершина (текущее состояние системы), из которой мы ищем кратчайший путь от v до t.

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

Модель с учётом последействия.
Существует класс задач о поиске кратчайших путей, для которых принцип оптимальности не выполняется. Это задачи с фиксированными платежами. Подобные задачи возникают в том случае, если за прохождение вершины сети взимается плата. Рассмотрим простейшую задачу из этого класса – задачу о штрафах за повороты. В этой задаче недостаточно помнить текущую вершину, нужно помнить предысторию: как мы в эту вершину попали.

3. Пусть X(x₁, ..., x_n) – управление, переводящее систему из состояния S₀ в состояние S_n. Тогда целевая функция системы (величина прибыли) F = F(S₀, X) зависит от начального состояния системы и управления на каждом шаге.
Целевая функция системы (величина прибыли) является аддитивной, т.е. целевая функция всей системы (оптимальная прибыль) равна сумме локальных ЦФ (локальных прибылей) на каждом шаге:
F = f₁(S₀, x₁)+...+ f_n(S_n-1, x_n)(2)

Окончательно, ДП формулируется так:
определить такое допустимое управление X, переводящее систему из начального состояния S₀ в конечное состояние S_n, при котором суммарная целевая функция принимает наибольшее (наименьшее) значение.
--------------------------------------------------------------------------------------------------

Мне интересно, правильно ли я указала эти 3 признака систем, для которых можно применить ДП.

Сообщение отредактировано: swf - 03.05.20, 21:30

Цитата

Сам способ решения ДП - мношаговый процесс принятия решений, см. книгу Беллмана, там он даёт все определения.

Вот эту? А на какую страницу смотреть, чтобы увидеть определение термина "динамическое программирование" применительно к программированию? Я просмотрел по диагонали оглавление и пролог, но ничего похожего не нашел.

Такой у меня нет.
У меня единственная бумажная книга
Беллман Р., Калаба Р. Динамическое программирование и современная теория управления

Сообщение отредактировано: swf - 03.05.20, 22:29

Почитал википедию и чуток пролога Беллмана, и, кажется, что-то понял. Если коротко и неточно:

1. Динамическое программирование (ДП) - это не про программирование, а про пошаговое управление динамическими системами с целью минимизации/максимизации некоторой функции от параметров системы.
2. Применительно к программированию системой является некий алгоритм, разбитый на шаги, и состояние программы на каждом шаге. Для применения ДП и задача, и алгоритм должны обладать некоторыми определенными свойствами.
3. Целью ДП в программировании является такой выбор действий на каждом шаге алгоритма, чтобы каждое новое состояние содержало новую часть (слагаемые, элементы списка и пр.) решения некоторой общей задачи (либо более точное приближение к решению). Например, в алгоритме Дейкстры на каждом шаге находится предварительная или окончательная оценка расстояния для очередной вершины, а совокупность всех окончательных оценок является решением общей задачи.
4. Каждый следующий шаг должен зависеть только от текущего состояния, точная предыстория никого не интересует.
5. Однако, насколько я понял, зависимости (через состояние) между шагами должны образовывать связный орграф. Если задача разбивается на непересекающиеся подзадачи, которые могут быть решены раздельно-параллельно - это не ДП (так в википедии, и в русской, и в английской).

Все это смутно понятно и имеет смысл. Все прочее - рекурсия, мемоизация - это шелуха и довески.

подытожим)

1. Этот ученый Беллман ввел этот термин в 50-е годы. А давайте-ка подумаем, насколько в эти годы было развито программирование (алгоритма + структуры данных) как таковое? Да оно вообще только ЗАРОЖДАЛОСЬ! Кнут школу еще не закончил)) Дейкстра лишь начал погружение в эту область и пр.мастодонты толком ничего не придумали. Нормальных ЯП не существовало, а копмы, если и были, то выглядели шкафоподобно. Все рассуждения Беллмана о ДП были сделаны исключительно с колокольни КИБЕРНЕТИКИ, чистой голимой кибернетики) То, что понимают сегодня под ДП и то, что понимал Беллман - имеет достаточно слабую связь.

2. Современное ДП характеризуется: рекурсией и рекуррентными соотношениями между элементами динамики, хранение ранее вычисленных значений (мемоизация)

А вообще, ведь ДП - чисто термин! Он объединяет ряд техник программирования (там и восходящее программирование и структурный подход и пр. пр.) и не более того. Можно писать "совершенный код", даже не имея представления о том, что существует какое-то понятия динамического программирования
------------------------------------------
Поставленная задача в 1ом посте ведь имеет некоторые решения в сети. Там нет примеров кода и структур данных, но есть математические модели. И во всех описаниях был показано способ решения, который пытался показать amk в посте №4 (разбивка на зоны).
И на данный момент я вот совсем не уверен, что это не является чуть ли не единственным верным подходом к решению задачи в рамках ДП. Реализовать алгоритм Беллмана-Форда будет попроще...

Цитата AVA12 @ 04.05.20, 01:21

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

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

Ну а термин "программирование" и у линейного программирования означает совсем не программирование.

Сообщение отредактировано: swf - 04.05.20, 09:44

Цитата

2. Современное ДП характеризуется: рекурсией и рекуррентными соотношениями между элементами динамики, хранение ранее вычисленных значений (мемоизация)

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

Обнаружила новую книгу, вернее, 3 тома Тим Рафгарден "Совершенный алгоритм".
Будет, что почитать во время самоизолированного летнего отпуска.
Один том называется "Жадные алгоритмы и динамическое программирование".
Там, в частности, объясняется различие между ДП и подходом "Разделяй и властвуй", автор находит 6 отличий. Основная проблема у ДП со склеиванием решений подзадач, которой нет у "Разделяй и властвуй".
16.4.4. Динамическое программирование против «разделяй и властвуй»
6. Парадигму «разделяй и властвуй» можно рассматривать как частный случай динамического программирования, в котором каждый рекурсивный вызов выбирает фиксированную коллекцию подзадач для рекурсивного решения. Как более сложная парадигма, динамическое программирование применяется к более широкому кругу задач, чем «разделяй и властвуй», но оно также более технически требовательно в применении (по крайней мере, до тех пор пока у вас не будет достаточного практического опыта).
Какую парадигму следует предпочесть, столкнувшись с новой задачей? Если вы видите решение «разделяй и властвуй», непременно используйте его. Если все ваши попытки «разделяй и властвуй» оказываются безуспешными — и в особенности если они оказываются безуспешными, потому что шаг совмещения всегда требует повторного выполнения большого объема вычислений с нуля, — то пришло время попробовать динамическое программирование.

В итоге реализовал через алгоритм Беллмана-Форда:

procedure FB(pn, ps: integer);
var
  i, j: integer;
begin
  for i := 1 to pn do
    d[i] := inf;
  d[ps] := 0;
 
  for i := 1 to (pn - 1) do
  begin
    for j := 1 to (E - 1) do
    begin
      if(d[edges[j].v] + edges[j].w < d[edges[j].u]) then
        d[edges[j].u] := d[edges[j].v] + edges[j].w;
    end;
  end;
end;

автор алгоритма клянется, что там есть метод динамического программирования
ну, не знаю, ну, всякое бывает, наверное, да, что-то из ДП есть, а может и нет, а кто ж его знает, ну да ладно, что ж поделать-то теперь, ну не знаю...

и так сойдет (с)

ЗЫ: результаты программа выдает ПРАВИЛЬНЫЕ

А на Prolog-е такое не проканает?

На Прологе что угодно проканает, даже сортировка "пузырёк".
"Но зачем, сэр?"

swf
Ну как я понял, цель ДП.