Ответ 1

Откат

• Он используется для поиска всех возможных решений, доступных для решения проблемы.
• Он перемещает дерево пространства состояний с помощью метода DFS (Depth First Search).
• Он понимает, что сделал плохой выбор и отменил последний выбор, выполнив резервное копирование.
• Он ищет дерево состояний, пока не найдет решение.
• Он включает функцию выполнимости.

ветвей и граница

• Он используется для решения проблемы оптимизации.
• Он может пересекать дерево любым способом, DFS или BFS.
• Он понимает, что он уже имеет лучшее оптимальное решение, которое пре-решение приводит к тому, что оно отказывается от этого предварительного решения.
• Он полностью ищет дерево состояний, чтобы получить оптимальное решение.
• Он включает ограничительную функцию.

Ответ 2

Откат

• Backtracking - это общий алгоритм поиска всех (или некоторых) решений некоторых вычислительных задач, в частности ограничение проблем удовлетворенности, который постепенно создает кандидатов в решениях и отказывается от каждого частичного кандидата c ( "backtracks" "), как только он определит, что c не может быть завершено до действительного решения.
• Он перечисляет набор частичных кандидатов, которые в принципе могут быть выполнены различными способами, чтобы дать все возможные решения данной проблемы. Завершение выполняется постепенно, путем последовательности шагов расширения кандидата.
• Концептуально, частичные кандидаты представлены в виде узлов дерева дерева, потенциального дерева поиска. Каждый частичный кандидат является родителем кандидатов, которые отличаются от него одним шагом расширения, а листья дерева являются частичными кандидатами, которые не могут быть расширены дальше.
• Он пересекает это дерево поиска рекурсивно, от корня вниз, в глубине-первом порядке (DFS). Он понимает, что сделал плохой выбор и отменил последний выбор, выполнив резервное копирование.
• Подробнее: Презентация Sanjiv Bhatia по Backtracking для UMSL.

Ветка и привязка

• A алгоритм с веткой и границей состоит из систематического перечисления возможных решений с помощью state space search: набор решений-кандидатов рассматривается как формирование корневое дерево с полным набором в корне.
• Алгоритм исследует ветки этого дерева, которые представляют собой подмножества набора решений. Прежде чем перечислять кандидатские решения ветки, ветвь проверяется на верхнюю и нижнюю оценочные оценки оптимального решения и отбрасывается, если она не может обеспечить лучшее решение, чем лучшее, найденное до сих пор алгоритмом.
• Он может пересекать дерево любым способом:
  • BFS (поиск первого дыхания) или (FIFO) ветвь и привязка
  • D-Поиск или (LIFO) Branch and Bound
  • Поиск по наименьшему количеству графов или (LC) и привязка
• Для получения дополнительной информации: презентация Sanjiv Bhatia по Backtracking для UMSL.