Перегнал Practical Common Lisp в формат fb2, не без помощи OpenOffice с ooofbtools, а также ручной правки.
Сноски, таблицы, иллюстрации, цитаты и код оформлены правильными fb2-тегами. Книга будет нормально выглядеть на LBook и прочих карманных девайсах.
Скачать можно здесь.
Алсо, pdf-файл с книгой раньше находился на сайте издательства Apress, но почему-то пропал. Здесь лежит копия.
воскресенье, 7 декабря 2008 г.
вторник, 25 ноября 2008 г.
Реверсивный поиск и перебор поддеревьев графа
Большинство комбинаторных и оптимизационных проблем содержат в себе задачу обхода вершин некоего связного графа. Граф, как правило, имеет большой размер и не задан явно, иначе перебор его вершин не составил бы труда. Известна лишь какая-то начальная вершина; также для каждой полученной в процессе перебора вершины можно узнать список смежных с ней вершин. Задача проста: посетить все вершины графа по одному разу.
Существуют два классических алгоритма для решения этой задачи: поиск в глубину (depth-first search) и поиск в ширину (breadth-first search). Оба алгоритма требуют, кроме памяти для хранения «фронта» (стека или очереди) вершин, которые будут посещены, дополнительной памяти для запоминания тех вершин, которые уже посещены.
При некотором условии можно написать рекурсивный алгоритм обхода, не требующий запоминания посещённых вершин. Алгоритм был предложен в 1996 году и называется «реверсивный поиск» (reverse search) [1]. Для его работы требуется, чтобы для каждой вершины v графа была определена соседняя вершина f(v), имеющая максимальный «приоритет». f должна быть задана так, чтобы любой путь вида v → f(v) → f(f(v)) → ... заканчивался, и обязательно в одной и той же вершине v*. Для определённости положим f(v*)=v*.
Простейший пример: пронумеруем вершины графа натуральными числами (p(v)) и определим f(v) как вершину, имеющую максимальный номер среди множества nei(v) всех соседей v. Конечно, не любая нумерация будет соответствовать критерию. На множестве V вершин графа функция p должна иметь единственный локальный максимум, он же и глобальный.
Рассмотрим граф T, множество вершин которого совпадает с V, а ребро между u и w есть, когда u=f(w) или w=f(u). Несложно показать, что этот граф будет деревом. На рисунке рёбра дерева обозначены стрелками, ведущими от v к f(v), по возрастанию номера вершины.
Собственно алгоритм реверсивного поиска очень прост:
После этого примера может создаться впечатление, что алгоритм вообще не имеет смысла, т.к. все заботы, связанные с отбрасыванием уже посещённых вершин, переложены на функцию f, и посчитать её не проще, чем обойти все вершины графа. Это не так: на многих графах, заданных неявно с использованием терминов какой-либо предметной области, функция f тривиально формулируется в тех же терминах. Авторы в своей статье приводят алгоритмы для перебора:
Мы покажем алгоритм перебора всех поддеревьев произвольного графа G, основанный на реверсивном поиске. Множество вершин V графа поиска соответствует множеству поддеревьев G. Мы будем считать, что между вершинами u и w есть ребро, если u получается из w добавлением или удалением одного ребра из графа G. Допустим, что рёбра графа G как-то упорядочены. Будем считать, что u=f(w), если u получается из w удалением максимального ребра (не считая тех рёбер, после удаления которых получается два дерева вместо одного). Нетрудно понять, что вершина v* в таком случае будет соответствовать пустому подграфу G.
Небольшой пример: построим граф поиска всех поддеревьев графа из трёх вершин:
Каждый узел графа поиска соответствует одному из поддеревьев нашего графа; пустое поддерево не является исключением.
Направления стрелок соответствуют удалению рёбер с максимальным номером в исходном графе.
Шаги 1 и 2 алгоритма перебора поддеревьев соответствуют шагам 3 и 4 общего алгоритма реверсивного поиска, т.к. известно, что начальное поддерево — пустое и искать его не надо. Кроме того, держать поддеревья на стеке не требуется; можно вместо поддерева класть на стек рёбра исходного графа. Каждое ребро кладётся на стек дважды: первый раз для добавления в поддерево, второй раз для удаления из него.
[1] David Avis, Komei Fukuda. Reverse search for enumeration. Discrete applied mathematics 65, pp. 21-46, 1996.
Существуют два классических алгоритма для решения этой задачи: поиск в глубину (depth-first search) и поиск в ширину (breadth-first search). Оба алгоритма требуют, кроме памяти для хранения «фронта» (стека или очереди) вершин, которые будут посещены, дополнительной памяти для запоминания тех вершин, которые уже посещены.
При некотором условии можно написать рекурсивный алгоритм обхода, не требующий запоминания посещённых вершин. Алгоритм был предложен в 1996 году и называется «реверсивный поиск» (reverse search) [1]. Для его работы требуется, чтобы для каждой вершины v графа была определена соседняя вершина f(v), имеющая максимальный «приоритет». f должна быть задана так, чтобы любой путь вида v → f(v) → f(f(v)) → ... заканчивался, и обязательно в одной и той же вершине v*. Для определённости положим f(v*)=v*.
Простейший пример: пронумеруем вершины графа натуральными числами (p(v)) и определим f(v) как вершину, имеющую максимальный номер среди множества nei(v) всех соседей v. Конечно, не любая нумерация будет соответствовать критерию. На множестве V вершин графа функция p должна иметь единственный локальный максимум, он же и глобальный.
Рассмотрим граф T, множество вершин которого совпадает с V, а ребро между u и w есть, когда u=f(w) или w=f(u). Несложно показать, что этот граф будет деревом. На рисунке рёбра дерева обозначены стрелками, ведущими от v к f(v), по возрастанию номера вершины.
Собственно алгоритм реверсивного поиска очень прост:
- Выбрать произвольную вершину v
- Если v≠f(v), то присвоить v←f(v) и перейти к шагу 1
- Положить на стек вершину v
- Пока стек не пуст:
- Снять со стека вершину u
- «Посетить» u
- Для каждой вершины w ∈ nei(u):
- Если f(w)=u, то положить w на стек
- Снять со стека вершину u
После этого примера может создаться впечатление, что алгоритм вообще не имеет смысла, т.к. все заботы, связанные с отбрасыванием уже посещённых вершин, переложены на функцию f, и посчитать её не проще, чем обойти все вершины графа. Это не так: на многих графах, заданных неявно с использованием терминов какой-либо предметной области, функция f тривиально формулируется в тех же терминах. Авторы в своей статье приводят алгоритмы для перебора:
- триангуляций точек на плоскости
- остовных деревьев графа
- остовных деревьев графа на плоскости с непересекающимися рёбрами
- связных индуцированных подграфов графа
- вершин n-мерного выпуклого многогранника, заданного гиперплоскостями граней
- и других объектов
Мы покажем алгоритм перебора всех поддеревьев произвольного графа G, основанный на реверсивном поиске. Множество вершин V графа поиска соответствует множеству поддеревьев G. Мы будем считать, что между вершинами u и w есть ребро, если u получается из w добавлением или удалением одного ребра из графа G. Допустим, что рёбра графа G как-то упорядочены. Будем считать, что u=f(w), если u получается из w удалением максимального ребра (не считая тех рёбер, после удаления которых получается два дерева вместо одного). Нетрудно понять, что вершина v* в таком случае будет соответствовать пустому подграфу G.
Небольшой пример: построим граф поиска всех поддеревьев графа из трёх вершин:
Каждый узел графа поиска соответствует одному из поддеревьев нашего графа; пустое поддерево не является исключением.
Направления стрелок соответствуют удалению рёбер с максимальным номером в исходном графе.Шаги 1 и 2 алгоритма перебора поддеревьев соответствуют шагам 3 и 4 общего алгоритма реверсивного поиска, т.к. известно, что начальное поддерево — пустое и искать его не надо. Кроме того, держать поддеревья на стеке не требуется; можно вместо поддерева класть на стек рёбра исходного графа. Каждое ребро кладётся на стек дважды: первый раз для добавления в поддерево, второй раз для удаления из него.
- Для каждого ребра e графа G
- Положить e на стек
- S ← пустой граф
- Пока стек не пуст:
- Снять ребро j со стека
- Если j ∈ S:
- Удалить j из S
- Иначе:
- Добавить j в S
- «Посетить» S
- Положить j на стек
- Для каждого ребра h графа G, соседнего с одним из рёбер S и не принадлежащего S:
- S’ ← S + h
- Если S’ — дерево и если h — максимальное ребро S’, содержащее вершину степени 1, то положить h на стек
- S’ ← S + h
- Добавить j в S
- Снять ребро j со стека
[1] David Avis, Komei Fukuda. Reverse search for enumeration. Discrete applied mathematics 65, pp. 21-46, 1996.
воскресенье, 7 сентября 2008 г.
Канонический код дерева
Канонический код графа (graph canonical code) — это уникальная строка, которая не зависит от порядка нумерации вершин. У изоморфных графов одинаковые канонические коды, у неизоморфных — разные.
Вершины и рёбра графа могут быть снабжены дополнительными метками (цветами). В этом случае канонический код включает в себя цветовые идентификаторы.
Канонические коды графов позволяют избавиться от дорогостоящей процедуры проверки изоморфизма (graph isomorphism), и определять совпадение графов по сравнению строк.
Например, как найти дубликаты в множестве N графов? Вычислить N канонических кодов, отсортировать их и последовательно сравнить. Гораздо выгоднее, чем делать N*(N-1)/2 проверок изоморфизма. Можно сказать, что канонический код — это хеш-код без промахов.
Канонический код может выглядеть по-разному: как матрица смежности, развёрнутая в строку, или как маршрут обхода графа в ширину, или в глубину. Какое представление выбрать, не столь важно. Задача в любом случае сводится к вычислению канонической нумерации вершин (canonical numbering, canonical labeling). Каноническая нумерация — это нумерация (перестановка) вершин графа, гарантирующая, что изоморфные графы будут пронумерованы одинаково. Получив нужную перестановку, уже не составит труда построить канонический код, например, по обходу графа в глубину: начать обход с вершины под номером 1 и при ветвлении выбирать ту вершину, «канонический номер» которой меньше.
Наличие полиномиального алгоритма для задачи канонической нумерации означало бы, что задача изоморфизма графов полиномиально разрешима. На данный момент, для задачи изоморфизма графов полиномиального алгоритма не найдено, но и не доказана NP-полнота (в отличие от известной задачи изоморфизма подграфу, subgraph isomorphism). По некоторым признакам можно предполагать, что она не является NP-полной.
В ряде частных случаев существуют полиномиальные алгоритмы проверки изоморфизма и канонической нумерации. Мы рассмотрим простейший случай: когда граф является деревом.
В книге Ахо, Хопкрофта и Ульмана «Построение и анализ вычислительных алгоритмов» приводится алгоритм для определения изоморфизма двух деревьев (tree isomorphism), работающий за линейное время от количества вершин. На его основе нетрудно составить алгоритм канонической нумерации вершин дерева, работающий за то же линейное время.
Этап 1. Выделение корня
Отрубим от дерева все листья. Получится дерево меньшего размера. Будем повторять процедуру до тех пор, пока не останется одна вершина (center) или две вершины, соединённых ребром (bicenter).
Если осталась одна вершина, мы делаем её корнем и располагаем остальные вершины по уровням, считая от корня:
Если осталось ребро, мы располагаем остальные вершины по уровням, считая от этого ребра, обе вершины которого помещаются на первый уровень:
Мы разделили N вершин на K уровней так, что у каждой вершины на уровне k>1 есть «родитель» из уровня k-1. Вспомним ещё, что вершины и рёбра снабжены цветами. В наших обозначениях вершины будут красные и синие, а рёбра — чёрные и зелёные.
Этап 2. Поуровневая сортировка
Для алгоритма нужно задать условный порядок на цветах. Пусть красный цвет будет старше синего, а зелёный старше чёрного. Введём обобщённый код вершины, состоящий из цветового кода ребра, которое соединяет её с родителем, и из цветового кода самой вершины. Сгруппируем вершины нижнего уровня, имеющие одинаковый обобщённый код, и присвоим каждой группе ранг, соответствующий старшинству цветов. Цвет ребра имеет больший приоритет, чем цвет вершины. Ранг 0 считается самым старшим:
Составим обобщённые коды родителей этих вершин, которые расположены на предыдущем уровне. Кроме цветовых кодов ребра к родителю и самой вершины, включим в обобщённый код отсортированный список рангов её детей. Ранги детей имеют меньший приоритет, чем цветовые коды вершины и ребра:
Повторяем описанную процедуру:
и ещё раз:
Пока не дойдём до уровня 1. В нашем случае на первом уровне одна вершина, поэтому её ранг нулевой, в случае двух вершин на первом уровне нужно сравнить их обобщённые коды и присвоить им ранги 0 и 1 (или 0 и 0).
Этап 3. Нумерация
Начиная с уровня 1, присваиваем вершинам возрастающие номера в порядке возрастания их рангов. В случае совпадения рангов на уровне порядок присваивания номеров может быть любым, т.к. вершины с одинаковым рангом в некотором смысле идентичны. (Выражаясь математически, эти вершины лежат на одной орбите, т.е. существует автоморфизм графа, переводящий одну вершину в другую.)
Построение канонического кода
Как было сказано, строить канонический код можно многими способами. Приведём пример канонического кода, построенного при обходе дерева в глубину:
Для построения такого кода не нужен даже третий этап предыдущего алгоритма (нумерация). Мы начинаем обход с корня и для каждой посещённой вершины обходим её детей в порядке старшинства. Для определения старшинства детей хватит «внутриуровневых» кодов, полученных на этапе 2.
Анализ сложности
Этап 1, очевидно, требует O(N) операций. Нетрудно также понять, что на этапе 2 мы, двигаясь от последнего уровня к первому, проходим все вершины по одному разу. Затруднения может вызвать только процесс «ранжирования» вершин на уровне, но при использовании поразрядной сортировки он занимает время, пропорциональное количеству вершин, и суммарно по уровням получается тоже O(N) операций. Этап 3 и построение самого кода также занимают линейное время.
Каноническая нумерация в общем случае
Австралийский профессор Brendan McKay написал библиотеку на C под названием nauty. Она предназначена для поиска групп автоморфизмов произвольных графов; одним из её «побочных» результатов является каноническая нумерация вершин.
Nauty работает очень быстро. Цвета рёбер она не поддерживает, но при необходимости всегда можно добавить в граф псевдо-вершины таким образом, что каноническая нумерация получившегося графа без учёта цветов рёбер будет являться канонической для исходного графа.
Вершины и рёбра графа могут быть снабжены дополнительными метками (цветами). В этом случае канонический код включает в себя цветовые идентификаторы.
Канонические коды графов позволяют избавиться от дорогостоящей процедуры проверки изоморфизма (graph isomorphism), и определять совпадение графов по сравнению строк.
Например, как найти дубликаты в множестве N графов? Вычислить N канонических кодов, отсортировать их и последовательно сравнить. Гораздо выгоднее, чем делать N*(N-1)/2 проверок изоморфизма. Можно сказать, что канонический код — это хеш-код без промахов.
Канонический код может выглядеть по-разному: как матрица смежности, развёрнутая в строку, или как маршрут обхода графа в ширину, или в глубину. Какое представление выбрать, не столь важно. Задача в любом случае сводится к вычислению канонической нумерации вершин (canonical numbering, canonical labeling). Каноническая нумерация — это нумерация (перестановка) вершин графа, гарантирующая, что изоморфные графы будут пронумерованы одинаково. Получив нужную перестановку, уже не составит труда построить канонический код, например, по обходу графа в глубину: начать обход с вершины под номером 1 и при ветвлении выбирать ту вершину, «канонический номер» которой меньше.
Наличие полиномиального алгоритма для задачи канонической нумерации означало бы, что задача изоморфизма графов полиномиально разрешима. На данный момент, для задачи изоморфизма графов полиномиального алгоритма не найдено, но и не доказана NP-полнота (в отличие от известной задачи изоморфизма подграфу, subgraph isomorphism). По некоторым признакам можно предполагать, что она не является NP-полной.
В ряде частных случаев существуют полиномиальные алгоритмы проверки изоморфизма и канонической нумерации. Мы рассмотрим простейший случай: когда граф является деревом.
В книге Ахо, Хопкрофта и Ульмана «Построение и анализ вычислительных алгоритмов» приводится алгоритм для определения изоморфизма двух деревьев (tree isomorphism), работающий за линейное время от количества вершин. На его основе нетрудно составить алгоритм канонической нумерации вершин дерева, работающий за то же линейное время.
Этап 1. Выделение корня
Отрубим от дерева все листья. Получится дерево меньшего размера. Будем повторять процедуру до тех пор, пока не останется одна вершина (center) или две вершины, соединённых ребром (bicenter).
Если осталась одна вершина, мы делаем её корнем и располагаем остальные вершины по уровням, считая от корня:
Если осталось ребро, мы располагаем остальные вершины по уровням, считая от этого ребра, обе вершины которого помещаются на первый уровень:
Мы разделили N вершин на K уровней так, что у каждой вершины на уровне k>1 есть «родитель» из уровня k-1. Вспомним ещё, что вершины и рёбра снабжены цветами. В наших обозначениях вершины будут красные и синие, а рёбра — чёрные и зелёные.
Этап 2. Поуровневая сортировка
Для алгоритма нужно задать условный порядок на цветах. Пусть красный цвет будет старше синего, а зелёный старше чёрного. Введём обобщённый код вершины, состоящий из цветового кода ребра, которое соединяет её с родителем, и из цветового кода самой вершины. Сгруппируем вершины нижнего уровня, имеющие одинаковый обобщённый код, и присвоим каждой группе ранг, соответствующий старшинству цветов. Цвет ребра имеет больший приоритет, чем цвет вершины. Ранг 0 считается самым старшим:
Составим обобщённые коды родителей этих вершин, которые расположены на предыдущем уровне. Кроме цветовых кодов ребра к родителю и самой вершины, включим в обобщённый код отсортированный список рангов её детей. Ранги детей имеют меньший приоритет, чем цветовые коды вершины и ребра:
Повторяем описанную процедуру:
и ещё раз:
Пока не дойдём до уровня 1. В нашем случае на первом уровне одна вершина, поэтому её ранг нулевой, в случае двух вершин на первом уровне нужно сравнить их обобщённые коды и присвоить им ранги 0 и 1 (или 0 и 0).
Этап 3. Нумерация
Начиная с уровня 1, присваиваем вершинам возрастающие номера в порядке возрастания их рангов. В случае совпадения рангов на уровне порядок присваивания номеров может быть любым, т.к. вершины с одинаковым рангом в некотором смысле идентичны. (Выражаясь математически, эти вершины лежат на одной орбите, т.е. существует автоморфизм графа, переводящий одну вершину в другую.)
Построение канонического кода
Как было сказано, строить канонический код можно многими способами. Приведём пример канонического кода, построенного при обходе дерева в глубину:
Для построения такого кода не нужен даже третий этап предыдущего алгоритма (нумерация). Мы начинаем обход с корня и для каждой посещённой вершины обходим её детей в порядке старшинства. Для определения старшинства детей хватит «внутриуровневых» кодов, полученных на этапе 2.
Анализ сложности
Этап 1, очевидно, требует O(N) операций. Нетрудно также понять, что на этапе 2 мы, двигаясь от последнего уровня к первому, проходим все вершины по одному разу. Затруднения может вызвать только процесс «ранжирования» вершин на уровне, но при использовании поразрядной сортировки он занимает время, пропорциональное количеству вершин, и суммарно по уровням получается тоже O(N) операций. Этап 3 и построение самого кода также занимают линейное время.
Каноническая нумерация в общем случае
Австралийский профессор Brendan McKay написал библиотеку на C под названием nauty. Она предназначена для поиска групп автоморфизмов произвольных графов; одним из её «побочных» результатов является каноническая нумерация вершин.
Nauty работает очень быстро. Цвета рёбер она не поддерживает, но при необходимости всегда можно добавить в граф псевдо-вершины таким образом, что каноническая нумерация получившегося графа без учёта цветов рёбер будет являться канонической для исходного графа.
понедельник, 14 января 2008 г.
Из архивов
Сэр Чарльз Энтони Ричард Хоар 2 года (1958-1960) учился в аспирантуре МГУ у академика А. Н. Колмогорова. Он вынужден был покинуть СССР после того, как советская ракета сбила самолёт-разведчик U-2.
Дональд Эрвин Кнут изучал русский в университете, и вместе с сокурсниками убедил преподавателя включить книгу академика А. П. Ершова «Программирование для БЭСМ» 1958-го года в практику чтения научных текстов.
Джон МакКарти в молодости изучил русский и переводил с русского научные тексты по дифференциальным уравнениям. Он познакомился с Ершовым в 1958 году в Англии, а в 1965 году посетил его в Новосибирске. Он оказался первым западным визитером, которому было позволено приехать после инцидента 1960 года. И МакКарти, и Хоар приезжали потом неоднократно.
Ершов однажды попросил Хоара перевести на английский биографический очерк о Дейкстре.
Кнут живо участвовал в подготовке перевода своей книги в СССР, в частности, присылал Ершову для русского издания поправки, не вошедшие в первое издание на английском.
Летом 1979 года Кнут прилетел на симпозиум в Ургенч (Узбекистан), на котором силами его и Ершова были собраны все светила теоретической информатики. Ершов в программу симпозиума включил «five o’clock», малознакомый Кнуту британский термин :)
Бруно Бухбергер неплохо говорит по-русски; он провёл год (1970-1971) в Объединённом Институте Ядерных Исследований в Дубне.
Подписаться на:
Сообщения (Atom)
