Поиск с возвратом — это рекурсивный метод, использующий грубую силу для постепенного поиска и построения наилучшего или желаемого решения.
Если частичное решение не удается, выполняется возврат к предыдущему частичному решению и повторная попытка с новым решением.
Одним из известных примеров является «лучший маршрут полета», учитывая список рейсов и отправную точку, постройте маршрут. Если существует несколько маршрутов, укажите первый в алфавитном порядке.
Давайте углубимся в код:
Давайте вызовем вспомогательный метод, но сначала мы определим лучший маршрут и текущие переменные маршрута.
Во-первых, мы проверяем, не пуст ли список рейсов и есть ли соединение (в противном случае мы мало что можем сделать).
Затем для каждого рейса в списке рейсов, если место отправления не совпадает с местом стыковки, это будет неудачный маршрут; нам нужно вернуться, и это частичное решение не работает.
Для текущего рейса, соответствующего месту отправления, есть два варианта; есть еще рейсы для проверки, затем мы добавляем пункт назначения рейса к текущему маршруту и рекурсивно вызываем список рейсов, но удаляем текущий рейс.
Если это был последний рейс в списке, нам нужно сравнить лучший маршрут; если лучшего маршрута нет, то выбираем текущий маршрут как лучший маршрут; в противном случае мы выбираем кратчайший маршрут между существующим лучшим маршрутом и текущим маршрутом.
Давайте используем следующее расширение, чтобы определить меньший маршрут.
Вот пример использования этой функции:
Поскольку метод поиска с возвратом использует подход грубой силы, вам может потребоваться попробовать все возможные комбинации; это неэффективный алгоритм.В худшем случае, в зависимости от требований алгоритма, это может привести к O(n!), O(2^n) или даже O(n^n) для пространства и временная сложность.
‹‹ Два указателя против скользящего окна | Книга | Вскоре…
