Это не важно!
Нас интересует, какие у нас есть достопримечательности (наши вершины) и какие из них соединены друг с другом линиями метро (наши ребра). Другие особенности этих мест нас не интересуют, поэтому мы их игнорируем. Мы опускаем их точное расположение, расстояние друг от друга, соединения автодорог и многие другие вещи, которые не относятся к нашей задаче — понять, как объехать все это на метро. Граф — это абстракция реального города. Мы спрятали все лишние детали, не нужные для построения графа. Здесь отражена только важная информация. Поэтому нам легко увидеть действительно необходимое для решения. Это хорошее представление текущей задачи.
Упрощаем
Графы часто используются, чтобы представить информацию о связях между объектами. Это маршруты на автобусных остановках, карты поездов и метро. Граф — очень хорошее представление в ситуации, когда нужно проложить маршрут из одного места в другое, как в нашем случае. Упрощенный граф облегчает составление маршрута по сравнению с максимально точной картой, где трудно выделить нужную информацию среди многочисленных подробностей.
Циклы
В информатике есть особое название для обхода графа, когда вы посещаете каждую вершину ровно один раз и возвращаетесь в начало. Это называется гамильтонов цикл — по имени ирландского физика Уильяма Роуэна Гамильтона. Он изобрел головоломку, по условиям которой нужно было обойти все углы додекаэдра, проходя по его граням.
Одно решение на двоих
Возвращаемся к началу
Возможно, вы уже заметили, что головоломка «Ход конем» и задача экскурсовода очень похожи друг на друга. Если вы записали требования для «Хода конем», то, вероятно, увидели полное совпадение.
1. Тур начинается в заданной точке.
2. Необходимо посетить все точки.
3. Нельзя проходить уже посещенную точку.
4. Необходимо закончить в начальной точке.
В обоих задачах вас просят найти гамильтонов цикл! Таким образом, мы использовали прием из вычислительного мышления. Мы обобщили обе задачи, чтобы они стали одинаковыми, и сделали это с помощью сопоставления с образцом, увидев важнейшие сходные черты. При этом мы абстрагировались от деталей, таких как отели и туристические достопримечательности или необходимость ходить конем или ехать по линиям метро.
Итак, задача экскурсовода оказалась легкой, потому что мы представили ее в виде графа. Так почему бы нам не сделать то же самое и с задачей «Ход конем»?
Для этого нужно абстрагироваться в большей степени. Чтобы это сделать, необходимо осознать две вещи. Во-первых, не важно, как выглядит доска. Не важно, что поля — это квадраты. Их форма и размер могли бы быть абсолютно любыми. Давайте нарисуем каждое поле в виде кружочка — так же, как достопримечательности изображены на карте метро. Это просто вершины графа.
Во-вторых, какие поля на самом деле находятся рядом друг с другом — тоже не очень важно. Единственное, что имеет значение, — между какими полями конь перемещается. Поэтому давайте соединим линиями любые два кружка, между которыми можно сделать ход. Подобным образом карта метро показывает, между какими достопримечательностями можно переместиться на метро. Это ребра графа.
Создаем граф
Чтобы сделать граф для головоломки «Ход конем», переходите с поля на поле и по мере продвижения рисуйте кружки и линии (вершины и ребра). Если четко выстроить путь, вы ничего не пропустите. Начните с поля 1. Нарисуйте кружок и пометьте его цифрой «1». Теперь с поля 1 можно перейти на поле 9 — значит нужно нарисовать еще один кружок, обозначить его как «9» и соединить их линиями. С поля 9 перейдите на поле 3 и нарисуйте еще один кружок, который пометьте «3» и соедините его линией с кружком 9.
Продолжайте так делать, пока не вернетесь к уже нарисованному кружку. Теперь отойдите на ход назад и попробуйте из этой точки пойти другой дорогой. Если других вариантов, которые вы еще не обозначили, больше нет, вернитесь еще на один ход и попробуйте оттуда. Продолжайте делать так до тех пор, пока не проведете эту операцию (она называется поиск с возвращением) до поля 1 и у вас не кончатся варианты. В итоге вы получите схему.
Заметим, что из трех внутренних кружков возможны только два хода, а значит, на завершенной схеме на каждую из этих вершин придется по два ребра (линии). С других полей можно сделать три разных хода, поэтому у их вершин будет по три ребра.
Идем вглубь
Способ исследования всех возможных ходов с целью нарисовать граф называется поиском в глубину: мы исследуем пути до самого конца, например продвигаясь через 1 — 9 — 3 — 11... до конца, потом сохраняем этот путь и пробуем другие. Альтернативный вариант (под названием поиск в ширину) подразумевает рисование всех ребер, исходящих из вершины, и всех вершин, к которым они ведут, перед перемещением к новой вершине. Используя этот метод, мы могли бы нарисовать все ребра из вершины 9, потом все ребра из вершины 6 — и так далее. Это два разных алгоритма для исчерпывающего исследования графа — два разных алгоритма обхода графа. Как только вы осознаете, что задачу можно представить в виде графа, то используйте любой из этих алгоритмов в качестве упорядоченного способа исследования графа и, соответственно, задачи.
Чистота и порядок
Если ваш рисунок получился немного беспорядочным из-за наезжающих друг на друга линий, как показано на рис. 34, можно перерисовать его начисто, чтобы линии не пересекались. В этом случае используйте два связанных шестиугольника — один внутри другого, как на рис. 35.
Когда вы аккуратно начертите граф, попробуйте снова решить задачу «Ход конем». Начните с вершины 1 и следуйте линиям, отмечая вершины, которые проходите. Теперь найти решение должно быть довольно легко.
Одна задача, одно решение
Теперь внимательно посмотрите на чистый вариант графа. Мы перечертили его, не меняя ребер и вершин, и он выглядит в точности как схема метро. Единственная разница — в обозначениях вершин. Цифры вместо названий.
Теперь видно, что эти задачи можно обобщить и что они не просто похожи, но в точности одинаковы. Если у вас есть решение для одной задачи (алгоритм, позволяющий найти ответ), значит, есть и для другой! Все, что нужно сделать, — поменять обозначения. Обобщенная версия алгоритма подойдет для обеих головоломок, и ничего не придется делать заново.
Сопоставление схем
На рис. 36 показано, как поменять обозначения на графе одной из наших задач, чтобы он подошел для другой. Еще на нем видно, как перевести решение одной задачи в решение другой. Обозначение каждого шага в алгоритме для одной из задач нужно заменить на соответствующее в другой.
