Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3831429 Tue, 26 May 2020 03:05:32 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3831429 swf
Ну как я понял, цель ДП. :rolleyes:]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3831424 Mon, 25 May 2020 22:46:49 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3831424 "Но зачем, сэр?"]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3831402 Mon, 25 May 2020 11:19:39 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3831402 :rolleyes:]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830272 Tue, 05 May 2020 11:42:14 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830272
    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;


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

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

ЗЫ: результаты программа выдает ПРАВИЛЬНЫЕ]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830241 Mon, 04 May 2020 18:07:20 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830241 Будет, что почитать во время самоизолированного летнего отпуска.
Один том называется "Жадные алгоритмы и динамическое программирование".
Там, в частности, объясняется различие между ДП и подходом "Разделяй и властвуй", автор находит 6 отличий. Основная проблема у ДП со склеиванием решений подзадач, которой нет у "Разделяй и властвуй".
16.4.4. Динамическое программирование против «разделяй и властвуй»
6. Парадигму «разделяй и властвуй» можно рассматривать как частный случай динамического программирования, в котором каждый рекурсивный вызов выбирает фиксированную коллекцию подзадач для рекурсивного решения. Как более сложная парадигма, динамическое программирование применяется к более широкому кругу задач, чем «разделяй и властвуй», но оно также более технически требовательно в применении (по крайней мере, до тех пор пока у вас не будет достаточного практического опыта).
Какую парадигму следует предпочесть, столкнувшись с новой задачей? Если вы видите решение «разделяй и властвуй», непременно используйте его. Если все ваши попытки «разделяй и властвуй» оказываются безуспешными — и в особенности если они оказываются безуспешными, потому что шаг совмещения всегда требует повторного выполнения большого объема вычислений с нуля, — то пришло время попробовать динамическое программирование.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830222 Mon, 04 May 2020 12:51:35 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830222 Цитата
2. Современное ДП характеризуется: рекурсией и рекуррентными соотношениями между элементами динамики, хранение ранее вычисленных значений (мемоизация)

Что значит "характеризуется"? В перечислении указаны обязательные признаки или всего лишь часто встречающиеся практики?
Мемоизация - это еще одна техника оптимизации, ДП остается ДП и с мемоизацией, и без.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830197 Mon, 04 May 2020 09:42:35 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830197 Цитата AVA12 @
5. Однако, насколько я понял, зависимости (через состояние) между шагами должны образовывать связный орграф. Если задача разбивается на непересекающиеся подзадачи, которые могут быть решены раздельно-параллельно - это не ДП (так в википедии, и в русской, и в английской).

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

Ну а термин "программирование" и у линейного программирования означает совсем не программирование.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830185 Mon, 04 May 2020 07:42:25 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830185
1. Этот ученый Беллман ввел этот термин в 50-е годы. А давайте-ка подумаем, насколько в эти годы было развито программирование (алгоритма + структуры данных) как таковое? Да оно вообще только ЗАРОЖДАЛОСЬ! Кнут школу еще не закончил)) Дейкстра лишь начал погружение в эту область и пр.мастодонты толком ничего не придумали. Нормальных ЯП не существовало, а копмы, если и были, то выглядели шкафоподобно. Все рассуждения Беллмана о ДП были сделаны исключительно с колокольни КИБЕРНЕТИКИ, чистой голимой кибернетики) То, что понимают сегодня под ДП и то, что понимал Беллман - имеет достаточно слабую связь.

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

