В технике, экономике и некоторых других направлениях иногда приходится решать задачи на поиск оптимального пути или состояния.
По сути это цель любой автоматизации - минимизировать затраты или получить наилучший результат.
Это понятие ввёл в 40-ых годах прошлого века Ричард Беллман. Идея достаточно простая - для того чтобы получить конечный результат, необходимо предварительно решить несколько вспомогательных задач. Решить каждую из которых можно решив их предварительные задачи.
Саму постановку таких задач оптимизации приписывают экономистам, но в технике она применяется тоже достаточно часто.
В некоторых источниках указывается, что основную задачу нужно решать разбив её на несколько более простых. Такое выражение не совсем верно, так как любая сложная задача является составной и всегда будет разбиваться на более простые.
Я бы сказал так, чтобы получить конечный результат в динамическом программировании для решения конечной задачи необходимо решить предшествующую ей задачу, А чтобы решить ту задачу, необходимо решить уже предшествующую ей задачу.
Получается у нас в решении задачи образуется последовательная цепочка задач, которую нужно решать в определенном порядке.
Самый простой пример для этого подходит ряд Фиббоначи. Мы знаем исходные данные, а дальше используем алгоритм получения 3-го элемента и так далее. Если я вас попрошу рассчитать 120-ый элемент ряда, то вам придется для этого найти 118 и 119. Чтобы найти 119, мне нужно знать 117 и 118 и так далее, пока не придём к первым элементам.
Так, например, я хочу посмотреть на какой высоте у меня будет флюгер на коньке дома. Получается мне сперва нужно будет понять где у меня будет крыша. А чтобы понять про крышу, нужно рассчитать положение стен и перекрытий. В итоге мы придем к фундаменту и отметке нулевого уровня.
На самом деле всё просто, только сложность состоит в том, что нужно правильно составить эту последовательность и выявить закономерность, которая и будет использована для расчетов.
Один из популярных примеров: задача про черепашку:
Подобного рода задачи используются в олимпиадах и даже как18 задача для ЕГЭ по информатике. Если вы планируете развиваться в направлении информатики, то эту тему необходимо освоить и понимать.
Подобных задач, на самом деле, достаточно много и они сложны до того момента пока вы не выявите последовательность её решения. В том же программировании есть множество куда более сложных алгоритмических задач.
В технике существуют собственные алгоритмы оптимизации, но и подобные используются тоже.
Про черепашку я решать сегодня не буду. выложу видео чуть позднее или можете найти решение в интернете.
Рассмотрим классический пример задачи с кузнечиком.
У нас есть кузнечик, который сидит на первой кочке и может прыгать на следующие кочки. Но прыгает он либо на следующую +1, либо на третью +3 от себя кочку. То есть кузнечик с первой может переместиться только на 2 или 4 кочку. Теперь вопрос, сколькими различными способами кузнечик может оказаться на 6 кочке, 10 или 120.
Первый раз такая задача ввела меня в легкое раздумье, но после намека на то как надо решать, сразу стало понятно.
Предположим мне надо попасть на 25 кочку (N). Попасть я туда могу с 24 (N-1)или 22(N-3), то есть это два варианта, а точнее сумма обоих вариантов. После того как идея понятна, заполним варианты для последующих кочек.
Далее начнем разбираться с кочками и вариантами попадания. Часто сложности только с первой ячейкой - кочкой. В данном случай у нас есть 1 способ оказаться на ней, поэтому мы ставим в квадрат число 1.
Переходим ко второй кочке, туда я могу попасть только с первой кочки, значит там тоже 1.
Третья кочка аналогично второй кочке. Туда кузнечик может попасть только их предыдущей - 2-ой.
А далее начинается ключевой момент, на 4-ую кочку я могу попасть только из первой или третьей. Получается - это сумма вариантов кочек под номерами 1 и 3.
На пятую кочку попасть можно со второй или четвёртой кочки. Получим 3.
Далее можете попробовать заполнить самостоятельно несколько чисел.
Как вы поняли, каждый элемент этой цепочки можно рассчитать по достаточно простому и понятному алгоритму. Уверен, что у вас получится заполнить квадраты до 16 номера, а далее просто написать алгоритм.
Вообще подобных алгоритмов достаточно много. сейчас готовлю ролик по обходу черепашкой поля.
У меня всё, благодарю за внимание.