ЗДОРОВЬЕ ТЕЛА И ДУШИ

Продолжим решать задачи. Вашему вниманию предлагается новая алгоритмическая задача. Кратчайший путь.

Профессор. Пусть из пункта А в пункт В можно добраться различными путями по дорогам с перекрестками, на которых установлены стрелочные указатели расстояний до следующего перекрестка. Как, начиная движение из пункта А, дойти до пункта В кратчайшим путем?

Самый простой по своей идее алгоритм решения этой задачи основывается на методе прямого перебора всех возможных путей достижения пункта В из пункта А и выбора из них наименьшего по своей протяженности. Однако количество всех путей может оказаться слиш­ком огромным, чтобы их перебор был практически осу­ществим.

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

Итак, рассмотренный алгоритм лишь стремится сократить весь маршрут, но не гарантирует его минимальной протяженности. Зато он не требует полного перебора всех возможных путей, а, следовательно, работает быстрее. Впро­чем, я должен заметить, что существуют эффективные алгоритмы поиска кратчайших маршрутов, основанные не на полном переборе. Наиболее из­вестным из них является алгоритм Дейкстры, но сейчас мы не будем его рас­сматривать.

Простак. Мне кажется, что простой алгоритм, который лишь стремится сократить маршрут, не гарантируя при этом наилучшего ре­зультата, можно усовершенствовать. Так, прежде чем окончательно выбрать направление движения на данном перекрестке, можно сначала проверить все направления из него. Иначе говоря, следует сбегать на все смежные перекре­стки, чтобы по указателям на них узнать расстояния до следующих перекре­стков. Получив эту информацию и вернувшись на исходный перекресток, можно принять решение о движении с учетом протяженности не одного, а двух переходов. Разумеется, эта стратегия потребует больше времени, но зато конечный результат будет лучше.

3 а н у д а. Аналогично, можно заглянуть не только на непосредственно смежные, но и на последующие перекрестки. Если продолжить эту аналогию, то мы придем в конце концов к полному перебору всех маршрутов и выбору самого короткого из них.

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

Алгоритмические задачи могут  быть разными. А вам интересны логические задачи? Например, эта задача? До новых встреч!

Статья подготовлена по материалам книги Вадима Дунаева «Занимательная математика. Множества и отношения».