В 2 понятия связаны между собой (иногда можно даже комбинировать их), но вы должны просто сосредоточиться на основных различиях между ними, как их имена предполагают:
ветвей и границ исследует пространство поиска исчерпывающе разветвление переменных (= проверить значения переменных). Это создает несколько подзадач, например. ветвление на двоичной переменной создает проблему, в которой переменная = 0 и проблема, в которой она равна 1. Затем вы можете продолжить и рекурсивно решить их. «Ограничивающий» аспект техники состоит в оценке оценок решений, которые могут быть достигнуты в подзадаче. Если подзадача может дать только плохие решения (по сравнению с ранее найденным решением), вы можете спокойно пропустить исследование этой части пространства поиска.
Лучшее в первую очередь пытается найти решение как можно быстрее, если посмотреть на самую интересную часть поискового пространства в первую очередь (самое интересное = оценка). Он не разбивает пространство поиска, а пытается как можно быстрее достичь решения /.
Оба подхода пытаются пропустить исследование частей поискового пространства. Их использование и эффективность зависят от настройки проблемы. В первую очередь вам нужно указать критерий «наиболее интересное решение для изучения», которое иногда может быть затруднительным/невозможным. Ветвь и граница интересны только в том случае, если оценка, которую вы можете поставить на подзадачи, имеет смысл/не слишком широка. Это зависит от проблемы, которую вы рассматриваете ...
Что я понял, так это: поиск в первом порядке учитывает только стоимость достижения состояния (т. Е. Сумму затрат от корневого состояния до этого состояния) для ранжирования , но BB использует оценочную минимальную стоимость наличия полных решений через это состояние. Я прав? – Barpa
Нет, Best First пытается выбрать следующий узел для обработки, используя глобальную смету затрат, а не только текущую стоимость. Рассмотрим проблему с навигацией, для которой вы можете использовать Dijkstra для создания кратчайших путей. Только просмотр стоимости достижения текущего состояния - это именно то, что делает Дейкстра, выбирая узел с самым низким предварительным расстоянием до следующего. Применяя Best First к нему, вы получаете A *, так как в A * вы всегда выбираете узел с самой низкой общей стоимостью. – Origin
Извините, но теперь я больше смущен. Вы говорите, что лучше всего сначала выберите следующий узел, используя глобальную смету. Разве глобальная оценка стоимости не совпадает с глобальными (нижними или верхними) ветвями и связанными применениями для сравнения с текущим состоянием? – Barpa