Проблема для самостоятельного исследования

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

В заключение

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

о минимальном количестве заправок

Условие задачи. Автомобиль движется из пункта Л в пункт В, начав движение с полным баком. Расход бензина на один километр пути известен. Между пунктами Ли В находится некоторое количество заправок с неограниченным запасом бензина на каждой. Определить, на каких колонках необходимо заправляться, чтобы количество заправок было минимальным.

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

Итак, все же от нас требуется построить свое поведение на дороге таким образом, чтобы именно количество заправок было минимальным. Задача в подобной постановке вполне допускает переборное решение. Достаточно построить все возможные сочетания из заправок, для каждого сочетания выяснить, позволит ли такая расстановка заправок автомобилю доехать до пункта В, и затем из всех допустимых сочетаний выбрать содержащее наименьшее количество заправочных станций. Такое решение выглядит вполне естественным.

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

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

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

Задача, не имеющая решения

Рис. 6.1. Задача, не имеющая решения

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

Задача, имеющая тривиальное решение

Рис. 6.2. Задача, имеющая тривиальное решение

Третий вариант появляется из более внимательного рассмотрения второго. Трудно предположить, что есть только два варианта: ни одного решения и одно тривиальное. Разумно ожидать, что какие-то из заправок можно выбросить из рассмотрения. Но если отрезки только пересекаются, то удаление одного из них делает весь путь невозможным. Следовательно, необходимо придумать ситуацию, в которой удаление отрезка не разорвет путь. Идея опять-таки лежит на поверхности. Это возможно в том случае, если некоторый отрезок полностью перекрывается своими соседями.

Ситуация, позволяющая выбросить одну станцию

Рис. 6.3. Ситуация, позволяющая выбросить одну станцию

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

Как получить решение, ясно. Но это еще, к сожалению, не все. Мы нашли способ выявления лишних заправок, но, может быть, этот способ не дает однозначного результата?!

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >