使用深度优先搜索算法的无限循环错误
Infinity loop error using the depth-first search algorithm
我正在尝试创建一个 Boggle Solver 程序,但我的深度优先搜索功能出现错误。在我使用 for 循环遍历 'visited' 数组后,我的函数应该 return 并再次开始遍历我的 trie。相反,它会继续打印在已访问数组中找到的值。代码如下所示。
// 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);
我建议使用更简化的 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; }
您的代码中的问题出在 depth_first_search
中,您没有将 n
定义为 local 变量,而是隐式 全局 变量。
您的代码将 运行 替换为:
for (n = 0; n < neighbors.length; n++)
与:
for (var n = 0; n < neighbors.length; n++)
注意:我假设输入中有一点错字,其中“moo”实际上应该是“mood”。
我正在尝试创建一个 Boggle Solver 程序,但我的深度优先搜索功能出现错误。在我使用 for 循环遍历 'visited' 数组后,我的函数应该 return 并再次开始遍历我的 trie。相反,它会继续打印在已访问数组中找到的值。代码如下所示。
// 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);
我建议使用更简化的 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; }
您的代码中的问题出在 depth_first_search
中,您没有将 n
定义为 local 变量,而是隐式 全局 变量。
您的代码将 运行 替换为:
for (n = 0; n < neighbors.length; n++)
与:
for (var n = 0; n < neighbors.length; n++)
注意:我假设输入中有一点错字,其中“moo”实际上应该是“mood”。