Джек считал себя величайшим в мире сердцеедом. Он решил снять квартиру в Вашингтоне.

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

На плане города Джек отметил те места, где живут его приятельницы.

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

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

Джек. Есть идея! Теперь я знаю, как легко и просто выбрать, где мне поселиться.

Джек мысленно опрашивал своих приятельниц, как бы они отнеслись к тому или иному его «переселению» и те «голосовали» либо за, либо против. Для начала Джек выбрал на карте точку в достаточно разумном месте и «переселился» на 1 квартал к востоку от нее.

Джек. Анита и Банни проголосовали бы за такое переселение, так как я перебрался бы поближе к ним, а Вика проголосовала бы против. Но в расстоянии я выиграл бы больше, чем проиграл, поэтому я подчинюсь мнению, за которое подано большинство голосов.

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

К его радости, квартирная плата в выбранном месте была ему по карману. Но через неделю Банни переехала на новую квартиру в 7 кварталах от своего прежнего дома.

Джек. Жаль, но придется переезжать на новую квартиру.

Но когда Джек достал план города, то, к своему удивлению, обнаружил, что может оставаться на месте.

Как это может быть?

Алгоритм с голосованием

Если Банни переедет на 7 кварталов к востоку от того места, где жила раньше, то ее переезд никак не скажется на выборе резиденции Джека. Более того, Банни могла бы переехать сколь угодно далеко на восток, и место, выбранное для своей квартиры Джеком, по-прежнему оставалось бы оптимальным.

Эффективность алгоритма с голосованием вы сможете лучше оценить, применив к более обширной территории с прямоугольной планировкой, на которой отмечено более трех точек. Вы обнаружите, что алгоритм Джека позволяет быстро находить положение точки x, сумма расстояний от которой до всех отмеченных точек минимально, если число отмеченных точек нечетно. Почему алгоритм перестает работать при четном числе точек? Причина довольно ясна: при четном числе отмеченных точек не исключен «ничейный» исход голосования, а как только голоса разбиваются поровну, алгоритм не срабатывает.

Попробуйте самостоятельно ответить на следующие вопросы:

1. Не могли бы вы предложить эффективный алгоритм, действующий при четном числе отмеченных точек?

2. При каких условиях перемещение одной или нескольких отмеченных точек не сказывается на положении точки x?

3. Изменится ли алгоритм с голосованием, если мы вздумаем учесть ширину улиц?

4. Изменится ли алгоритм, если точка x и отмеченные точки могут не располагаться на перекрестках?

5. Применим ли алгоритм с голосованием в том случае, если сеть улиц образована прямыми, идущими в самых разных, а не только в двух взаимно перпендикулярных направлениях?

6. Останется ли алгоритм в силе, если улицы будут кривыми или зигзагообразными?

Хотя алгоритм с голосованием применим к любым сетям, на «чистой» плоскости без выделенной сети он сразу утрачивает силу, и это понятно: по чистой плоскости мы можем перемещаться в любом направлении, не придерживаясь заданных маршрутов. Общая задача ставится так. На плоскости заданы n точек. Требуется найти такую точку x, чтобы сумма кратчайших расстояний от нее до заданных точек была минимальной. Рассмотрим, например, три города A, B и C. Где следовало бы построить аэропорт, чтобы суммарная протяженность воздушных маршрутов из него в эти города была минимальной? Ясно, что если бы речь шла о длине автомобильных маршрутов, связывающих некоторую точку на карте с городами A, B и C, то ответ был бы другой. Иначе говоря, идеальное место для аэропорта может не совпадать с идеальным местом для автобусной станции.

Ответ, основанный на довольно сложных геометрических соображениях, гласит: идеальным местом для строительства аэропорта была бы такая точка на карте, в которой лучи, проведенные к трем городам, образовывали бы между собой углы в 120°. Если бы число городов возросло до четырех, причем города располагались в вершинах выпуклого четырехугольника, то аэропорт выгоднее всего было бы построить в точке пересечения диагоналей. Доказать это утверждение совсем не трудно. Общая задача (найти точку x, сумма кратчайших расстояний от которой до n заданных точек плоскости минимальна) более трудная.

