Метод поиска в ширину. Привести пример примененияРассмотрим задачу поиска всех простых цепей (маршрутов) из вершины х 1 в вершину x 4 в графе G (X, U). Начиная с вершины х 1, будем включать в маршруты ребра в порядке возрастания их номеров. Вершина дерева решений с номером 1 соответствует включению в маршрут ребра u 1, вершины c номерами 2 и 3 – ребер u 3 и u 6. Переход на следующий уровень дерева решений выполняется только после того, как были получены все подмножества текущего уровня. Таким образом на первом шаге (на 2-ом уровне дерева решений) множество М разбивается на три непересекающихся подмножества вариантов, одно из которых М 1, соответствующее вершине 1 дерева решений, порождает следующие три варианта простых цепей графа G: – { u 1, u 2, u 5}, – { u 1, u 4, u 7}, – { u 1, u 8, u 9}. Далее формируются вершины следующего третьего и т. д. уровней. Процесс заканчивается после получения всех вариантов решения. Описанный процесс реализует декомпозицию множества вариантов решения по методу в ширину с последовательным формированием состава вариантов и позволяет реализовать поиск решения полным перебором.
Данный метод осуществляет полный перебор и гарантирует нахождение точного решения.
|