А вообще, ведь ДП - чисто термин! Он объединяет ряд техник программирования (там и восходящее программирование и структурный подход и пр. пр.) и не более того. Можно писать "совершенный код", даже не имея представления о том, что существует какое-то понятия динамического программирования
------------------------------------------
Поставленная задача в 1ом посте ведь имеет некоторые решения в сети. Там нет примеров кода и структур данных, но есть математические модели. И во всех описаниях был показано способ решения, который пытался показать amk в посте №4 (разбивка на зоны).
И на данный момент я вот совсем не уверен, что это не является чуть ли не единственным верным подходом к решению задачи в рамках ДП. Реализовать алгоритм Беллмана-Форда будет попроще...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830178 Mon, 04 May 2020 01:21:53 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830178
1. Динамическое программирование (ДП) - это не про программирование, а про пошаговое управление динамическими системами с целью минимизации/максимизации некоторой функции от параметров системы.
2. Применительно к программированию системой является некий алгоритм, разбитый на шаги, и состояние программы на каждом шаге. Для применения ДП и задача, и алгоритм должны обладать некоторыми определенными свойствами.
3. Целью ДП в программировании является такой выбор действий на каждом шаге алгоритма, чтобы каждое новое состояние содержало новую часть (слагаемые, элементы списка и пр.) решения некоторой общей задачи (либо более точное приближение к решению). Например, в алгоритме Дейкстры на каждом шаге находится предварительная или окончательная оценка расстояния для очередной вершины, а совокупность всех окончательных оценок является решением общей задачи.
4. Каждый следующий шаг должен зависеть только от текущего состояния, точная предыстория никого не интересует.
5. Однако, насколько я понял, зависимости (через состояние) между шагами должны образовывать связный орграф. Если задача разбивается на непересекающиеся подзадачи, которые могут быть решены раздельно-параллельно - это не ДП (так в википедии, и в русской, и в английской).

Все это смутно понятно и имеет смысл. Все прочее - рекурсия, мемоизация - это шелуха и довески.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830176 Sun, 03 May 2020 22:28:12 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830176 У меня единственная бумажная книга
Беллман Р., Калаба Р. Динамическое программирование и современная теория управления
user posted image]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830175 Sun, 03 May 2020 21:51:10 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830175 Цитата
Сам способ решения ДП - мношаговый процесс принятия решений, см. книгу Беллмана, там он даёт все определения.

Вот эту? А на какую страницу смотреть, чтобы увидеть определение термина "динамическое программирование" применительно к программированию? Я просмотрел по диагонали оглавление и пролог, но ничего похожего не нашел.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830173 Sun, 03 May 2020 21:27:27 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830173 Похоже, необходимо, чтобы целевая функция системы была аддитивна, чтобы можно было ДП решать.

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

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

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

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

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

3. Пусть X(x1, ..., xn) – управление, переводящее систему из состояния S0 в состояние Sn. Тогда целевая функция системы (величина прибыли) F = F(S0, X) зависит от начального состояния системы и управления на каждом шаге.
Целевая функция системы (величина прибыли) является аддитивной, т.е. целевая функция всей системы (оптимальная прибыль) равна сумме локальных ЦФ (локальных прибылей) на каждом шаге:
F = f1(S0, x1)+...+ fn(Sn-1, xn)(2)

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

Мне интересно, правильно ли я указала эти 3 признака систем, для которых можно применить ДП.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830172 Sun, 03 May 2020 21:07:05 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830172 Цитата
Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем.

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

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

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

А в остальном - да, все четко и понятно.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830169 Sun, 03 May 2020 20:52:49 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830169 Если n=250, то это больше чем число атомов в видимой нами части вселенной.

Добавлено
В стандартном Ф.-Б. алгоритм ДП оптимизирован, вместо таблицы храним одну-единственную текущую строку, так называемый вектор расстояний.
Но может препод хочет как раз неоптимизированный алгоритм с двумерной таблицей - он есть по ссылке, которую я дала (фоксфорд какой-то). Конечно, не проверяла, как это работает.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830168 Sun, 03 May 2020 20:49:20 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830168 Цитата JoeUser @
Задача сводится к поиску всех путей от вершина старта до вершины стопа, и выборе наилучшего варианта.

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

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

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

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

вроде, да. я не помню форда-беллмана наизусть, но вроде там заполнение ячеек таблицы происходит на основании уже некоторых, ранее заполненных значениями ячеек...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830167 Sun, 03 May 2020 20:46:39 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830167 А вот в исходной задаче о штрафах за повороты последействие есть. НАМ НАДО ПОМНИТЬ историю процесса, т.е из какой вершины мы попали в текущую, чтобы знать, будет у нас поворот или нет.
Но если перестроить граф и включить стоимости поворотов в стоимости новых ребер, то в этой конкретной задаче можно избавиться от последействия. Обычно от него избавиться нельзя, конечно.

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

