Упражнение с решением 2

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

Задачу можно абстрактно смоделировать следующим образом. Допустим, име- ется ненаправленный граф G = (V, E), предоставляющий план здания; два робота изначально расположены в узлах a и b графа. Робот в узле a должен переместиться к узлу c по пути в графе G, а робот в узле b должен переместиться к узлу d. Для этого используется механизм планирования: на каждом временном отрезке один из роботов перемещается по одному ребру, от ребра к соседнему узлу; в конце периода планирования робот из узла a должен находиться в узле c, а робот из узла b — в узле d.

Планирование свободно от помех, если не существует точки, в которой два робота занимают узлы на расстоянии < r друг от друга в графе (для заданного па- раметра r). Предполагается, что два начальных узла a и b находятся на расстоянии, большем r (как и два конечных узла c и d).

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

Решение

Рассматриваемая задача относится к более общей категории: имеется набор воз- можных конфигураций для роботов (под конфигурацией понимается выбор ме- стонахождения каждого робота). Мы пытаемся перейти из заданной начальной конфигурации (a, b) в конечную конфигурацию (c, d), принимая во внимание ограничения на возможность перемещения между конфигурациями (робот может перейти только в соседний узел) и на то, какие конфигурации считаются «допу- стимыми».

Задача получается довольно сложной, если рассматривать происходящее на уровне нижележащего графа G: для заданной конфигурации роботов (то есть текущего местонахождения каждого робота) неясно, какое правило следует ис- пользовать для принятия решения о перемещении одного из роботов. Вместо этого применяется идея, которая часто бывает очень полезной в ситуациях с подобным поиском. Можно заметить, что задача очень похожа на задачу поиска пути — но не в исходном графе G, а в пространстве всех возможных конфигураций.

Определим следующий граф H (большего размера). Множество узлов H со- ответствует множеству всех возможных конфигураций роботов; иначе говоря, H состоит из всех возможных пар узлов в G. Два узла H соединяются ребром, если они представляют конфигурации, которые могут занимать последовательные по- зиции в процессе планирования; иначе говоря, (u, v) и (u', v') соединяются ребром в H, если одна из пар u, и' или v, v' состоит из одинаковых значений, а другая пара соответствует ребру в G.

Мы уже видим, что пути из (a, b) в (с, d) в H соответствуют правилам плани- рования для роботов: такой путь состоит из последовательности конфигурации, в которой на каждом шаге один робот пересекает ровно одно ребро в G. Тем не менее в расширенной формулировке еще не отражено правило, согласно которому планирование должно быть свободно от помех.

Для этого из H просто удаляются все узлы, соответствующие конфигурациям с помехами. Таким образом определяется H' — граф, полученный удалением всех узлов (u, v), для которых расстояние между и и v в G не превышает r.

В этом случае полный алгоритм выглядит так. Мы строим граф H', а затем вы- полняем алгоритм из текста для проверки существования пути из (a, b) в (с, d). Правильность работы алгоритма следует из того факта, что пути в H' соответству- ют процессам планирования, а узлы H' точно соответствуют конфигурациям без помех.

Остается оценить время выполнения. Пусть n — количество узлов в G, а m — количество ребер в G. Чтобы проанализировать время выполнения, мы сформу- лируем оценки для: (1) размера графа H' (который в общем случае больше G), (2) времени построения H' и (3) времени поиска пути от (a, b) к (с, d) в H.

1. Начнем с размера H'. Граф H' содержит не более n2 узлов, так как его узлы соответ- ствуют парам узлов в G. Сколько же ребер содержит H' ? С узлом (u, v) связаны ребра (u', v) для каждого соседа и' узла и в G и ребра (u, v') для каждого соседа v' узла v в G. Чтобы сформулировать простую верхнюю границу, заметим, что име- ется не более n вариантов для (u', v) и не более n вариантов для (u, v'), поэтому каждый узел H' имеет максимум 2n инцидентных ребер. Суммируя по (макси- мум) n2 узлам H', получаем O(n3) ребер. (Вообще говоря, для количества ребер H' можно дать улучшенную границу O(mn) на основании границы (3.9), доказанной в разделе 3.3, для суммы степеней графа. Мы вернемся к этой теме позднее.)

