Есть идея! - [55]
В идеализированной постановке остров вырождается в точку, доски заменяются отрезками прямых, а для «перекрытия» достаточно касания. Представим себе, что мы располагаем неограниченным запасом одинаковых «досок». Предельный случай показан на рис. 12. Если озеро имеет форму квадрата со стороной, равной 2 единицам длины, то каждая доска (даже если их у нас бесконечно много) не может быть короче √2/2. Доказать это можно с помощью теоремы Пифагора.
Попытайтесь решить ту же задачу в идеализированной постановке для «озер», имеющих какую-нибудь другую форму, например круглых или многоугольных.
Ленивый донжуан
Джек считал себя величайшим в мире сердцеедом. Он решил снять квартиру в Вашингтоне.
В этом городе у него жили три приятельницы, и он решил поселиться как можно ближе ко всем трем.
На плане города Джек отметил те места, где живут его приятельницы.
Джек. Я бы хотел поселиться в таком месте, откуда было бы удобно добираться до всех моих приятельниц, то есть чтобы сумма расстояний от моего дома до тех мест, где живут они, была бы минимальной.
Джек прикидывал так и этак, но все было безуспешно: найти нужную точку никак не удавалось. Вдруг ему пришло в голову неожиданное и простое решение.
Джек. Есть идея! Теперь я знаю, как легко и просто выбрать, где мне поселиться.
Джек мысленно опрашивал своих приятельниц, как бы они отнеслись к тому или иному его «переселению» и те «голосовали» либо за, либо против. Для начала Джек выбрал на карте точку в достаточно разумном месте и «переселился» на 1 квартал к востоку от нее.
Джек. Анита и Банни проголосовали бы за такое переселение, так как я перебрался бы поближе к ним, а Вика проголосовала бы против. Но в расстоянии я выиграл бы больше, чем проиграл, поэтому я подчинюсь мнению, за которое подано большинство голосов.
Всякий раз, когда большинство голосов было за очередное переселение, Джек оставался на новом Месте, а если большинство голосов было против, возвращался на старое. Наконец, он достиг точки, из которой нельзя было переместиться ни в одну сторону, чтобы девушки не проголосовали против. Там он и решил поселиться.
К его радости, квартирная плата в выбранном месте была ему по карману. Но через неделю Банни переехала на новую квартиру в 7 кварталах от своего прежнего дома.
Джек. Жаль, но придется переезжать на новую квартиру.
Но когда Джек достал план города, то, к своему удивлению, обнаружил, что может оставаться на месте.
Как это может быть?
Если Банни переедет на 7 кварталов к востоку от того места, где жила раньше, то ее переезд никак не скажется на выборе резиденции Джека. Более того, Банни могла бы переехать сколь угодно далеко на восток, и место, выбранное для своей квартиры Джеком, по-прежнему оставалось бы оптимальным.
Эффективность алгоритма с голосованием вы сможете лучше оценить, применив к более обширной территории с прямоугольной планировкой, на которой отмечено более трех точек. Вы обнаружите, что алгоритм Джека позволяет быстро находить положение точки x, сумма расстояний от которой до всех отмеченных точек минимально, если число отмеченных точек нечетно. Почему алгоритм перестает работать при четном числе точек? Причина довольно ясна: при четном числе отмеченных точек не исключен «ничейный» исход голосования, а как только голоса разбиваются поровну, алгоритм не срабатывает.
Попробуйте самостоятельно ответить на следующие вопросы:
1. Не могли бы вы предложить эффективный алгоритм, действующий при четном числе отмеченных точек?
2. При каких условиях перемещение одной или нескольких отмеченных точек не сказывается на положении точки x?
3. Изменится ли алгоритм с голосованием, если мы вздумаем учесть ширину улиц?
4. Изменится ли алгоритм, если точка x и отмеченные точки могут не располагаться на перекрестках?
5. Применим ли алгоритм с голосованием в том случае, если сеть улиц образована прямыми, идущими в самых разных, а не только в двух взаимно перпендикулярных направлениях?
6. Останется ли алгоритм в силе, если улицы будут кривыми или зигзагообразными?
Хотя алгоритм с голосованием применим к любым сетям, на «чистой» плоскости без выделенной сети он сразу утрачивает силу, и это понятно: по чистой плоскости мы можем перемещаться в любом направлении, не придерживаясь заданных маршрутов. Общая задача ставится так. На плоскости заданы n точек. Требуется найти такую точку x, чтобы сумма кратчайших расстояний от нее до заданных точек была минимальной. Рассмотрим, например, три города A, B и C. Где следовало бы построить аэропорт, чтобы суммарная протяженность воздушных маршрутов из него в эти города была минимальной? Ясно, что если бы речь шла о длине автомобильных маршрутов, связывающих некоторую точку на карте с городами A, B и C, то ответ был бы другой. Иначе говоря, идеальное место для аэропорта может не совпадать с идеальным местом для автобусной станции.
Ответ, основанный на довольно сложных геометрических соображениях, гласит: идеальным местом для строительства аэропорта была бы такая точка на карте, в которой лучи, проведенные к трем городам, образовывали бы между собой углы в 120°. Если бы число городов возросло до четырех, причем города располагались в вершинах выпуклого четырехугольника, то аэропорт выгоднее всего было бы построить в точке пересечения диагоналей. Доказать это утверждение совсем не трудно. Общая задача (найти точку
