为什么我的 BFS 算法没有返回预期的最短路径？

Question

我正在尝试编写一个算法，该算法应该找到从给定的 beginWord 到 endWord 的最短转换路径，这样一个字母就可以一次更改。

测试用例

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log","cog"]

预期输出为 5，因为可以遵循长度为 5 的最短转换之一：

"hit" -> "hot" -> "dot" -> "dog" -> "cog"

在我的算法中，我使用队列遵循 BFS，对于每个单词，我用从 'a' 到 'z' 的所有字母替换它的每个字母，同时我检查结果单词是否存在于给定的词典中，即 wordList.

如果是，那我就把它推入队列，这样它也可以像最后一个字一样处理。否则，从队列中获取下一个条目，依此类推，直到队列为空。

现在，我的代码如下 returns hit -> hot -> dot -> lot -> dog -> log -> cog，这是一个错误的输出。这主要是因为dot和dog错误地转换成了lot。

lot 和 dog 以及一个与 dot 不同的字母，因此它们都被推入队列并稍后处理，这导致类似的问题 [= 的双重转换15=] 变成 log 和 cog。

现在，这清楚地表明我遗漏了 BFS 和最短路径搜索的一些关键点。我如何决定我必须将 dot 转换为 dog 而不是 lot 以确保我按照最短路径到达预期目标，前提是两者都是有效的转换dot.

这将帮助我理解和修复我的代码。

var ladderLength = function(beginWord, endWord, wordList) {

    wordList = new Set(wordList);
    var str = [beginWord];

    var queue = [], distance = 0, i, j, len;
    len = beginWord.length;
    queue.push(beginWord);

    while (queue.length > 0) {
        var currentWord = queue.shift();
        if (currentWord === endWord) {
            console.log(str.join(" -> "));
            return distance + 1;
        }
        for (i = 0; i < len; i++) {
            var tempCh = currentWord[i];
            for (j = 'a'; j <= 'z'; j = String.fromCharCode(j.charCodeAt(0)+1)) {
                currentWord = currentWord.replaceAt(i,j);
                if (wordList.has(currentWord)) {
                    distance++;
                    wordList.delete(currentWord);
                    str.push(currentWord);
                    queue.push(currentWord);
                }
            }
            currentWord = currentWord.replaceAt(i, tempCh);

        }   
    }
    return 0;
};


String.prototype.replaceAt=function(index, replacement) {
    return this.substr(0, index) + replacement+ this.substr(index + replacement.length);
}

Answer 1

您可以在转换字符串的同时进行一些额外的处理以获得正确的输出。在替换字母之前，将要替换的字符 (i) 与将取代它的字符 (j).

进行比较

为每次迭代保留一个标志变量flag，并检查新字符j是否会更接近EndWord中相应位置的字符。如果它正在靠近而不是远离（例如，'d' vs 'l' for 'c' in cog），并且存在于 WordList 中，进行替换并设置 flag = true。如果在与角色的距离相同的情况下也可以进行另一个转换，请检查标志，如果为真，则跳过它，否则进行转换。

希望对您有所帮助。

Answer 2

I replace each of its letter with all alphabets

表示您进行了太多有效性检查。
我建议您只用 valid 字母替换每个字母。例如"hit"中的i只能用o代替："hot","dot","dog","lot","log","cog".
这将使程序更高效，更不容易出错。

Answer 3

我想我找到了我理解中的主要问题。主要问题是，在距离树的根级别 'd' 的给定级别，我可以有多个匹配项，例如"lot"和"dog"与"dot"改造后达到的水平相同。

在每个级别，我都必须排完队列，否则我计算的距离将变得不正确。

因此，当我将代码更改为以下内容时（请参阅代码中的注释 Process all items in queue which contains words on same level），算法变得更好了。至少对于许多测试用例来说更好，包括这个问题中给出的测试用例。

感谢大家审阅代码。 :)

var ladderLength = function(beginWord, endWord, wordList) { wordList = new Set(wordList);

    var queue = [], distance = 1, i, j, len;
    len = beginWord.length;
    queue.push(beginWord);

    while (queue.length > 0) {
        // Process all items in queue which contains words on same level
        for (var k=0; k<queue.length; k++) {
            var currentWord = queue.shift();
            if (currentWord === endWord) {
                return distance;
            }

            for (i = 0; i < len; i++) {
                var tempCh = currentWord[i];
                for (j = 'a'; j <= 'z'; j = String.fromCharCode(j.charCodeAt(0)+1)) {
                    if (j !== tempCh) {
                        currentWord = currentWord.replaceAt(i,j);
                        if (wordList.has(currentWord)) {
                            wordList.delete(currentWord);
                            queue.push(currentWord);
                        }
                    }
                }
                currentWord = currentWord.replaceAt(i, tempCh);

            } 
        }
        distance++;
    }
    return 0;
};

String.prototype.replaceAt=function(index, replacement) {
    return this.substr(0, index) + replacement+ this.substr(index + replacement.length);
}

为什么我的 BFS 算法没有返回预期的最短路径？

Why is my BFS algo not returning expected shortest path?

javascript

algorithm

breadth-first-search