2. Перейдем ко времени, необходимому для построения H'. Чтобы построить H, мы переберем все пары узлов в G за время O(n2) и построим ребра по приведен- ному выше определению за время O(n) на каждый узел, за общее время O(n3). Теперь нужно определить, какие узлы следует удалить из H для получения H'. Это можно сделать так: для каждого узла и в G запускается поиск в ширину от u, который находит все узлы v, находящиеся на расстоянии не более r от u. Все такие пары (u, v) удаляются из H. Каждый поиск в ширину в G выполняется за время O(m + n), и мы проводим по одному такому поиску от каждого узла, по- этому общее время для этой части составит O(mn + n2).

3. Итак, граф H’ построен, и теперь достаточно определить, существует ли путь из (a, b) в (с, d). Для этого можно воспользоваться алгоритмом связности (см. выше) за время, линейное по отношению к количеству ребер и узлов H’. Так как H' состоит из O(n[3]) узлов и O(n[4] [5]) ребер, последний шаг также выполняется за полиномиальное время.

Упражнения

1. Рассмотрим направленный ациклический граф G на рис. 3.10. Сколько тополо- гических упорядочений он имеет?

Рис. 3.10. Сколько топологических упорядочений существует у этого графа?


делить n образцов на две группы (относящиеся к видам A и B), но напрямую классифицировать каждый отдельно взятый образец очень трудно. Вместо этого они решают действовать немного иначе.

Каждая пара образцов i и j располагается рядом и тщательно изучается. Если исследователи достаточно уверены в своей оценке, они помечают образцы из пары (i, j) либо как «одинаковые» (то есть как относящиеся к одному виду), либо как «разные» (то есть как относящиеся к разным видам). Также они могут отказаться от назначения оценки конкретной паре; в таком случае пара назы- вается неопределенной.

Итак, имеется набор из n образцов, а также набор из m оценок («одинаковые» или «разные») для пар, которые не были отнесены к неопределенным. Вашим друзьям хотелось бы знать, соответствуют ли эти данные представлению о том, что каждая бабочка относится к одному из видов A или B. Говоря конкретнее, набор из m оценок объявляется непротиворечивым, если возможно пометить каждый образец A или B так, чтобы для каждой пары (i, j) с пометкой «оди- наковые» i и j относились к одному виду, а для каждой пары (i, j) с пометкой «разные» i и j относились к разным видам. Ваши друзья возятся с проверкой непротиворечивости оценок, как вдруг один из них осознает: ведь вы сможете придумать алгоритм, который позволит с ходу получить ответ на этот вопрос. Предложите алгоритм для проверки непротиворечивости оценок с временем выполнения O(m + n).

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

6. Имеется связный граф G = (V, E) и конкретная вершина и V. Предположим, при вычислении дерева поиска в глубину с корнем и было получено дерево T, включающее все узлы G. После этого при вычислении дерева поиска в ширину с корнем и было получено то же дерево T. Докажите, что G = T. (Иначе говоря, если T одновременно является деревом поиска в глубину и в ширину с корнем в u, то G не может содержать ребер, не принадлежащих T.)

7. Ваши друзья, занимающиеся технологиями беспроводных сетей, в настоя- щее время изучают свойства сети из n мобильных устройств. Перемещаемые устройства (или вернее, их хозяева) в любой момент времени определяют граф по следующим правилам: существует узел, представляющий каждое из n устройств, и между i и j существует ребро, если физические позиции i и j находятся на расстоянии не более 500 метров. (В таком случае устройства на- ходятся «в пределах дальности» друг друга.)

