1

我目前正在尝试使用回溯来生成单词在 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;}
}

提前感谢您提供的所有帮助！

4

1 回答 1

0

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

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

我还选择通过引用传递 2D 网格矢量，并在递归函数返回之前撤消其所做的任何更改。这样，搜索只使用一个网格对象，而通过值传递会产生大量开销，因为每次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);
}
于 2016-12-20T02:13:45.833 回答