Твои ноги гудят от усталости. Ты вспоминаешь, что вся еда осталась в тюках, навьюченных на лошадь, и что ты уже давно не ел. Руки и спина ноют от тяжелой ноши.
Сложная сеть скрещивающихся троп протянулась на многие мили вниз по склону горы. Но как выбрать свою тропу?
Во-первых, повозка слишком тяжела, чтобы ты смог протащить ее по поднимающейся вверх тропе на заметное расстояние. Если же уклон становится слишком пологим, повозка увязает и ее очень трудно сдвинуть и значит, существует минимальная крутизна тропинки, при которой ты с твоей повозкой можешь передвигаться.
Во-вторых, пользоваться крутыми спусками гораздо легче и приятнее. Но если выбирать только их, то часть времени неизбежно придется либо перемещаться по слишком пологим участкам, либо подниматься в гору. Соответственно, ты должен найти баланс между крутыми участками пути и участками более пологими, которых на твоем пути больше. Наконец ты видишь вдалеке свою цель все тропинки сходятся там у реки, которая разливается по равнине. Но вот вопрос: по какой тропе ты можешь попасть туда с наименьшими усилиями?
Твои ноги гудят от усталости. Ты вспоминаешь, что вся еда осталась в тюках, навьюченных на лошадь, и что ты уже давно не ел. Руки и спина ноют от тяжелой ноши.
Сложная сеть скрещивающихся троп протянулась на многие мили вниз по склону горы. Но как выбрать свою тропу?
Так выбери же ту, что подходит именно тебе!
Поэт мог бы сказать, что вода течет с горы вниз из-за того, что ее притягивает море, но физик и обычный смертный скажет, что она течет так, как течет в каждой точке из-за того, что так устроена земная поверхность в данной точке, независимо от того, что лежит впереди.
Бертран Рассел «Азбука относительности»
Проблема спуска с горы с затратой наименьшего усилия это очень распространенный тип задачи о том, как выбрать путь в пространстве, когда какой-то параметр минимизируется. Например, мы часто ищем путь наименьшей длины, то есть хотим попасть к месту назначения самым быстрым из всех возможных способом. Эта задача предполагает, что вы в уме или на бумаге перечислите возможные пути, измерите их длину и найдете кратчайший. Но вскоре вы можете обнаружить, что кратчайший и быстрейший пути это не одно и то же: иногда по более длинной автостраде вы доедете гораздо быстрее, чем по короткой проселочной дороге. Чтобы найти самый быстрый путь, вы должны каждый из возможных путей разбить на сегменты длиной A d и в каждом сегменте оценить скорость v, с которой вы можете преодолеть этот сегмент. Время, за которое вы преодолеваете данный сегмент, равно t = d/v, а суммируя время по всем сегментам, вы получаете общее время, которое затрачивается при движении по этому пути. Сравнивая времена, относящиеся ко всем возможным путям, вы находите самый быстрый.
Задача нахождения легчайшего пути при спуске с горы немного другая. Ваша цель не побыстрее спуститься с горы, а затратить при этом как можно меньше усилий. Сложность состоит в том, что после того как вы спуститесь с определенной высоты, вам придется преодолеть горизонтальный участок (чтобы попасть к выходу реки на равнину). Вы можете выбрать пологие участки, по которым спускаться тяжелее, но которые зато покрывают большую часть пути, а можете выбрать крутые участки, где спускаться хотя и легче, но высота теряется слишком быстро. Мы можем написать выражение для усилия в виде:
(усилие) = (потеря высоты) × (сложность спуска).
Здесь сложность определяется тем, с каким напряжением вам придется спуститься с данной высоты. И мы знаем, что сложность тем больше, чем более плоска на данном участке тропа.
Мы, как и в случае сложения интервалов времени при движении между двумя точками пространства, должны суммировать усилия при спуске от начальной точки до конечной, разделив весь путь на маленькие отрезки. Затем для каждого такого маленького отрезка мы умножим потерю высоты на этом отрезке на сложность его преодоления и в результате найдем усилие, затраченное на спуск на этом сегменте пути. Суммируя все эти небольшие усилия, мы получим полное усилие, затраченное на весь спуск с горы.
Процедура расчета проста: и для вычисления времени, затраченного на путь, и для вычисления усилий, затраченных на спуск, мы должны сначала разделить весь путь на сегменты, затем умножить каждый интервал на некую величину назовем ее, скажем, L, и наконец просуммировать все произведения. Величина L может зависеть от различных особенностей пути, например, от скорости или от того, насколько тяжело приходится работать, спускаясь со склона с заданной крутизной. Нахождение оптимального пути сводится к тому, чтобы просуммировать L по каждому пути, получить для него значение суммы назовем ее S, а затем выбрать путь с минимальным S. И этим способом находится как путь с минимальным временем, так и путь с минимальным затраченным усилием.
Это похоже на решаемую нами проблему, а значит, нужно рассмотреть все возможные пути, ведущие вниз с горы, разбить каждый из них на сегменты, найти крутизну каждого сегмента, определить, насколько сложно будет тащить повозку по склону с данной крутизной (имея в виду, что крутизна не может быть ниже критической величины, так как при меньшей крутизне повозка двигаться не будет), умножить сложность преодоления этого участка на его высоту и просуммировать результаты по всем сегментам. Повторить эту процедуру для всех троп и в конце концов найти ту, для которой суммарное усилие окажется наименьшим.