Может быть, вам удастся придумать простое механическое устройство (аналоговую вычислительную машину), позволяющее быстро находить положение точки x для трех заданных точек на плоскости? Пусть плоскость изображает плоскость стола. В каждой из заданных точек просверлим в крышке стола отверстие. Затем пропустим через эти отверстия по веревочке, верхние концы веревочек свяжем в один узел, а к нижним подвесим одинаковые грузики. Равные силы, действуя на веревочки, заставят их «проголосовать» за жителей трех населенных пунктов, и узел расположится в точке x. Наша аналоговая машина основана на использовании изоморфизма между математической структурой задачи и структурой физической модели.

Усложним теперь исходную задачу. Предположим теперь, что в точках A, B и C находятся не населенные пункты с одинаковым количеством жителей, а три дома, причем в доме A живут 20 школьников, в доме B — 30 школьников и в доме C — 40 школьников. Все дети ходят в одну школу. Где следует выстроить школу, чтобы свести до минимума сумму расстояний, проходимых всеми детьми?

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

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

Сработает ли наше аналоговое устройство, если в одном доме учеников окажется больше, чем в двух других домах, вместе взятых, например, если 20 школьников живут в доме A, 30 школьников — в доме B и 100 школьников — в доме C? Да, сработает: грузик весом в 100 единиц будет тянуть свою веревочку до тех пор, пока узел не совместится с отверстием C. Это означает, что школу следует построить в точке C!

Будет ли наше аналоговое вычислительное устройство работать также безотказно при числе точек больше трех? Попробуйте придумать такое расположение четырех точек, при котором наше устройство даст заведомо неверный результат. Указание: что произойдет, если четыре точки расположены в вершинах невыпуклого четырехугольника?

Изучением систем точек (вершин), соединенных линиями (ребрами), занимается теория графов — обширный и быстро развивающийся раздел современной математики. Существуют десятки теорем теории графов, позволяющие находить минимальные пути. Одни задачи, связанные с отысканием минимальных путей, давно решены, другие ожидают своего решения. Примером знаменитой решенной задачи может служить следующая.

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

Алгоритм Крускала (названный в честь Джозефа Б. Крускала, который впервые предложил его) позволяет свести построение минимальной сети к следующим этапам.

Определить расстояния между любыми двумя точками и расположить все расстояния в порядке возрастания (напомним, что расстоянием между двумя вершинами в графе называется число ребер, ведущих из одной вершины в другую). Кратчайшее расстояние равно 1, затем идет расстояние 2 и т. д. Если два расстояния одинаковы, то безразлично, какое из них считать первым. Соединить отрезками прямых все точки, расстояние между которыми равно 1. Затем соединить отрезками прямых все точки, расстояние между которыми равно 2, 3, 4, 5 и т. д. Никогда не проводить отрезок, замыкающий цикл. Если проведенная линия замыкает цикл, отбросить соответствующую пару точек и перейти к рассмотрению точек, разделенных следующим по величине расстоянием. Проделав все эти операции, мы получим минимальное дерево, соединяющее все заданные точки.

Минимальные деревья обладают интересными свойствами. Например, все рёбра пересекаются только в вершинах, причем в одной вершине пересекается не более 5 ребер.

Минимальные деревья отнюдь не обязательно совпадают с кратчайшей сетью, соединяющей n точек. Напомним, что дополнять сети новыми вершинами не разрешается. Если снять запрет на новые вершины, то сети могут стать короче. В качестве простого примера достаточно рассмотреть четыре вершины единичного квадрата. Минимальное дерево состоит из любых трех сторон квадрата (рис. 13, слева). Предположим, что разрешается вводить новые вершины. Существует ли тогда сеть короче 3, соединяющая четыре вершины?

Большинство людей считает, что минимальную сеть образуют две диагонали квадрата (рис. 13, посредине), но это не верно. Правильное решение изображено на рис. 13, справа. Суммарная длина двух диагоналей квадрата равна 2√2 ≈ 2,82… Суммарная длина сети на правом рисунке меньше, она равна лишь 1 + √3 ≈ 2,73…

Общая задача о построении минимальной сети, соединяющей n заданных точек на плоскости (при условии, что разрешается вводить новые вершины), известна под названием задачи Штейнера. Она решена лишь в отдельных частных случаях. Эффективный алгоритм, позволяющий определять положение «точек Штейнера» (новых вершин) минимального дерева Штейнера, соединяющего n заданных точек плоскости, не известен. Задача Штейнера имеет многочисленные приложения в технике — от элементов микросхем, используемых в ЭВМ, до прокладки кратчайших сетей железных дорог, воздушных маршрутов, телефонных линий и любых других видов транспорта и связи.