Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

44 ГЛАВА 2
этой работы, мы теперь можем исследовать генетические заболевания, рас- познавать мутации, изучать геномы вымерших видов и многое другое.
Геномы закодированы в ДНК — большой органической молекуле в форме двойной спирали. Эта двойная спираль состоит из четырех нуклеотидов: ци- тозина (C), гуанина (G), аденина (A) и тимина (T). Каждая спираль представ- ляет собой последовательность нуклеотидов, такую как ACCGTATAG. Соот- ветствующие нуклеотиды, находящиеся в разных спиралях, связаны между собой по принципу A-T и C-G. Таким образом, если одна спираль имеет вид
ACCGTATAG, то другая выглядит как TGGCATATC.
Определить структуру неизвестного участка ДНК можно следующим об- разом. Мы создаем множество копий цепочки и разбиваем их на мелкие фраг- менты — например, по три нуклеотида в каждом. Эти фрагменты легко рас- познать с помощью специальных инструментов. В итоге мы получаем набор известных фрагментов. Теперь нам остается собрать их в последовательность
ДНК, чью структуру мы уже будем знать.
Представьте, что у нас есть следующие фрагменты (или, как их называют, полимеры): GTG, TGG, ATG, GGC, GCG, CGT, GCA, TGC, CAA и AAT. Все они трой- ные; чтобы получить последовательность ДНК, которую они изначально со- ставляли, создадим граф. Вершинами в этом графе будут двойные полимеры, выведенные из тройных путем отбора первых двух и последних двух нуклеоти- дов. Таким образом из GTG получается GT и TG, а из TGG — TG и GG. Каждая пара вершин, полученная из исходного тройного полимера, соединяется реб- ром. Мы присваиваем название полимера этому ребру. То есть из ATG получа- ются вершины AT и TG, а также ребро ATG. Итоговый граф показан ниже.
AT
TG
GG
GC
CG
GT
CA
AA
ATG
TGG
TGC
GGC
GCG
GCA
CGT
GTG
CAA
AAT

ГРАФЫ 45
Теперь нам остается только найти путь в этом графе, который проходит по каждому ребру ровно один раз (то есть эйлеров цикл), чтобы получить ис- ходную цепочку ДНК. В 1873 году Карл Хирхольцер опубликовал алгоритм для поиска эйлеровых циклов, названный в его честь. Выглядит он так.
1. Выбираем начальный узел.
2. Идем от узла к узлу, пока не вернемся в начало. Пройденный нами путь может охватывать не все ребра.
3. Если существует вершина, которая является частью пути, но при этом принадлежит ребру, которое мы не проходили, мы начинаем с нее еще один путь, используя ранее не пройденные ребра, пока не возвраща- емся в исходную точку. Таким образом у нас получается еще один за- мкнутый путь. Затем мы совмещаем его с путем, пройденным ранее.
Если использовать этот алгоритм для нашего графа, получится следую- щий путь.
AT
TG
GG
GC
CG
GT
CA
AA
ATG
1
TGG
6
TGC
2
GGC 7
GCG
3
GCA
8
CGT
4
GTG5
CAA 9
AAT
10
Мы начинаем в AT и проходим по маршруту AT
→ TG → GG → GC → CA → AA →
AT. Маршрут пройден, но он не охватывает все ребра. Например, у TG есть ребро TGC, которое мы еще не покрыли. Поэтому мы переходим в TG и начи- наем еще один маршрут с ребра TGC; в результате получается TG
→ GC → CG →
GT
→ TG. Совместим этот путь с первым и получим маршрут, представленный

