Минимизация использования памяти при первом поиске

Question

В следующем коде я пересекаю график через breadth first search.Код строит граф во время его обхода.Это очень большой график, с веером из 12. Из-за этого, всякий раз, когда глубина breadth first search увеличивается, я хочу разрушить слой над ним, чтобы минимизировать использование памяти.Как я мог разработать алгоритм для этого?

string Node::bfs(Node * rootNode) {
QQueue<Cube *> q;
q.enqueue(rootNode);

while (!(q.empty())) {
    Node * currNode = q.dequeue();
    currNode->constructChildren();
    foreach (Node * child, currNode->getListOfChildren()) {
        q.enqueue(child);
    }
    if (currNode->isGoalNode()) {
        return currNode->path;
    }
}

Answer 1

При постоянном разветвлении и в предположении древовидного графа количество узлов, которые посетили BFS, почти равно числу узлов на границе.(например, в дереве с разветвлением K каждый уровень n имеет K ^ n узлов, а число узлов с меньшей глубиной, чем n, также является тэтой (K ^ n)).

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

Но если вы хотите уничтожить «посещенные» узлы, тогда какой-то способ отслеживания того, что былопосещенный (в случае общего графа; если это - это дерево, то проблем нет) необходимо разработать.В этом случае требуется больше информации на графике.

EDIT о том, почему итеративное углубление DFS лучше.

Край (не посещаемые узлы, которые должны быть смежными сколичество посещенных узлов) в BFS имеет размер O (K ^ n), где n - текущая глубина.Край для DFS имеет размер O (n).

Итеративное углубление DFS имеет тот же размер полосы, что и DFS, и дает тот же результат, что и BFS, потому что он "имитирует" BFS.

Answer 2

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