Чтобы сеть устройств по возможности оставалась связной, перемещение устройств ограничивается по следующему правилу: в любое время каждое устройство i должно находиться на расстоянии не более 500 метров от по крайней мере n/2 других устройств (где n — четное число). Требуется узнать: гарантирует ли это свойство само по себе, что сеть будет оставаться связной?

Ниже приведена конкретная формулировка этого вопроса как утверждения применительно к графам.

Утверждение: пусть G — граф из n узлов, где n — четное число. Если каждый узел G имеет степень не менее n/2, то граф G является связным.

Считаете вы это утверждение истинным или ложным? Приведите доказатель- ство истинности или ложности.

8. Во многих публикациях, посвященных структуре Интернета и Всемирной паутины, в том или ином виде обсуждался следующий вопрос: на каком рас- стоянии находятся типичные узлы этих сетей? Если внимательно читать такие статьи, выясняется, что многие из них путают понятия диаметра сети и среднего расстояния в сети; авторы используют эти понятия так, словно они являются взаимозаменяемыми.

В соответствии с нашей терминологией расстоянием между двумя узлами и и v в графе G = (V, E) называется минимальное количество ребер в пути, связываю- щем эти узлы; расстояние будет обозначаться dist(и, v). Диаметром G называется максимальное расстояние между любой парой узлов G; эта характеристика будет обозначаться diam(G).


Определим сопутствующую характеристику, которая будет называться средним попарным расстоянием в G, обозначим ее apd(G). Величина apd(G) вычисляется


Другими словами,

Простой пример наглядно показывает, что существуют графы G, для которых diam(G) Ф apd(G). Пусть G — граф с тремя узлами u, v, w и двумя ребрами {u, v} и {v, w}. Тогда

diam(G) = dist(и, w) = 2,

при том, что

apd(G) = [dist(и, v) + dist(и, w) + dist(v, w)] / 3 = 4/3.

Конечно, эти два числа не так уж сильно отличаются в случае графа из трех узлов; будет естественно задаться вопросом, всегда ли между ними существу- ют тесные отношения. Следующее утверждение пытается формализовать этот вопрос.

Утверждение: существует положительное натуральное число с, при котором для любого связного графа G выполняется условие

diи>i} (G)

apd(G)

Считаете вы это утверждение истинным или ложным? Приведите доказатель- ство истинности или ложности.

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

Допустим, ненаправленный граф G = (V, E) из n узлов содержат два узла 5 и t, расстояние между которыми строго больше n/2. Покажите, что должен суще- ствовать некоторый узел v, отличный от 5 и t, такой, что удаление v из G при- ведет к уничтожению всех путей s-t. (Другими словами, граф, полученный из G посредством удаления v, не содержит путей от 5 к t.) Предложите алгоритм поиска такого узла v с временем выполнения O(m + n).

10. Во многих музеях можно увидеть работы художника Марка Ломбарди (1951- 2000), которые представляют собой художественно воспроизведенные графы. На этих графах изображены полученные в результате серьезных исследований отношения между людьми, замешанными в крупных политических скандалах за последние десятилетия: узлы представляют участников, а ребра — некие от- ношения в парах. Если внимательно присмотреться к этим рисункам, можно проследить довольно зловещие пути от высокопоставленных государственных служащих США через бывших деловых партнеров и швейцарские банки к под- польным торговцам оружием.

Такие изображения служат ярким примером социальных сетей, в которых, как упоминалось в разделе 3.1, узлы представляют людей и организации, а ре- бра — различного рода отношения. Короткие пути, в изобилии встречающиеся в таких сетях, в последнее время привлекают общественное внимание: люди размышляют над их смыслом. В случае с графами Марка Ломбарди такие пути наводят на мысли о короткой последовательности шагов, приводящих от хоро- шей репутации к позору.

