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

Цитата

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

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

Цитата

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

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

Цитата

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

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

Цитата 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;

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

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

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