Лестница слов 2 с использованием BFS - PullRequest
Новая
       13

Лестница слов 2 с использованием BFS

0 голосов
/ 18 июня 2020

Море РЕДАКТИРОВАТЬ !! Ниже

я кодирую алгоритм словарной лестницы. Пользователь вводит начальное слово, конечное слово и ха sh всех слов. Алгоритм возвращает все кратчайшие пути (несколько, если они есть) от начального слова до конечного слова. Например -> start_word = 'cold', end_word = 'warm'

output = [[cold -> cord-> card-> ward-> warm], [/ Если существует другой путь /]].

Каждое последующее слово от предыдущего отличается на один символ. Я использую поиск 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 = {};
    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;
}

Он действительно возвращает несколько путей, однако проблема в том, что он не возвращает все пути. Один из путей, который он возвращает ->

1) бодрствовать, осознавать, клясться, делиться, шир, ширр, шиер, чистый, овца, сон

однако путь не возвращается -> 2) «бодрствовать», «осознавать», «клясться», «делиться», «шарн», «шон», «показывать», «блеск», «овец», «спать»

I Я почти уверен, что причина в том, что, как я его закодировал, слово «share» помечается как посещенное при первой встрече (в 1)). Следовательно, он не go по второму пути (в 2))

Чтобы решить эту проблему, я немного изменил свое значение на l oop: 

    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);

        }

Идея была чтобы проверить, посещалось ли слово в пути, который вы отслеживаете в очереди, а не глобально. Однако это решение по какой-то причине застревает где-то в al oop и не завершается (я предполагаю, что из-за большого набора данных?).

Что-то не так с моим кодом во втором или требуется слишком долго из-за большого набора данных? Как я могу лучше найти решение?

EDIT !!!

Теперь я вместо того, чтобы искать все пути, нахожу длину кратчайшего пути, а затем выполняю 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;
}

Решение теперь прекращается, поэтому определенно проблема ранее заключалась в большом количестве поисков. Однако мой алгоритм все еще не дает мне правильного ответа, так как то, как я отслеживаю глубину моих узлов (слов), почему-то неверно.

1 Ответ

1 голос
/ 18 июня 2020

Вы пытаетесь найти эффективное решение, но, скорее всего, его не существует. См. этот ответ . Перечисление всех кратчайших путей может быть очень дорогостоящим.

...