Итак, если мы нашли следующее решение для задачи экскурсовода:
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 веке. Нарисуйте граф для задачи и посмотрите, сможете ли решить ее, прежде чем читать дальше.
Мыслим логически
Вычислительное мышление подразумевает умение мыслить логически. Хорошее представление информации помогает в этом, потому что позволяет убрать ненужное и сосредоточиться на главном. Именно это и обнаружил Леонард Эйлер, когда решал задачу «Мосты Кенигсберга» и пришел к мысли нарисовать граф (рис. 39). Граф помог ему увидеть задачу предельно ясно.
Глядя на граф, Эйлер осознал, что найти ответ невозможно. Почему? Подходящий маршрут должен затронуть все вершины и обойти все ребра, но только один раз (поскольку ребра — это мосты, а нам сказали, что по каждому мосту можно пройти один раз). Давайте предположим, что такой маршрут существует, и, чтобы его показать, нарисуем пунктирные линии со стрелками вдоль ребер. Все ребра должны входить в маршрут, а значит, все они должны совпасть с пунктирными стрелками. Возьмем вершину на этом маршруте, как показано на рис. 40. На каждую пунктирную стрелку, направленную от нее, должна приходиться пунктирная стрелка, направленная к ней. В противном случае маршрут зайдет в тупик — когда пойдет по лишнему ребру, над которым не будет пунктирной стрелки. Из этого тупика не получится выйти без возвращения на уже пересеченный мост. То же относится и к любой вершине. Поэтому, чтобы искомый маршрут был возможен, у всех вершин должно быть четное число связанных с ними ребер.
Все вершины на графе Кенигсберга имеют нечетное число ребер, поэтому искомый маршрут невозможен. Однако со времен Эйлера через реку построили новый мост, поэтому граф изменился. Экскурсоводам современного Калининграда живется легче.
Собираемся и путешествуем
Настоящее путешествие
Мы рассмотрели простые головоломки с поиском маршрута. Теперь возьмем задачу из реальной жизни. Представьте, что специалист по продажам каждый день настраивает навигатор, чтобы найти самый короткий путь, позволяющий по одному разу посетить несколько клиентов в разных городах и снова оказаться в офисе, не возвращаясь по собственным следам.
Такую кратчайшую дорогу можно просчитать, но вряд ли получится каждый раз делать это за разумный промежуток времени. Даже если надо побывать у 20 клиентов, нельзя гарантировать, что вы ежедневно будете находить оптимальное решение — на это потребуется слишком много времени. И дело не в том, что требуется более мощный навигатор или компьютер. Если число мест, где необходимо побывать, достаточно велико (на самом деле оно не очень-то и велико), то на поиск совершенного решения уйдет больше времени, чем прошло с момента возникновения Вселенной, — даже при наличии самого быстрого компьютера! Почему? Потому что число возможных вариантов, которые необходимо проверить, стремительно растет с появлением каждого нового города. Даже если навигатор запрограммировать на какое-то решение, нельзя гарантировать, что оно будет безупречным. Заложенный в программу способ не обеспечит кратчайшего пути. Вполне вероятно, что в программе сработает так называемый жадный алгоритм. Давайте изменим условия задачи, чтобы понять, о чем идет речь.