46 ГЛАВА 2
на рисунке, AT
→ TG (→ GC → CG → GT → TG) → GG → GC → CA → AA → AT. Если пройти его от начала и до конца, не доходя до последнего узла, и соединить вершины с общими нуклеотидами ровно по одному разу, получится цепочка
ДНК ATGCGTGGCA. Вы можете убедиться в том, что она содержит все поли- меры, с которых мы начинали; CAA и CAT находятся, если при достижении последней вершины перейти в самое начало.
В этом конкретном примере мы нашли всего один дополнительный ци- клический путь, который затем был совмещен с исходным. Но таких путей мо- жет быть больше; шаг 3 повторяется до тех пор, пока не закончатся вершины с непокрытыми ребрами. Алгоритм Хирхольцера довольно быстрый: если его как следует реализовать, он выполняется за линейное время, O(n), где n — ко- личество ребер в графе.
Планирование турнира
Представьте, что вы занимаетесь организацией турнира, участники которого будут состязаться попарно в цепочке матчей. У нас есть восемь участников, каж- дый из которых сыграет в четырех матчах. Нам нужно создать такой график со- ревнований, чтобы у каждого участника оказалось по одному матчу в день.
Очевидное решение заключается в том, чтобы ограничить весь турнир од- ним матчем в день, растянув его настолько, насколько потребуется. У нас есть восемь участников, каждый из которых играет в четырех матчах, поэтому турнир займет 16 дней (8 × 4 / 2; мы делим на два, чтобы не считать каж- дый матч дважды). Назовем наших участников Элис (A), Боб (B), Кэрол (C),
Дэйв (D), Иви (E), Фрэнк (F), Грейс (G) и Хайди (H). В скобках указаны буквы, которыми мы будем их обозначать.
A
B
C
D
E
F
G
H
A
B
C
D
0 1
0 1
E
F
G
H
0 1
0 1
2 3
3 2
3 2
3 2

ГРАФЫ 47
Мы можем найти лучшее решение, если смоделируем эту задачу в виде графа. Каждый игрок будет представлен отдельной вершиной, а каждый матч — ребром. В результате получится граф, показанный в левой части ри- сунка (см. выше). Справа рядом с ребрами указаны дни, на которые заплани- рованы соответствующие матчи. Как мы получили это решение?
Мы решили пронумеровать дни последовательно. Пусть турнир начина- ется в нулевой день и все матчи проходят один за другим.
1. Берем матч, который мы еще не запланировали. Если все матчи уже за- планированы, останавливаемся.
2. Планируем матч на ближайший день, но так, чтобы ни у одного из игро- ков не было в этот день других матчей. Возвращаемся к шагу 1.
Этот алгоритм выглядит настолько просто, что вы можете даже засомне- ваться, решает ли он нашу задачу. Это обманчивое впечатление. Давайте пройдемся по нему и посмотрим, что получится. В таблице ниже указаны матчи, следующие один за другим, и дни, на которые они запланированы, — все в соответствии с нашим алгоритмом. Сначала читаем первые два столбца, а затем другие два.
Матч
День
Матч
День
A, B
0
C, F
3
A, D
1
C, G
2
A, E
2
D, G
3
A, H
3
D, H
2
B, C
1
E, F
0
B, E
3
E, H
1
B, F
2
F, G
1
C, D
0
G, H
0
В первом матче встречаются Элис и Боб. Ни один из этих игроков больше не будет участвовать в турнире в нулевой день (в день, на который мы запла- нируем матч).
Берем еще один матч, который пока не был запланирован, — скажем,
Элис против Дэйва. Мы отбираем игроков в алфавитном порядке их однобук- венных обозначений, но имейте в виду, что порядок может быть любой, даже

