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

•    Состояния. Каждое состояние представлено местонахождением (например, аэропортом) и текущим временем.

•    Начальное состояние. Оно задается в условии задачи.

•    Функция определения преемника. Эта функция возвращает состояния, которые следуют из выполнения любого полета, указанного в расписании (возможно, с дополнительным указанием класса и места), отправления позже по сравнению с текущим временем с учетом продолжительности переезда внутри самого аэропорта, а также из одного аэропорта в другой.

•    Проверка цели. Находимся ли мы в месте назначения к некоторому заранее заданному времени?

•    Стоимость пути. Зависит от стоимости билета, времени ожидания, продолжительности полета, таможенных и иммиграционных процедур, комфортности места, времени суток, типа самолета, скидок для постоянных пассажиров и т.д.

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