Next:4.4
Алгоритм поиска с возвращением
Up:4
Разработка алгоритмов
Previous:4.2
Язык описания алгоритмов
,
в качестве множества всех возможных решений можно взять множество всех
целых чисел от 1 до ,
а при нахождении пути через лабиринт множеством всех возможных решений
может служить множество всех путей, начинающихся входом в лабиринт.
Рис. 19. Лабиринт (целью пути является черный квадрат; стрелками обозначены
возможные продолжения текущего пути)
Общим методом организации исчерпывающего поиска является так называемый поиск с возвращениям или возвратный ход по упорядоченному множеству частичных возможных решений. Понятие частичное возможное решение, с помощью которого формулируется алгоритм поиска с возвращением, мы иллюстрируем ниже в примере решения задачи поиска выхода из лабиринта. Заметим здесь, что каждое частичное решение фиксирует определенное подмножество возможных (полных) решений, не противоречащих данному частичному решению, т.е. являющихся его расширениями. Этот метод -- метод поиска с возвращением -- основан на том, что мы многократно пытаемся расширить текущее частичное решение, или, что то же самое, сузить множество тех возможных полных решений, которые не противоречат текущему частичному решению. Если расширение невозможно на текущем шаге поиска, то происходит возврат к предыдущему более короткому частичному решению и делается попытка его расширения, но уже другим способом.
Идею поиска с возвращением можно продемонстрировать на примере решения задачи поиска выхода из лабиринта, в которой требуется попасть из входного квадрата в некоторый заданный квадрат (рис. 19) путем последовательного перемещения по соединенным смежным квадратам. Поиск с возвращением осуществляет движение по лабиринту в соответствии со следующими двумя правилами:
1) продвижение: из текущего квадрата нужно переходить в еще не исследованный соседний квадрат,
2) возврат: если все соседние квадраты уже исследованы, то нужно вернуться на один квадрат назад по пройденному пути.
Первое правило говорит о том, как расширить исследуемый путь, если это
возможно, а второе -- о том, как выходить из тупика. Заметим, что каждый
исследуемый путь определяет множество всех тех возможных путей по лабиринту,
начальным отрезком которых он является, и, таким образом, удлинение исследуемого
пути сужает связанное с ним множество возможных путей по лабиринту, а сокращение
расширяет это множество. В этом и состоит сущность поиска с возвращением:
продолжать расширение найденного частичного решения до тех пор, пока это
возможно, и, когда текущее частичное решение нельзя расширить, возвращаться
по нему и пытаться сделать другой выбор по расширению частичного решения
на самом близком шаге, где имеется такая
возможность.
Next:4.4
Алгоритм поиска с возвращением
Up:4
Разработка алгоритмов
Previous:4.2
Язык описания алгоритмов