48 ГЛАВА 2
случайный; главное, чтобы матчи не повторялись. У Элис уже есть матч, за- планированный на эту дату, поэтому ближайший свободный день — первый.
Дальше идет матч между Элис и Иви. Элис уже занята в первые два дня, поэтому запланируем матч на день 2. Свой заключительный матч Элис про- ведет против Хайди; дни 0, 1 и 2 распланированы, поэтому данное событие должно произойти в день 3.
С Элис мы закончили. Переходим к матчам Боба и сразу пропускаем тот, который у него должен быть с Элис, так как мы его уже запланировали. Берем матч Боба против Кэрол. Боб уже занят в нулевой день (матч с Элис), поэтому матч будет проведен в день 1. При планировании матча против Иви мы видим, что Боб уже занят в дни 0 и 1, а Иви играет против Элис в день 2, поэтому вы- бираем день 3. Берем матч Боба против Фрэнка; у Боба есть матчи в дни 0, 1 и 3, а Фрэнк полностью свободен, поэтому выбираем день 2 (на день раньше матча Боба против Иви).
После Боба мы переходим к Кэрол. Ни у Кэрол, ни у Дэйва нет матчей в ну- левой день, поэтому они сразятся в первый день турнира. Матч Кэрол против
Фрэнка пройдет в день 3, поскольку Кэрол состязается в дни 0 (только что за- планировали) и 1 (с Бобом), а у Фрэнка есть матч с Бобом. День 2 (это мы тоже запланировали ранее). Матч Кэрол против Грейс пройдет раньше, в день 2, так как Грейс все еще свободна, а у Кэрол нет матчей в этот день.
Аналогичным образом планируются оставшиеся матчи; интересно, что матчи вдоль внешнего и внутреннего прямоугольников графа состоятся в те- чение первых двух дней. У нас получилось две группы игроков, которые сна- чала состязаются параллельно, а затем встречаются между собой. В итоге найденное нами решение существенно превосходит простейший вариант с 16-дневным графиком; нам достаточно всего четырех дней!
На самом деле планирование турнира — это разновидность более общей задачи: раскраски ребер. Эта задача состоит в распределении цветов между ребрами таким образом, чтобы никакие два смежных ребра не имели один и тот же цвет. Конечно, цвет здесь — образное понятие. В нашем примере вместо цветов использовались номера дней; в целом это может быть любой другой набор уникальных значений. Если вместо ребер раскрашивать вер- шины и делать это так, чтобы никакие две из них, соединенные общим реб- ром, не имели один и тот же цвет, получится задача раскраски вершин. Как вы уже могли догадаться, обе эти задачи принадлежат к более общей категории, известной как задача раскраски графа.
Алгоритм раскраски ребер, описанный выше, отличается простотой и эф- фективностью (он последовательно проходит по каждому ребру, и делает

ГРАФЫ 49
это всего один раз). Алгоритмы такого рода называют жадными. Они пыта- ются решить задачу путем поиска оптимального решения на каждом этапе, не заботясь об общем результате. Жадные алгоритмы подходят для многих случаев, в которых на каждом этапе необходимо принимать решение, «оп- тимальное в текущий момент». Стратегии, которыми руководствуется алго- ритм при принятии решений, называются эвристиками от греч.
εὑρίσκω —
«искать» [решение].
Но, если немного подумать, такой недальновидный способ принятия решений может оказаться не лучшим. Иногда имеет смысл проявить не- которую сдержанность; выбор, кажущийся оптимальным в текущий мо- мент, может привести к последствиям, о которых мы позже пожалеем.
Представьте, что вы взбираетесь на гору. Если следовать жадной эври- стике, на каждом этапе нужно выбирать самый крутой подъем (предполо- жим, что вы опытный скалолаз). Но так не всегда можно добраться до вер- шины: есть вероятность очутиться на плоскогорье, с которого придется спускаться обратно. Настоящий путь к вершине может пролегать по более пологим склонам.
Метафору со скалолазанием часто используют при решении задач в ин- форматике. Задача моделируется так, чтобы решение находилось на «вер- шине», к которой ведут разные потенциальные действия; идея в том, чтобы найти правильное сочетание действий. Этот подход называется поиск восхо-
ждением к вершине. Плато в таком случае является локальным оптимумом, а вершина, на которую мы взбираемся, — глобальным оптимумом.
Вернемся от скалолазания к планированию турнира. Мы выбрали ближай- ший свободный день для каждого матча. К сожалению, это может быть не луч- шим способом планирования. Действительно, раскраска графа — сложная задача. Составленный нами алгоритм не гарантирует получение оптималь- ного результата — такого, для которого требуется наименьшее количество дней (или цветов, если говорить в целом). У узла графа есть степень — число выходящих из него ребер. Мы можем доказать, что в случае, если наивысшая степень любого узла в графе равна d, для раскраски всех ребер достаточно d или d + 1 цветов; количество цветов, необходимое для раскраски ребер, на- зывается хроматическим индексом графа. В конкретном примере наше ре- шение является оптимальным, d = 4 (четыре дня). Но в других графах ал- горитм может выдать не лучший результат. Плюс жадной раскраски графа в том, что мы знаем, насколько сильно решение способно отклониться от оп- тимума: потенциальное количество цветов может превышать d и достигать
2d — 1, но не более того.

