Блог

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

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), но никаких улучшений. Тогда, я не знаю, я все еще не понимаю, как это решить.

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

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