III. Метод отрабатывания назад.

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

Пример: Задача о джипе.

Путешественник пересекает на джипе пустыню шириной в 1000 км, расходуя по 1 л на каждый километр пути. Однако бак джипа рассчитан только на 500 л. Пу­тешественник может делать запасы бензина, завозя его в пусты­ню на некоторое расстояние, и возвращаясь назад на дозаправку. Необходимо пересечь пустыню с минимальными затратами топ­лива.

Решение. На самом деле, не сразу понятно, что задача во­обще имеет решение. Выработаем определенную стратегию дей­ствий и посмотрим, к чему она приведет. Так как нельзя пересечь пустыню за один раз, необходимо заезжать на какое-то расстояние вглубь, оставлять там некоторое количество топлива так, чтобы в баке еще оставалось достаточно бензина для возвращения. Кур­сируя туда-назад и завозя все больше топлива в глубь пустыни, можно двигаться дальше, в следующий раз возвращаясь уже не к началу пути, а к предыдущему хранилищу. Таким образом, наш путь в 1000 км разбивается на дистанции x₁, x₂, x_k, в конце которых расположены временные хранилища.

Теперь предположим, что пустыня пересечена (метод отраба­тывания назад). Чтобы доехать до ее конца, полностью опустошив бак (а это необходимо по требованию минимального расхода топ­лива, т.е. после пересечения пустыни не должно остаться излиш­ков бензина), последнее хранилище должно быть организовано за 500 км до конца пустыни и содержать 500 л топлива. При этом требование минимального расхода топлива означает, что перед пе­ресечением последнего отрезка пустыни бак джипа снова должен быть пуст.

Последовательные шаги в решении задачи о джипе изображе­ны на рис. 2.3. Итак, известно место и объем последнего хранили­ща — 500 л (один полный бак) за 500 км до окончания пустыни. На каком расстоянии от этого хранилища должно быть преды­дущее, и сколько оно должно содержать топлива, чтобы оттуда можно было перевезти один полный бак до места последнего хра­нилища? Обозначим это расстояние через x₁ (рис. 2.3, а). Итак, сформулировали частную цель.

Попробуем решить поставленную частную цель. Предположим, что за 500 + x₁ км до конца пустыни (в точке предпоследнего хра­нилища) осталось неограниченное количество топлива и доезжаем до этой точки с пустыми баками. Данная ситуация соответству­ет нахождению в точке А (рис. 2.3, б). Заправляем полный бак (это обозначено на рис. 2.3, б как +1), доезжаем до точки В (ме­ста последнего хранилища), оставляем там какое-то количество топлива так, чтобы осталось только на дорогу назад. При возвра­щении (точка С) бак снова пуст, и он снова заправляется целиком, после чего едем до последнего хранилища (точка D), забираем то, что оставили там на прошлом шаге, и в сумме должны получить ровно 500 л, чтобы пересечь остаток пустыни.

Таким образом, три раза проезжаем расстояние х\, затрачи­ваем 500 л, чтобы добраться от точки А до точки С, и еще 500, чтобы от точки С с учетом дозаправки пересечь пустыню. Прой­денное расстояние равно Зх\ + 500 и на это потрачено два полных бака, т.е. 1000 л. Отсюда

3 x₁ + 500 = 1000

и имеем

х₁ = 500/3 или треть бака.

Рис. 7

a – постановка частной цели

б – решение частной цели: вычисление х1

в – подъем вверх с вычислением х2

г - подъем вверх с вычислением хn

На рис. 2.3, б отмечен расход топлива: треть бака на дорогу длиной x₁, треть оставить в точке В, на оставшейся трети вернуться назад. Заправить полный бак, после проезда еще x₁ километров бак полон на 2/3, доливаем еще одну треть, остав­ленную нами ранее, и с полным баком пересекаем оставшиеся 500 км.

Итак, решили одну частную цель, но теперь перед нами стоит другая — нужно завезти два полных бака на расстояние 500 + x₁ = 500 + 500/3 от конца пустыни. Для решения этой частной цели можно использовать решение предыдущей. Схема действий показана на рис. 2.3, в. В этом случае нужно сделать уже не 3, а 5 поездок, расходуя 1/5 бака на каждую поездку и оставляя в хранилище 3/5 бака топлива. После 5 поездок в точке 500 + x₁ (от конца пустыни) имеем два полных бака, а в качестве следующей частной цели в точку 500 + x₁ + х₂ необходимо завезти 3 бака горючего, где х₂ = 500/5.

Дальнейшая схема действий изображена на рис. 2.3, г. Для то­го чтобы завезти n баков на расстояние х_n, нужно n+1 бак и 2n+1 поездка. Один бак тратится на переезды, n баков перевозятся, и тогда

x_n = 500/(2n+1),

или 1/(2n + 1)-я часть бака расходуется на одну перевозку. В хранилище оставляется часть топлива, равная 1 - 2/(2n + 1) = (2n - l)/(2n + 1). После 2n +1 поездки бак полон на 2n/(2n + 1), и в хранилище перевезено n(2n - l)/(2n + 1) топлива, т.е. всего перевезли

баков, что и требовалось.

Рис. 8

Частичные суммы ряда 500/(2n+1)

Для решения задачи теперь нужно найти число k хранилищ, которые необходимо организовать. Мы научились проходить рас­стояние 500 + x₁ + x₂ + x₃ +… — Чтобы пересечь всю пустыню нужно, чтобы это пройденное расстояние (или израсходованное топливо, что одно и то же) превышало 1000 км, т.е.

Данный ряд является расходящимся, а значит задача всегда имеет решение, так как ряд не имеет предела сверху. Частичные суммы этого ряда приведены на рис. 2.4. Как видно из рисунка, для того чтобы проехать 1000 км, нужно организовать k = 15 хранилищ.

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

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

Дата добавления: 2015-11-30