В чем разница между отслеживанием с возвратом и переходом и связыванием

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

Алгоритм - это методическая последовательность шагов для решения конкретной проблемы. Существуют различные алгоритмы, два из которых - с возвратом и переходом и связыванием.

Отслеживание с возвратом, ветвление и привязка

Что такое возврат

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

Все решения для поиска с возвратом должны удовлетворять сложному набору явных и неявных ограничений. Явное ограничение ограничивает выбор каждого элемента вектора из данного набора. Более того, неявное ограничение находит в пространстве решений кортежи, которые могут удовлетворять целевой функции.

Что такое Branch and Bound

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

Далее, чтобы решить проблему, этот метод делит данную подзадачу как минимум на две новые ограниченные подзадачи.

Разница между отслеживанием с возвратом и ветвлением и связыванием

Определение

Отслеживание с возвратом - это алгоритм для поиска всех решений некоторых вычислительных проблем, в частности проблем удовлетворения ограничений, который постепенно создает кандидатов для решений. Branch and bound - алгоритм для задач дискретной и комбинаторной оптимизации и математической оптимизации. Таким образом, это основное различие между отслеживанием с возвратом и переходом и связыванием.

Процесс

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

Эффективность

Заключение

Отслеживание с возвратом - это алгоритм для захвата некоторых или всех решений заданных вычислительных проблем, особенно для проблем удовлетворения ограничений. С другой стороны, Branch and Bound - это алгоритм для поиска оптимальных решений многих задач оптимизации, особенно в дискретной и комбинаторной оптимизации. В этом основное различие между Backtracking и Branch and Bound.

Ссылка:

1. «Методы разработки алгоритмов DAA - Javatpoint». Www.javatpoint.com, доступен здесь 2. «Введение в поиск с возвратом - Javatpoint». Www.javatpoint.com, доступно здесь 3. «Возврат». Википедия, Фонд Викимедиа, 7 декабря 2018 г., доступно здесь 4. «Ветвь и граница». Википедия, Фонд Викимедиа, 8 октября 2018 г., доступно здесь 5. «Что такое возврат? - Определение из Техопедии ». Techopedia.com, доступен здесь.