Конечно, один короткий путь между узлами v и w в такой сети может объяс- няться простой случайностью; большое количество коротких путей между v и w выглядит куда убедительнее. По этой причине наряду с задачей вычисления одного кратчайшего пути v-w в графе G исследователи социальных сетей зани- мались рассмотрением задачи определения количества кратчайших путей v-w. Как выяснилось, у этой задачи есть эффективное решение. Допустим, имеется ненаправленный граф G = (V, E), в котором выделены два узла v и w. Приведите алгоритм, который вычисляет количество кратчайших путей v-w. (Алгоритм не должен выводить все пути; достаточно указать их количества.) Алгоритм дол- жен выполняться за время O(m + n) для графа с n узлами и m ребрами.

11. Вы помогаете специалистам по безопасности отслеживать распространение компьютерного вируса. Система состоит из n компьютеров C1, C2, ..., Cn; на входе вы получаете набор данных трассировки с указанием времени взаимодействий между парами компьютеров. Таким образом, данные представляют собой по- следовательность упорядоченных триплетов вида (C, C, tk), сообщающих, что между компьютерами C. и C. передавались данные во время tk. Общее количе- ство триплетов равно m.

Предполагается, что триплеты передаются отсортированными по времени. Для простоты будем считать, что каждая пара компьютеров обменивается данными не более одного раза за интервал наблюдения. Специалисты по безопасности хотели бы иметь возможность получать ответы на вопросы следующего типа: если вирус был внедрен на компьютер Ca во время х, мог ли он достичь ком- пьютера Cb ко времени у? Механика распространения вируса проста: если за- раженный компьютер C. взаимодействует с незараженным компьютером C. во время tk (другими словами, если в данных трассировки присутствует один из триплетов (C, C, tk) или (C, C, tk)), то компьютер C. тоже становится заражен- ным начиная с времени tk.

Таким образом, вирус передается с машины на машину через серию взаимодей- ствий; предполагается, что ни один шаг в этой последовательности не подра- зумевает перемещения назад во времени. Например, если компьютер C. заражен к моменту tk, и данные трассировки содержат триплеты (C, C, tk) и (C, Cq, t), где tk < t, то компьютер Cq будет заражен через C. (Обратите внимание: время tk может быть равно t; это означало бы, что у C . были одновременно открыты под- ключения к C. и C , так что вирус мог переместиться с C. на Cq.)

Допустим, для n = 4 данные трассировки состоят из триплетов

и вирус был внедрен на компьютер Cl во время 2. В этом случае компьютер C3 будет заражен ко времени 8 серией из трех шагов: сначала C2 заражается во вре- мя 4, затем C4 получает вирус от C2 ко времени 8 и, наконец, C3 получает вирус от C4 ко времени 8. С другой стороны, если бы данные трассировки имели вид

и вирус снова был бы внедрен на компьютер Cl во время 2, то компьютер C3 не был бы заражен за наблюдаемый период: хотя C2 заражается к времени 14, мы видим, что C3 взаимодействует с C2 до заражения C2. Никакая последователь- ность взаимодействий с прямым перемещением во времени не приведет к рас- пространению вируса с C1 на C3 во втором примере.

Разработайте алгоритм, который позволит получить ответы на вопрос типа: для заданного набора данных трассировки необходимо определить, сможет ли вирус, внедренный на компьютере Ca во время х, заразить компьютер Cb ко вре- мени у. Алгоритм должен выполняться за время O(m + n).

12. Вы помогаете группе ученых-этнографов в анализе устных исторических дан- ных о людях, живших в некоторой деревне за последние двести лет. В этих материалах ученые узнали о множестве из n людей (все эти люди уже умерли), которых мы будем обозначать P1, P2, ..., Pn. Также были собраны сведения о вре- мени жизни этих людей друг относительно друга. Каждый факт представлен в одной из двух форм:

• для некоторых i и j человек P умер до рождения человека P; или

1 J

• для некоторых i и j сроки жизни P. и P. перекрывались по крайней мере частично.

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнение с решением 2:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.