Питер Макоуэн - Вычислительное мышление: Метод решения сложных задач

Чтобы сделать граф для головоломки «Ход конем», переходите с поля на поле и по мере продвижения рисуйте кружки и линии (вершины и ребра). Если четко выстроить путь, вы ничего не пропустите. Начните с поля 1. Нарисуйте кружок и пометьте его цифрой «1». Теперь с поля 1 можно перейти на поле 9 — значит нужно нарисовать еще один кружок, обозначить его как «9» и соединить их линиями. С поля 9 перейдите на поле 3 и нарисуйте еще один кружок, который пометьте «3» и соедините его линией с кружком 9.

Продолжайте так делать, пока не вернетесь к уже нарисованному кружку. Теперь отойдите на ход назад и попробуйте из этой точки пойти другой дорогой. Если других вариантов, которые вы еще не обозначили, больше нет, вернитесь еще на один ход и попробуйте оттуда. Продолжайте делать так до тех пор, пока не проведете эту операцию (она называется поиск с возвращением) до поля 1 и у вас не кончатся варианты. В итоге вы получите схему.

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

Способ исследования всех возможных ходов с целью нарисовать граф называется поиском в глубину:мы исследуем пути до самого конца, например продвигаясь через 1 — 9 — 3 — 11... до конца, потом сохраняем этот путь и пробуем другие. Альтернативный вариант (под названием поиск в ширину) подразумевает рисование всех ребер, исходящих из вершины, и всех вершин, к которым они ведут, перед перемещением к новой вершине. Используя этот метод, мы могли бы нарисовать все ребра из вершины 9, потом все ребра из вершины 6 — и так далее. Это два разных алгоритма для исчерпывающего исследования графа — два разных алгоритма обхода графа.Как только вы осознаете, что задачу можно представитьв виде графа, то используйте любой из этих алгоритмов в качестве упорядоченного способа исследования графа и, соответственно, задачи.

Если ваш рисунок получился немного беспорядочным из-за наезжающих друг на друга линий, как показано на рис. 34, можно перерисовать его начисто, чтобы линии не пересекались. В этом случае используйте два связанных шестиугольника — один внутри другого, как на рис. 35.

Когда вы аккуратно начертите граф, попробуйте снова решить задачу «Ход конем». Начните с вершины 1 и следуйте линиям, отмечая вершины, которые проходите. Теперь найти решение должно быть довольно легко.

Теперь внимательно посмотрите на чистый вариант графа. Мы перечертили его, не меняя ребер и вершин, и он выглядит в точности как схема метро. Единственная разница — в обозначениях вершин. Цифры вместо названий.

Теперь видно, что эти задачи можно обобщитьи что они не просто похожи, но в точности одинаковы. Если у вас есть решение для одной задачи (алгоритм, позволяющий найти ответ), значит, есть и для другой! Все, что нужно сделать, — поменять обозначения. Обобщеннаяверсия алгоритма подойдет для обеих головоломок, и ничего не придется делать заново.

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

Итак, если мы нашли следующее решение для задачи экскурсовода:

1. Отель.

2. Научный музей.

3. Магазин игрушек

4. Колесо обозрения.

5. Парк.

6. Зоопарк.

7. Аквариум.

8. Художественный музей.

9. Музей восковых фигур.

10. Военный корабль.

11. Замок.

12. Собор.

13. Отель,

то, используя таблицу, сразу же найдем решение для «Хода конем»:

1. Поле 1.

2. Поле 9.

3. Поле 3.

4. Поле 11.

5. Поле 5.

6. Поле 7.

7. Поле 12.

8. Поле 4.

9. Поле 10.

10. Поле 2.

11. Поле 8.

12. Поле 6.

13. Поле 1.

Эта таблица — еще один вид представленияинформации или структуры данныхв виде таблицы поиска.С ее помощью вы легко найдете эквивалент поля из «Хода конем» в списке достопримечательностей из задачи для экскурсовода. Но стоит заметить, что искать поле, соответствующее достопримечательности, не очень удобно. Было бы гораздо лучше, если бы достопримечательности стояли в алфавитном порядке.

Схема на рис. 37 — еще одно представление той же информации, полученное методом наложения. Также она показывает единое решение (для обеих задач). Конечно, поскольку решений может быть много, вы можете прийти к какому-то другому, но и тогда оно подойдет для обеих задач.

Итак — вероятно, это удивит вас, — две разные вроде бы задачи оказались одинаковыми и с одним решением (после обобщения). Решив одну, вы сразу решили и другую! Это открытие происходит после выбора подходящих абстракцийи подходящего представлениядвух задач ( структура данныхв виде графа).

Вот еще одна головоломка, над которой стоит поразмыслить. На рис. 38 показана карта города с рекой, протекающей через него, двумя островами и семью мостами через реку.

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

Похожую задачу о мостах города Кенигсберга в XVIII веке решил математик Леонард Эйлер. В своем решении он впервые ввел идею графов. В итоге они стали одним из ключевых вычислительных инструментов как в математике, так и в информатике. Ученые Викторианской эпохи Чарльз Беббидж и Ада Лавлейс, написавшие первые компьютерные программы, попытались решить ее в XIX веке. Нарисуйте граф для задачи и посмотрите, сможете ли решить ее, прежде чем читать дальше.