二维向量中的 C++ 回溯

Question

我目前正在尝试使用回溯来生成一个词在 2D 向量中可能具有的所有不同位置。

假设我有一个包含单词 'Hello'.

的向量（出于记忆原因我更喜欢使用它，因为我将处理很多单词）

我生成了“.”的二维向量字符 5x5 宽（所以它可以适应这个词）。

然后使用回溯算法，我想生成这个词可能占据的所有位置，字母 仍然相互链接。

例如：

 . . . . .        . . . . .              . . . . .
 H e . . .   or   . . . H .    or even   . . . . .
 . l . . .        . . o e .              . . . . .
 . l o . .        . . l l .              . . . . .
 . . . . .        . . . . .              o l l e H

我感兴趣的一维算法是（伪代码）：

function solve(word vector, size of vector) 

  if end of word vector
     Print vector obtained

   else for choice possible do
         if Choice is admissible then 
             Build partial Candidate according to Choice 
             Test(i + 1) 
             Undo Choice

这段伪代码可以给出单词中字母的不同组合。我正在尝试调整它以使其执行之前解释的操作。

遗憾的是我实施错误，因为我根本没有获得预期的结果：没有打印。我很高兴阅读您对此的评论和意见。

这是我目前所做的：

回溯函数：

// All the arguments of the function are correctly defined in the main, with i, j, k set to zero.

bool backtracking(vector<vector<char> > vect , vector <char> word,int n, int i, int j, int k) {

    if(k==n)    // If the end of the word is reached
    {
        print_grid(vect);  //Prints the 2D vector with the word included
        return true;
    }
    
    else    
    {
        
        if(admissible_choice(vect, n, i, j) == true) // If choice is admissible
        {
            
            vect[i][j] = word[k];                   // Builds partial candidate
            
            if (backtracking(vect,word,n,i+1,j,k)==true) // Moves in the i-direction
            {   k++;                    // If true, goes to the next element of the chain
                return true;        }
            
            if (backtracking(vect,word,n,i,j+1,k)==true) // Moves in the j direction
            {   k++;
                return true;        }
                    
            else
            {   vect[i][j] = '.';           // Backtrack, if no condition verified then fills the 2D vector with points
                
                return false;       }
        }
 
    return false;
    }
        
}

打印功能

void print_grid(vector<vector<char> > vect) {
    for (int i = 0; i < vect.size(); i++)  {
        for (int j = 0; j < vect[i].size(); j++) {
            cout << vect[i][j]; 
        }
        cout<<""<<endl;
    }
    cout<<"\n"<<endl;   
}

确定可接受选择的函数

bool admissible_choice(vector<vector<char> > vect, int n, int i, int j)
{
    if(i >= 0 && i < n && j >= 0 && j < n && vect[i][j] == '.')
    {   return true;}

    else
    {   return false;}
}

在此先感谢您提供的所有帮助！

Answer 1

给你。在某个点开始搜索与从一个有效点继续到下一个点之间存在根本区别。所以在这段代码中，place_word遍历所有可能的网格位置，为每个点调用递归backtracking。

backtracking需要查找，不仅要查找自增坐标，还要查找自减坐标。其中 place_word 仅增加其坐标 - 我认为您最初的尝试是试图将这些概念组合成一个代码单元。

我还选择通过引用传递 2D 网格向量，并撤消它之前的递归函数所做的任何更改 returns。这样一来，搜索只使用一个网格对象，而每次调用 backtracking 时都会制作一份新的网格副本，而按值传递会产生大量开销。

我需要重命名一些变量以帮助我了解发生了什么。我还删除了多余的维度变量，因为它们已经可以作为矢量大小使用。

#include <iostream>
#include <vector>
#include <algorithm>

// admissible_choice returns true when the point at (x,y) is inside the grid,
// and is also unpopulated.
bool admissible_choice(std::vector<std::vector<char> > grid, int x, int y) {
    return x >= 0
        && x < static_cast<int>(grid.front().size())
        && y >= 0
        && y < static_cast<int>(grid.size())
        && grid[y][x] == '.';
}

void print_grid(std::vector<std::vector<char> > const& grid) {
    for(const auto& line : grid) {
        for(auto ch : line) {
            std::cout << ch;
        }
        std::cout << '\n';
    }
    std::cout << '\n';
}

// backtracking performs a depth-first recursive search for valid word positions
void backtracking(std::vector<std::vector<char> > &grid, std::vector<char> const& word, int x, int y, int wi=0) {
    if(!admissible_choice(grid, x, y)) {
        return;
    }

    grid[y][x] = word[wi];

    if(++wi == word.size()) {
        print_grid(grid);
    } else {
        backtracking(grid, word, x+1, y, wi);
        backtracking(grid, word, x-1, y, wi);
        backtracking(grid, word, x, y+1, wi);
        backtracking(grid, word, x, y-1, wi);
    }
    grid[y][x] = '.';
}

// place_word initializes backtracking recursion, for every
// possible starting point for a word placed in a grid
void place_word(std::vector<std::vector<char> > &grid, std::vector<char> const& word) {
    const int width = static_cast<int>(grid.front().size());
    const int height = static_cast<int>(grid.size());
    for(int y=0; y<height; ++y) {
        for(int x=0; x<width; ++x) {
            backtracking(grid, word, x, y);
        }
    }
}

// ToVector converts a char string literal to a vector
template <std::size_t N>
std::vector<char> ToVector(const char (&str)[N]) {
    return std::vector<char>(&str[0], &str[N-1]);
}

// InitGrid returns a grid with the given dimensions in its unpopulated state
std::vector<std::vector<char> > InitGrid(std::size_t width, std::size_t height) {
    std::vector<std::vector<char> > grid(height);
    for(auto& line : grid) {
        line.assign(width, '.');
    }
    return grid;
}

int main() {
    auto word = ToVector("Hello");
    auto grid = InitGrid(word.size(), word.size());

    place_word(grid, word);
}

二维向量中的 C++ 回溯

C++ Backtracking in a 2D vector

c++

algorithm

backtracking

2d-vector

回溯函数：

打印功能

确定可接受选择的函数