В чем разница между FIFO Branch and Bound, LIFO Branch and Bound и LC Branch and Bound?

Branch & Bound обнаруживает ответвления в полном пространстве поиска, используя оценочные границы для ограничения числа возможных решений. Различные типы (FIFO, LIFO, LC) определяют разные «стратегии» для исследования пространства поиска и создания ветвей.

FIFO (первым пришел, первым вышел): для расширения ветви всегда используется самый старый узел в очереди. Это приводит к поиску в ширину, при котором сначала просматриваются все узлы на глубине d, прежде чем будут посещены какие-либо узлы на глубине d+1.

LIFO (последний вошел, первый вышел): всегда самый молодой узел в очереди используется для расширения ветви. Это приводит к поиску в глубину, где ветвь расширяется через каждого 1-го дочернего элемента, обнаруженного на определенной глубине, пока не будет достигнут конечный узел.

LC (наименьшая стоимость): ветвь расширяется узлом, который добавляет наименьшие дополнительные затраты в соответствии с заданной функцией стоимости. Таким образом, стратегия обхода пространства поиска определяется функцией стоимости.

Единственное отличие заключается в реализации живых узлов. В ветвях и границах LC первый узел, который мы начинаем исследовать, — это тот, который обещает нам лучшее решение в данный момент. Например, в задаче о рюкзаке 0/1, используя LC Branch and Bound, первым дочерним узлом, который мы начнем исследовать, будет тот, который предлагает максимальную стоимость из всех.

В ветвлении и привязке FIFO, как видно из названия, дочерние узлы исследуются в порядке «первым пришел — первым обслужен». Мы начинаем исследовать узлы, начиная с первого дочернего узла. В ветвях LIFO мы исследуем узлы с последнего. Последний дочерний узел должен быть изучен первым.