深度优先搜索算法出现无限循环错误

Question

我正在尝试创建一个 Boggle 求解程序，但是我的深度优先搜索函数出现了错误。在使用 for 循环迭代“visited”数组之后，我的函数应该返回并开始再次通过 trie 进行搜索。但实际情况是，它继续打印在 visited 数组中找到的值。以下是代码。

  // Sample Boggle Dictionary
var boggle_dxctionary = ['apple', 'pickle', 'side',
  'sick', 'moo', 'cat',
  'cats', 'man', 'super',
  'antman', 'godzilla', 'dog',
  'dot', 'sine', 'cos',
  'signal', 'bitcoin', 'cool',
  'kick', 'zapper'
];

// Sample Boggle Board
var boggle_board = [
  ['c', 'n', 't', ],
  ['d', 'a', 't', ],
  ['o', 'o', 'm', ],
];

var column_length = boggle_board[0].length;
var row_length = boggle_board.length;
var trie_node = {
  'valid': false,
  'next': {}
};

var neighbors_delta = [
  [-1, -1],
  [-1, 0],
  [-1, 1],
  [0, -1],
  [0, 1],
  [1, -1],
  [1, 0],
  [1, 1],
];

function generate_trie(word, node) 
{
  if (!(word)) 
  {
    return;
  }
  if ((word[0] in node) == false) 
  {
    node[word[0]] = {  'valid': (word.length == 1),'next': {}};
  }
  generate_trie(word.slice(1, ), node[word[0]]);
}

function build_trie(boggle_dxct, trie) {
  for (var word = 0; word < boggle_dxct.length; word++) {
    generate_trie(boggle_dxct[word], trie);
  }
  return trie;
}

function get_neighbors(row, column) 
{
  var neighbors = [];

  for (var neighbor = 0; neighbor < neighbors_delta.length; neighbor++) 
  {
    var new_row = row + neighbors_delta[neighbor][0];
    var new_column = column + neighbors_delta[neighbor][1];

    if (new_row >= row_length || new_column >= column_length || new_row < 0 || new_column < 0) 
    {
      continue;
    }

    neighbors.push([new_row, new_column]);
  }
  return neighbors;
}


function depth_first_search(row, column, visited, trie, current_word, found_words, board)
{
  var row_column_pair = [row, column];
  for (var i = 0; i < visited.length; i++) # Infinity loop error
  {
    var a = visited[i][0];
    var b = visited[i][1];
    if (row == a && column == b)
    {
      console.log(a,b);
      return;
    }
  }


  var letter = board[row][column];
  visited.push(row_column_pair);
  if (letter in trie) 
  {
    current_word = current_word + letter;
    console.log(current_word)
    if (trie[letter]['valid']) 
    {
      console.log("Found word", current_word, "at", row_column_pair);
      found_words.push(current_word);
      //console.log(visited);

    }
    var neighbors = get_neighbors(row, column);
    for (n = 0; n < neighbors.length; n++) 
    {
      depth_first_search(neighbors[n][0], neighbors[n][1], visited.slice(0), trie[letter], current_word, found_words, board);
    }
  }
}

function main(trie_node, board) {
  trie_node = build_trie(boggle_dxctionary, trie_node);
  var found_words = [];
  for (r = 0; r < row_length; r++) {
    for (c = 0; c < column_length; c++) 
    {
      var visited = [];
      depth_first_search(r, c, visited, trie_node, '', found_words, board);
    }
  }
  console.log(found_words);
}

main(trie_node, boggle_board);

- TonyGrey

---

你有想要结果的示例吗？ - Nina Scholz

期望的结果是 ['cat', 'cat', 'dot', 'man', 'mood']。 - TonyGrey

你能否对已经给出的答案进行评论？ - trincot

Answer 1

我建议使用一个更简化的trie，以避免额外开销。

然后迭代给定的板并检查实际位置，并通过交出trie的根节点来处理。

如果存在end属性，则找到了一个单词。

function check(i, j, t, found = '') {
    const letter = board[i][j];
    if (!t[letter]) return;
    found += letter
    if (t[letter].end) {
        words.push(found);
    }
    for (let [x, y] of neighbors) {
        if (i + x < 0 || i + x >= rows || j + y < 0 || j + y >= cols) continue;
        check(i + x, j + y, t[letter], found);
    }
}

const
    dictionary = ['apple', 'pickle', 'side', 'sick', 'moo', 'cat', 'cats', 'man', 'super', 'antman', 'godzilla', 'dog', 'dot', 'sine', 'cos', 'signal', 'bitcoin', 'cool', 'kick', 'zapper'],
    board = [['c', 'n', 't'], ['d', 'a', 't'], ['o', 'o', 'm']],
    rows = board.length,
    cols = board[0].length,
    neighbors = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]],
    trie = dictionary.reduce((trie, word) => {
        [...word].reduce((t, c) =>  t[c] = t[c] || {}, trie).end = true;
        return trie;
    }, {}),
    words = [];

for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
        check(i, j, trie);
    }
}

console.log(words);
console.log(trie);

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz

Answer 2

你代码中的问题在于 depth_first_search 函数中，你没有将 n 定义为一个局部变量，而是隐式地定义为全局变量。

当你将这个代码替换为以下内容时，你的代码将可以正常运行：

for (n = 0; n < neighbors.length; n++) 

使用：

for (var n = 0; n < neighbors.length; n++) 

注意：我假设输入中有一个小错别字，"moo" 应该真正是 "mood"。

- trincot