Интересные ссылки

Алгоритмическая задача Кратчайший путь

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

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

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

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

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

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

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

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

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

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

6 комментариев: Алгоритмическая задача Кратчайший путь

  • В общем случае данная задача не имеет решения. Любой алгоритм, используемый при недостатке информации не позволит “из пункта А, дойти до пункта В кратчайшим путем”. Можно говорить только о кратчайшем пути для заданных условий. Это первый вариант условий задачи.
    Обычно в транспортной задаче бывает известна топология сети дорог и расстояния между перекрестками. Это второй вариант условий задачи. Упомянутый в статье алгоритм Дейкстры решает именно такую задачу. В нем нет перебора всех возможных путей, но выполняется перебор всех перекрестков. Я предложил свой алгоритм, который не требует перебора всех перекрестков.

  • Геннадий говорит:

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

  • По-моему, условие задачи недостаточно конкретно.
    1. Если известно только название конечного пункта, а расстояния мы узнаем лишь дойдя до перекрестка, то на каждом перекрестке выбор пути к ближайшему перекрестку, на котором мы еще не были, будет оправданным. Если на всех ближних перекрестках мы уже побывали, идем к тому, где больше неисследованных дорог. Хотя наш путь будет напоминать траекторию движения ежика в тумане, рано или поздно мы придем, куда нужно. С большой степенью вероятности путь будет близким к оптимальному для заданных условий.
    2. Если все расстояния известны заранее, то строим таблицу расстояний. Столбцы и строки означают перекрестки, а в пересечениях их ставим расстояния между соответствующими перекрестками. Затем для начального пункта вычисляем и проставляем расстояния до перекрестков, следующих за соседними, обязательно записывая путь к этому перекрестку. Потом аналогично вычисляем пути до третьего перекрестка. Если существует несколько таких путей, в таблице остается тот, который короче. Точно такие же операции выполняем для конечного пункта. Как только будет рассчитаны расстояния до какого-либо перекрестка как от конечного, так и от начального пункта, задача решена. Решение будет оптимальным. Для большого числа перекрестков задачу решаем, разработав компьютерную программу. А для малого можно обойтись таблицей на бумаге, причем таблица делится по диагонали от верхнего левого угла к правому нижнему. В одной половине таблицы можно считать расстояния от начального (первого в таблице) пункта, а в другой половине – для конечного (последнего в таблице)
    3. Если известны координаты начальной и конечной точек, тогда более разумным, на мой взгляд будет выбор такого пути, направление которого ближе к направлению на конечный пункт при условии, что этот путь ведет к перекрестку, на котором мы еще не были.

    • admin говорит:

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

  • Людмила говорит:

    Теперь все значительно проще, надо просто в телефон иметь навигатор.

    • admin говорит:

      Верно! Но если все функции перекладывать на аппараты и приборы, то кем станет сам человек?

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля отмечены *

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>