Как избежать переполнения стека в глубокой рекурсии дерева - PullRequest
Новая
       29

Как избежать переполнения стека в глубокой рекурсии дерева

0 голосов
/ 30 апреля 2011

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

Я кодирую функцию для заполнения дерева, каждый узел имеет четыре ветви, в которых будут храниться возможные манипуляции с состояниями «головоломки восьми плиток», т.е. http://www.8puzzle.com/images/8_puzzle_start_state_a.png

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

Хвостовая рекурсия кажется решением, хотя я не уверен, насколько она актуальна / возможна или как реализовать ее в этом случае. Код следует: 

void Tree::insert(string &initialState, const string &goalState, tree_node *&inNode){
cout<<"insert called"<<endl;
depth++;
cout<<depth<<endl;
string modState;
int zeroPos=0;

if(initialState==goalState){
    cout<<"*    *   *   GOAL    *   *   *"<<endl;
    getchar();
    exit(0);
}   

if(inNode==NULL){//is this the first node?

    inNode = new tree_node(initialState);       
    root=inNode;
    inNode->parent=NULL;
    insert(initialState, goalState, inNode);
}else{
    inNode->state = initialState;

    for(zeroPos=0;zeroPos<initialState.size();zeroPos++){//where is the empty tile?
        if(initialState[zeroPos]=='0'){
            break;
        }
    }
    //left
    if(zeroPos!=0 && zeroPos!=3 && zeroPos!=6){//can the empty tile move left?

        modState=initialState;
        modState[zeroPos]=modState[zeroPos-1];
        modState[zeroPos-1]='0';

        if(isOriginal(modState, inNode) ){//does this state already exist?

            cout <<"left  " << modState[0]<<modState[1]<<modState[2]<<endl;
            cout <<"left  " << modState[3]<<modState[4]<<modState[5]<<endl;
            cout <<"left  " << modState[6]<<modState[7]<<modState[8]<<endl;

            inNode->l = new tree_node(modState);    
            inNode->l->parent= inNode;
            if(inNode->l != NULL){
                insert(modState, goalState, inNode->l);
            }
        }
    }

    }
 }
}

Ответы [ 2 ]

2 голосов
/ 30 апреля 2011

Это очень общий ответ, но пытались ли вы явно управлять своим стеком через что-то вроде выделенной кучи очереди или стека? По сути, на самом деле не используйте вызовы функций, просто вставляйте и вытаскивайте вещи из своего собственного стека / очереди. Они охватывают нерекурсивные алгоритмы обхода графа здесь (поиск как по глубине, так и по ширине).

0 голосов
/ 30 апреля 2011

Оптимизируйте свой код, то есть оставляйте только те узлы, которые вам нужны.Например, оставляйте только листовые узлы (я имею в виду те, которые вы еще не расширили).И да, вы можете искать дерево при его создании, написать функцию для измерения расстояния между вашим текущим состоянием и вашим целевым состоянием, которая называется эвристической.Есть также лучший алгоритм, который решает 8puzzle, он называется A *, я предлагаю вам погуглить его.

...