河内塔BackTracking bad_alloc

Question

我当时正在阅读this post，我试图在这个版本的河内塔上实现一个回溯算法，使用文章第一部分中定义的状态。基本上，它适用于相对较小的数字，但在某些情况下，程序会出现以下错误：

terminate called after throwing an instance of std::bad_alloc what(): bad_alloc This application has requested the Runtime to terminate it in an unusual way. Please contact the application's support team for more information. Process returned 3 (0x3)

我的注意力是为n = 7，m = 8做的。

我在这里张贴整个代码，因为它是一个小代码。

#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<int> get_initial_state(int n, int m)
{
    vector<int> state(m+1, 1);
    state[0] = n;
    return state;
}

bool is_final_sate(vector<int> state, vector<int> fin_state)
{
    if (state == fin_state)
        return true;
    return false;
}

int get_first_index_vector(vector<int> state, int val)
{
    for (int i = 1; i < state.size() ; ++ i)
        if (state[i] == val)
            return i;
    return state.size();
}

bool is_valid_transition(vector<int> state, int n, int m, int i, int j)
{
    if (i > n || j > n)
        return false;

    int pos_i = get_first_index_vector(state, i);
    if (pos_i == state.size())
        return false;

    int pos_j = get_first_index_vector(state, j);
    if (pos_i > pos_j)
        return false;

    return true;
}

vector<int> get_transition_state(vector<int> state, int n, int m, int i, int j)
{
    if (is_valid_transition(state, n, m, i, j))
    {
        int first = get_first_index_vector(state, i);
        if (first < state.size())
            state[first] = j;
    }
    return state;
}

bool backtrack_solver(vector<int> state, int n, int m, vector<int> fin_state, map<vector<int>, bool > visited, int length_sol)
{
    if (is_final_sate(state, fin_state))
    {
        cout << length_sol;
        return false;
    }

    /* in each state I try to move a disk from
     i-th rod to j-th rod */
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
        {
            if(i != j)
            {
                vector<int> new_state = get_transition_state(state, n, m, i, j);
                if (visited.find(new_state) == visited.cend())
                {
                    visited.insert(make_pair(new_state, 1));
                    if (!backtrack_solver(new_state, n, m, fin_state, visited, length_sol +1))
                        return false;
                }
            }
        }
    return true;
}

主要应该是这样的：

int main()
{
    int n = 7, m = 8;
    map<vector<int>, bool> visited;
    visited.insert(make_pair(get_initial_state(n,m), 1));
    vector<int> fin_state(m+1, n);
    backtrack_solver(get_initial_state(n,m), n, m, fin_state, visited, 0);
    return 0;
}

我一直在尝试的是:在开始时，我认为这是关于大量的递归调用，所以我在IDE中设置了堆栈大小(CodeBlocks 16.01)，但没有进行任何改进。然后，我不知道，我还是不知道如何解决它。

Answer 1

bad_alloc表示无法分配资源，因为可用内存不足。您的代码存在的一个主要问题是，您正在按值传递向量。这意味着每次都要把它们作为一个参数来传递。如果在递归中发生这种情况，那么内存分配就会很容易崩溃。请传递向量作为参考。例如：

bool is_valid_transition(vector<int> &state, int n, int m, int i, int j)