Метод динамического программирования в картинках

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

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


Этап 1. Строим граф переходов состояний объекта управления

На входе в алгоритм мы имеем описание мерных характеристик объекта. В терминах описываемого метода: рекуррентное соотношение, описывающее систему. Мне же больше нравится название из теории категорий - "стрелка". 

Определив текущее состояние, где мы находимся сейчас, и состояние в которое мы хотим попасть, мы начинаем применять "стрелку" к одному из них (на иллюстрации к начальному состоянию) Результатом имеем граф как на картинке, где кружочками обозначены состояния в которые мы можем попасть.

Не из каждого состояния можно попасть на "выход". Поэтому следующим шагом удаляем лишние хвосты.


Этап 2. Строим граф переходов состояний объекта управления

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




Этап 3. Ищем "кратчайший путь"

Понятно, что в случае прибыли, искать придётся наибольший путь. Суть от этого не меняется. На этом этапе ищем такой путь. В случае небольших графов, это можно сделать и вручную. Для больших построений может пригодиться дополнительная вычислительная мощность, например graphonline.ru.


Итогом мы будем иметь цепочку переходов или шаговых управлений. То есть концепцию.


И вот эту штуку мы и будем передавать дальше на этап проектного управления.



И на последок, ещё раз хотелось бы обратить внимание, что метод динамического программирования не является единственным способом построения концепции.

Комментарии