Блог

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

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

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

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

 void Tree::insert(string amp;initialState, const string amp;goalState, tree_node *amp;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 amp;amp; zeroPos!=3 amp;amp; 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);
            }
        }
    }

    }
 }
}
  

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

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