3. Штопором в самоизоляции не пользуюсь, чёто все вина попадаются с откручивающимися крышками :D]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830166 Sun, 03 May 2020 20:39:23 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830166 Цитата AVA12 @
Вот и еще одно определение.

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

По условию задачи ТС нужно просто рекурсивно побегать по графу и найти кратчайший по стоимости путь. Задача сводится к поиску всех путей от вершина старта до вершины стопа, и выборе наилучшего варианта. В качестве оптимизации можно запоминать пройденный и найденный минимальный путь, и при следующей итерации, если достижение очередной вершины уже больше запомненного минимального пути - просто обрывать итерацию.]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830165 Sun, 03 May 2020 20:23:07 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830165 Цитата
Я так понимаю, где ДП:

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

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

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

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

Я понимаю, как можно применить это заклинание к физической системе и, например, перевести ее из состояния "плоский штопор" в состояние "горизонтальный полет" через фиксированное промежуточное состояние "пикирование". Но вот каким боком все это относится к задаче о нахождении кратчайшего пути в графе - не понимаю.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830163 Sun, 03 May 2020 20:00:23 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830163
Я выяснила, к ДП в "узком" смысле относят "табличный" способ решения задачи. Там вообще нет рекурсии.
И по поводу задания. Чего там хотят.
Может, там хотят не оптимизированный алгоритм Ф.-Б., а как здесь первый вариант, с двумерной табличкой
https://foxford.ru/wiki/informatika/algoritm-forda-bellmana]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830157 Sun, 03 May 2020 19:46:12 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830157 1. нужно запомнить какое-то решение, чтобы при необходимости извлечь сразу ответ (мемоизация) без повторного решения
2. большую задачу можно разбить НА РЯД НЕБОЛЬШИХ, и что самое важное эти подзадачи должны решаться рекурсивно]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830152 Sun, 03 May 2020 19:10:45 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830152 1. Система без последействия и обратной связи.
2. Решение находят с помощью многошагового процесса принятия решения (строгое определение всех этих слов - в книге Беллмана "Динамическое программирование и современная теория управления", 1969 года издания.).
Цитата
Принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):
Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление таким образом, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.


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

Таких задач (без последействия и обратной связи) на самом деле не очень много, все они хорошо изучены и все решаются ДП.
Пример, когда одна и та же задача может решаться ДП или не ДП.
Набор заданной суммы из заданных слагаемых.
ДП за псевдополиномиальное время находит ровно одно решение;
алгоритм с возвратом за экспоненциальное время находит все решения.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830147 Sun, 03 May 2020 18:16:04 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830147 Цитата
я думаю, что ты много раз и сам видел всякие определения и рассуждения на эту тему + понимаешь это гораздо лучше меня. В вики целая статья посвящена ДП

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

Вот, к примеру, предложенное мной решение состоит из двух этапов: нахождение кратчайших расстояний и построение кратчайшего пути. Второй этап получает на вход данные, полученные на первом - это и есть две "подзадачи меньшего размера" или еще нет? Каждый этап строит решение постепенно, один узел за другим, на каждом шаге мы получаем все увеличивающуюся часть требуемого на этом этапе результата - это и есть "подзадачи меньшего размера"? Чего не хватает этому решению, чтобы можно было гордо налепить бирку "dynamic programming inside"? Или же тут всего хватает? Но оба приема - и поэтапное преобразование входных данных, и постепенное построение результата - используются в программировании повсеместно. Тогда получается, что любой алгоритм - даже, например, решение квадратного уравнения - можно относить к динамическому программированию?]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830145 Sun, 03 May 2020 18:11:25 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830145 https://foxford.ru/wiki/informatika/algoritm-forda-bellmana
Алгоритм тот же (что и везде), но вводят функцию с двумя аргументами.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830143 Sun, 03 May 2020 17:50:01 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830143 Цитата swf @
Алгоритм Форда-Беллмана

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

Цитата swf @
Беллман и ДП придумал

тоже верно, в 50-е годы]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830141 Sun, 03 May 2020 17:47:01 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830141 Цитата FasterHarder @
на 1-ом этапе нужно получить эти зоны/группы/слои. В этом поможет обход графа В ШИРИНУ (+очередь).
Для графов общего вида это не работает.]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830138 Sun, 03 May 2020 17:38:01 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830138 Собственно, Беллман и ДП придумал, и этот алгоритм.
Граф нужно представить списками инцидентности типа "пред", т.к. для каждой вершины нужно знать список предыдущих "соседок".

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

ДП основано на чём: на отсутствии у системы последействия.
То есть, мы находимся в текущем состоянии и из него ищем оптимальное продолжение.
А историю, как мы попали в это состояние - мы не помним.
То есть, если кратчайший путь между s и t проходит через вершину v, то он делится на кратчайший путь от s до v и кратчайший путь от v до t.
Это не всегда так.
Если выполнение поворота требует времени, т.е. удлиняет путь, то на перекрёстке нужно помнить, из какой вершины мы попали в текущую, придётся выполнять поворот или нет.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830134 Sun, 03 May 2020 17:15:53 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830134 Цитата amk @
сли вершины перенумерованы послойно, как в этой задаче, можно их обрабатывать последовательно

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

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

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

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

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

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

я понял о чем ты говоришь.
кстати, далеко не факт, что такой ситуации не может возникнуть...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830133 Sun, 03 May 2020 17:11:10 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830133 FasterHarder, а что вообще такое - "динамическое программирование"? Как именно формулирует этот термин тот, кто задает задачи? Каковы четкие критерии определения "вот тут динамическое программирование, а вот тут - не динамическое (или не программирование)"? Если четких критериев нет, то смело используй Дейкстру с дополнениями, а все возражения посылай в /dev/null.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830132 Sun, 03 May 2020 17:10:18 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830132 amk, т е алго Дейкстры использовать нельзя (из-за требований в условии про ДП), так??]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830125 Sun, 03 May 2020 16:12:12 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830125
А каковы принципы динамического программирования?

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

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

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

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 Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830117 Sun, 03 May 2020 15:47:05 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830117 AVA12, эх, я в первом посте хотел написать, что можно заюзать алгортим Дейкстры, т к он позволяет найти кратчайший путь в графе от заданной вершины до всех остальных, но мне казалось, что здесь его применять нельзя, т к он не использует принципы дин.прог.

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

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

P.S. на самом деле я не оч.глубоко понимацию концепт дин.прог., т к там стараются делать упор на рекурсию, мемоизацию, а в дейкстре сплошные циклы и одномерные массивы....]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830114 Sun, 03 May 2020 15:34:31 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830114
Поскольку веса ребер неотрицательные, можно использовать алгоритм Дейкстры. Тогда для каждого Vi получим d(i) - стоимость минимального пути V1 -> Vi. Затем нужно построить список узлов, входящих в этот путь.

Строим путь от конца к началу. Заведем список, состоящий из одной вершины (конечной). Затем в цикле:
- смотрим на первую вершину в списке (Vk), ищем все вершины Vi, для которых есть ребро Eik;
- для каждой Vi вычисляем стоимость d(i) + w(i, k), если эта сумма равна d(k), значит мы пришли в Vk именно из этой вершины Vi, заносим ее в начало списка (может получиться, что это условие выполняется для нескольких вершин Vi, тогда неважно, какую из них включать в путь - стоимость результата будет одна и та же);
- продолжаем, пока в списке не окажется V1 - тогда список и будет искомым путем.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830109 Sun, 03 May 2020 14:37:51 +0000 выбор оптимального маршрута перевозки грузов https://forum.sources.ru/index.php?showtopic=418496&view=findpost&p=3830109 Есть сеть дорог, соединяющих города. Известны стоимости перевозки груза между городами. Используя метод динамического программирования, найти самый экономный маршрут доставки груза из города №1 в город №10: вывести все города, входящие в маршрут + общую стоимость перевозки. На рис.показана сеть городов и стоимость перевозки грузов.

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

Пусть входные данные задаются в виде весовой матрицы, т е матрицы размером 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.
Также хочется понять, нужна ли в коде какая-то ядровая функция, которая, на вход принимает номер обрабатываемой вершины, а на выходе, например, выдает минимум затрат для этой вершины или вообще все делается в циклах на стартовой весовой матрице.

подскажите как быть-то, буду признателен]]> FasterHarder Алгоритмы