Геометрическая задача на компьютере

С помощью компьютера можно решить множество проблем — от
прокладки курса космического корабля до раскроя тканей. Все
эти проблемы можно разбить на определенные классы — по исполь-
зуемым идеям и методам их решения.
Пусть есть совершенно разные на первый взгляд задачи:
размещение телефонных станций в городе, определение минималь-
ного списка различных электродвигателей, которые будут покры-
вать весь спектр потребностей, разбивка большой электронной
схемы на печатные платы… В формальной постановке (если отб-
росить несущественную для решения информацию из условия) они
очень похожи. Задачи такого типа получили название задач стан-
дартизации. Именно решение такого сорта проблем имеет колос-
сальный экономический эффект в самых разных областях.
Общая формулировка таких задач примерно следующая:
Имеется какое-либо множество, причем известен способ, при
помощи которого можно вычислить, насколько в том или ином
смысле далеки два объекта этого множества друг от друга. Надо
найти один или несколько объектов, к которым близки все ос-
тальные.
На первый взгляд решение — дело нехитрое: перебрал все
варианты, выбрал оптимальный, — и дело в шляпе. Но перебор,
как мы увидим в дальнейшем — не самый эффективный способ реше-
ния.
Рассмотрим одну из задач стандартизации:
Пусть через административный район проходит по прямой же-
лезная дорога. На ней надо построить станцию так, чтобы расс-
тояние от нее до самой дальней деревни было бы минимальным.
Эту задачу можно геометрически формализовать следующим
образом:
На плоскости расположены N точек,заданные своими коорди-
натами. Найти на оси абсцисс точку, наибольшее из расстояний
от которой до выбранных точек было бы минимальным.
Переформулируем условие: На плоскости своими координатами
задаются N точек P_i(x_i,y_i). Построить окружность минималь-
ного радиуса с центром на оси абсцисс так, чтобы она содержала
внутри себя и на своей границе все эти точки.
Везде в дальнейшем будем обозначать через C(P,Z) окруж-
ность с центром в точке (P,O) и проходящую через точку
Z=(Zx,Zy).
Очевидно, что на искомой окружности лежит по меньшей мере
одна точка. Действительно, в противном случае мы можем, не ме-
няя центра окружности, уменьшить ее радиус, а это противоречит
предположению о том, что нами была построена окружность мини-
мального радиуса.
Докажем следующее простое утверждение: Если на искомой
окружности лежит единственная точка, то центр окружности есть
проекция этой точки на ось абсцисс.
Предположим противное — на минимальной окружности лежит
единственная точка Z(Zx,Zy), а центр ее не совпадает с (Zx,0).
Если мы начнем понемножку двигать центр окружности, проходящей
через точку Z, в направлении (Zx,0), то, так как все точки,
кроме Z, лежат внутри окружности, до какого-то момента они и
будут оставаться внутри нее. Таким образом мы можем хоть
чуть-чуть, но сдвинуть центр, уменьшив при этом радиус окруж-
ности, содержащей все точки. Получаем противоречие с предполо-
жением о минимальности радиуса.
Следствие. Если на искомой окружности лежит только одна
точка, то это точка с максимальной по модулю ординатой.
Отметим далее, что окружность с центром на оси абсцисс
единственным образом определяется двумя лежащими на ней точка-
ми (центр этой окружности — это точка пересечения оси абсцисс
и срединного перпендикуляра к отрезку, соединяющего эти две
точки).
Таким образом мы получаем следующий

Алгоритм 1:
Шаг 1. Ищем точку (x_i,y_i) с максимальной по модулю ор-
динатой y_i (если таких точек несколько, и у них разные
абсциссы, то перейти на Шаг 2), и для окружности
C(x_i,(x_i,y_i)) проверяем, содержит ли она все N точек. Если
да, то задача решена, если нет, то
Шаг 2. Среди окружностей, определяемых всевозможными па-
рами точек (P_i, P_j), находим те, которые содержат все точки,
а затем выбираем из них окружность минимального радиуса.
Пар точек, которые могут определять окружности, всего
N(N-1)/2, т.е. порядка N^2, следовательно, и возможных окруж-
ностей тоже порядка N^2. Для проверки принадлежности N точек
каждой окружности требуется порядка N операций. Получаем, что
сложность этого алгоритма порядка N^3. (Когда мы говорим о
сложности алгоритма, то мы рассматриваем только зависимость
роста числа требуемых операций от числа N, игнорируя все
константные множители и медленно растущие слагаемые).
Рассмотрим другой способ решения этой задачи, основанный
на более глубоком ее анализе.

Алгоритм 2.
Проверка по Шагу 1 ранее изложенного алгоритма остается
без изменения. Пусть искомая окружность не найдена.
Для обоснования Шага 2 докажем следующее утверждение:
Пусть окружность с центром (P_ij,0) определяется точками
P_i(x_i,y_i) и P_j(x_j,y_j). Она только тогда может быть со-
держащей все точки окружностью C минимального радиуса, когда
(P_ij,0) лежит на ортогональной проекции отрезка
[(x_i,y_i),(x_j,y_j)] на ось абсцисс, т.е. должны выполняться
неравенства x_i<=P_ij<=x_j. Окружность C с центром (P_ij,0) должна проходить не менее чем через 2 точки заданного множества из N точек, и при этом из этих точек всегда можно выбрать две такие (обозначим их P_i(x_i,y_i) и P_j(x_j,y_j)), что x_i=C(0).
i-ый итеративный (повторяющийся) шаг алгоритма, i=0, 1, 2,
3, … :
Если B(i)-A(i)<=epsilon, то центр окружности лежит на от- резке [A(i),B(i)] и желаемая точность достигнута. Стоп. Иначе Вычисляем C(i)=(A(i)+B(i))/2. Находим Dl(C(i)) и Dr(C(i)). Если Dl(C(i))9).

И3. В программистском фольклоре есть предание, что при приеме
в одну из ведущих компьютерных фирм претенденту предлагалась решить
следующую задачу:
Дана последовательность двузначных чисел
24, 81, 63, 26, 41, …
Продолжить ее. Найти правило формирования последующих членов.

Продумайте, какие способы формирования последовательнос-
тей Вы можете предложить. Не настораживает ли Вас то, что это
последовательность именно двузначных чисел?
Эту последовательность можно переписать и так:
2, 4, 8, 16, 32, 64, 128, …
Очередной член последовательности — 28.

И4. Во время поездки на поезде девочка заменила в назва-
нии поезда каждую букву ее номером в русском алфавите и полу-
чила запись из единиц и двоек «211221-21221″. Определить отку-
да и куда идет поезд.

«Баку-Уфа». Сформулируйте, как Вы решали задачу. Метод,
использованный Вами при решении ее, носит название «Перебор с
возвратом» и является одним из стандартных методов в програм-
мировании.

Кстати! Наверное Вы заметили в статье «Единственно верное
решение?» («Фокус» N 2) две авторские опечатки: в методе 1
(сортировка пузырьком) должно быть, конечно же, for j:=i+1 to
N do, и else Count:=1, а не 0, как было в статье.

И.А.Волков, В.Л.Завадский, В.М.Котов, Т.Г.Котова

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>