Полный перебор
При данном подходе должен выполняться полный перебор, перечисляя все возможные пути и выбирая путь(и) с самой низкой стоимостью. Любой метод, используемый, чтобы создать эти пути может быть иллюстрирован деревом решений.
Мы могли бы например выполнять полный перебор, используя алгоритм 'поиска в глубину', см. [CORM90] стр. 477 .. 483. Кратко: начнем 'трассировку' пути решения с листа в дереве решений, производящем первый путь. Затем мы создадим указатель возврата на первую точку решения, где мы еще не исследовали все возможные 'решения' и наченм новый перебор по дереву для нового пути. Чтобы ограничивать число путей для перебора, мы можем непосредственно отбрасывать любые пути, которые имели бы 'циклы'. Продолжайте по этому способу, пока все дерево пройдено. Другими словами, начните в исходной вершине, перейдите по граням к другим вершинам (которые еще не прошли), и повторяйте, пока вершина адресата не достигнута.В каждой точке решения, мы имеем выбор из восьми направлений. Назовем число вершин N. Поскольку любая ячейка может быть посещена больше, чем один раз (иначе имелся бы цикл), мы можем устанавливать, что каждый возможный путь имеет в большинстве случаев N-1 граней, то есть дерево поиска имеет глубину O(N). Так как число ветвей восемь на каждом уровне, мы получаем в большинстве 8N -1 возможных путей, то есть мы имеем O(8N) путей, чтобы исследовать в самом плохом случае. Таким образом, этот подход берет экспоненциальное время, чтобы найти решение. Это ясно не очень хорошо. Алгоритм очень плохой так как не различает между огромным большинством возможных путей, которые, вряд ли, будут оптимальны и те очень немногие, которые являются вероятными кандидатами.
7.1.2