Читать «Вычислительное мышление: Метод решения сложных задач» онлайн - страница 41

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

Идем вглубь

Способ исследования всех возможных ходов с целью нарисовать граф называется мы исследуем пути до самого конца, например продвигаясь через 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.