使用BFS的字梯2

Question

海编辑！！以下

我正在编写一个字梯算法。用户输入开始词、结束词和所有词的散列。该算法 returns 从起始词到结束词的所有最短路径（如果存在则为多个）。例如 -> start_word = 'cold' , end_word = 'warm'

output = [[ cold -> cord-> card-> ward-> warm], [/如果存在另一路径/]].

每个连续的单词都与前一个单词相差一个字符。我正在使用 BFS 搜索来解决这个问题。我的策略是 return 所有路径，然后 select returned 列表中最短的路径。这是我 return 所有路径的代码：

auto word_ladder::generate(std::string const& from, std::string const& to, absl::flat_hash_set<std::string> const& lexicon) -> std::vector<std::vector<std::string>> {


    absl::flat_hash_set<std::string> visited = {};
    std::queue<std::vector<std::string>> search_queue = {};
    std::vector<std::vector<std::string>> paths = {};

    search_queue.push(std::vector<std::string>{from});

    while (!search_queue.empty()) {
    auto word = search_queue.front();
    search_queue.pop();

    auto neighbours = generate_neighbours(word.back(), lexicon);
    for (auto &i: neighbours) {

        auto new_word = word;
        new_word.push_back(i);
        if (i == to) {
            paths.push_back(new_word);
            continue;
        }

        if (visited.find(i) != visited.end()) {
            continue;
        }

        search_queue.push(new_word);
        visited.insert(i);

    }
}

    return paths;
}

它有 return 多条路径，但问题是它没有 return 所有路径。它 returns 的路径之一是 ->

1) 清醒、意识到、sware、share、shire、shirr、shier、sheer、sheep、sleep

但是它没有 return 路径 -> 2) "awake","aware","sware","share","sharn" ,"shawn","shewn","sheen","sheep","sleep"

我很确定原因是因为我编码它的方式，它在第一次遇到它时将 "share" 标记为已访问（在 1 中））。因此它不会通过第二条路径（in 2））

为了解决这个问题，我稍微更改了 for 循环：

    for (auto &i: neighbours) {

            auto new_word = word;
            new_word.push_back(i);
            if (i == to) {
                paths.push_back(new_word);
                continue;
            }

            for (auto &j: word) {
                if (j == i) {
                    continue;
                }
            }

            search_queue.push(new_word);

        }

我们的想法是检查是否在您在队列中跟踪的路径中访问了该词，而不是全局访问。但是，由于某种原因，此解决方案在某处陷入循环并且不会终止（我假设是由于大型数据集？）。

是不是我的代码有问题，还是因为数据集大，耗时太长？我怎样才能更好地实现解决方案？

编辑！！！

我现在不是寻找所有路径，而是寻找最短路径的长度，然后执行 BFS 直到该深度以获得该深度的所有路径。

auto word_ladder::generate(std::string const& from, std::string const& to, absl::flat_hash_set<std::string> const& lexicon) -> std::vector<std::vector<std::string>> {


    absl::flat_hash_set<std::string> visited = {};
    visited.insert(from);

    std::queue<std::vector<std::string>> search_queue = {};
    std::vector<std::vector<std::string>> paths = {};

    search_queue.push(std::vector<std::string>{from});

    auto length = find_shortest_path_length(from, to, lexicon);
    std::cout << "length is: " << length << "\n";
    // auto level = 0;

    std::unordered_map<std::string, int> level_track = {};
    level_track[from] = 0;

    while (!search_queue.empty() ) {
        auto word = search_queue.front();
        search_queue.pop();

        // **
        if (level_track[word.back()] <= length) {
            auto neighbours = generate_neighbours(word.back(), lexicon);
            const auto &parent = word.back();
            for (auto &i: neighbours) {

                auto new_word = word;
                new_word.push_back(i);
                if (i == to) {
                    paths.push_back(new_word);
                    std::cout << "The level at the path was " << level_track[parent] << "\n";
                    continue;
                }

                if (path_crossed(word, i)) {
                    continue;
                }


                search_queue.push(new_word);
                level_track[i] = level_track[parent] + 1;

            }
        }
    }
    return paths;
}

解决方案现在终止，所以之前的问题肯定是大量搜索。但是我的算法仍然没有给我正确的答案，因为我跟踪节点（单词）深度的方式在某种程度上是不正确的。

Answer 1

您正试图找到一个有效的解决方案，但很可能它不存在。参见 this answer。枚举所有条最短路径的成本可能非常高。

使用BFS的字梯2

Word ladder 2 using BFS

c++

breadth-first-search