50 ГЛАВА 2
Если вам интересно, как это может произойти, взгляните на граф, кото- рый состоит из «звезд», соединенных с центральным узлом.
1 2
3 1
2 3
1 2
3 4
5 6
2 3
4 1
3 4
1 2
4 1
2 3
Если число звезд равно k и у каждой звезды есть k ребер, не считая того, которое ведет к центральному узлу, для раскраски ребер звезд понадобится
k цветов. Нам нужно еще k цветов, чтобы соединить звезды с центральным узлом. Всего получается 2k цветов. Это то, что было сделано слева. Но это не идеальное решение. Если мы начнем с раскраски ребер, соединяющих звезды с центральным узлом, нам хватит k цветов. А для раскраски самих звезд будет достаточно одного дополнительного цвета. Итого k + 1 цветов.
Этот подход проиллюстрирован справа. Все это соответствует теории, так как степень каждой звезды равна k + 1.
Но проблема в том, что жадный алгоритм выбирает порядок раскраски ребер, который в итоге оказывается неоптимальным (или, если быть более точным, не глобально оптимальным). Он может выдать лучшее решение, а может и нет. Но, опять же, отклонение от оптимального решения не такое уж большое. Это смягчает проблему, так как задача раскраски графа очень сложная, и алгоритм, который находит лучшее решение в каждом случае, имеет экспоненциальную сложность, около O(2
n
), где n — количество ребер в графе. Такие точные алгоритмы зачастую применимы только для крошеч- ных графов.
У жадного алгоритма, который мы здесь представили, есть одна замеча- тельная особенность (если не считать его практичность). Это онлайн-алго-
ритм. Он работает, даже если ввод известен не с самого начала, а предостав- ляется по ходу продвижения вперед. Для его запуска не нужно знать обо всех ребрах. Алгоритм будет работать правильно, даже если граф генерируется прямо на лету, по одному ребру за раз. Это может произойти, если игроки продолжают записываться для участия в турнире даже после того, как мы начали планировать матчи. Мы можем раскрашивать каждое ребро (матч) при его появлении, и по завершении создания графа он уже будет раскра- шен. Более того, если граф создается постепенно, этот жадный алгоритм оказывается оптимальным; для графа, который формируется прямо в про- цессе решения задачи, не существует точного алгоритма, даже самого не- эффективного.

ГРАФЫ 51
Кратчайшие пути
Как мы уже видели, жадный алгоритм принимает лучшее решение на каж- дом этапе, что может не привести к лучшему итоговому результату. Можно сказать, что он имеет оппортунистический, недальновидный характер. К со- жалению, как мы знаем из басни Эзопа, кузнечик, живущий сегодняшним днем, может пожалеть о своем решении зимой, а муравей, который думает о будущем, окажется в тепле и уюте. Но, если говорить о планировании тур- нира, участь кузнечика может быть не так уж печальной. Теперь давайте по- смотрим, что на это ответит муравей.
В главе 1 мы отмечали, что поиск кратчайшего пути между двумя точками на сетке лучше не делать путем перебора всех возможных вариантов. Вы сами видели, что на практике этот подход неосуществим, так как количество путей растет огромными темпами. Но теперь, когда мы познакомились с графами, эта задача кажется не такой безнадежной. Давайте поднимемся на уровень выше. Сетка имеет простую геометрию с равными расстояниями между со- седними точками; давайте исходить из того, что мы имеем дело с сеткой лю- бой формы, точки в которой могут находиться на разных расстояниях друг от друга.
Для этого мы создадим граф, узлы и ребра которого представляют карту, и попробуем найти кратчайший путь между двумя его узлами. Кроме того, каждому ребру будет назначен вес. Это нулевое или положительное значе- ние, соответствующее расстоянию между двумя соединенными узлами. Рас- стояние может измеряться в километрах или времени, которое занимает его прохождение; подойдут любые неотрицательные величины. Таким образом
длина пути будет суммой весов всех его ребер; кратчайшим путем между двумя узлами является тот, который имеет наименьшую длину. Если все веса равны 1, длина пути равна количеству ребер, из которых он состоит. Если до- пускаются другие значения, это утверждение неверно.
Следующий граф состоит из шести узлов, соединенных девятью ребрами с разными весами. Мы хотим найти кратчайший путь из A в F.
Если применить жадную эвристику, вначале мы перейдем из A в C, затем лучшим выбором будет E, а оттуда уже можно попасть в F. Общая длина пути A,
C, E и F равна 8, что не является оптимальным решением. Лучше всего пройти из A в C, затем в D и, наконец, в F; длина этого варианта — 6. Итак, жадная эв- ристика не работает, и, в отличие от примера с планированием турнира, мы не знаем, насколько хуже ее результат может быть по сравнению с настоящим кратчайшим путем. Тем не менее и, опять же, в отличие от планирования