LinuxSir.cn,穿越时空的Linuxsir!

 找回密码
 注册
搜索
热搜: shell linux mysql
查看: 450|回复: 0

BSF算法

[复制链接]
发表于 2024-2-19 22:57:46 | 显示全部楼层 |阅读模式
无向图有 24 个顶点,分别用 A'、B、C'、D'、E'、F'、G'、H'、I'、J'、K'、L'、M'、N'、P'、Q'、R'、S'、T'、U'、V'、W'、Y' 和 Z' 表示。{M', Z'}, {M', Y'}, {L', W'}, {K', V'}, {J', U'}, {J', T'}, {I', S'}, {H', R'}, {G', Q'}, {F', P'}, {F', N'}, {E', M'}, {E', L'}, {D', K'}, {D', J'}, {D', I'}, {C', H'}, {C', G'}, {B', F'}, {B', E'}, {A', D'}, {A', C'}, 和 {A', B'} 是此图中的边。假设广度优先搜索不会沿任何路径重新访问任何顶点。每条边等价于两个算子,例如,{A', B'}对应的算子是A' --> B'和B' --> A'。如果 D' 是初始状态,V' 是目标状态,那么除了 D' 和 V' 之外,有多少个顶点是广度优先搜索保证访问的?
我已经编写了以下代码,但我对一件事感到困惑。我是否应该考虑 D 的近邻,包括 A、I、J 和 K,并考虑所有可能性?
假设
可以从 D、I、J 和 K 访问,然后从 I 访问“S”,从 J、“T”和“U”访问,从“K”访问“V”。到目前为止,{E,J,K,S,T,U} 都在这边访问。现在我的问题是,我是否也应该考虑通过 A 的所有路径?就像 B 和 C 可以通过 A 访问一样,那么 E 和 F 可以通过 B 访问,到目前为止,依此类推。非常感谢您的帮助。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

unordered_map<char, vector<char>> graph = {
    {'A', {'B', 'C', 'D'}},
    {'B', {'A', 'F', 'E'}},
    {'C', {'A', 'H', 'G'}},
    {'D', {'A', 'K', 'J', 'I'}},
    {'E', {'B', 'M', 'L'}},
    {'F', {'B', 'P', 'N'}},
    {'G', {'C', 'Q'}},
    {'H', {'C', 'R'}},
    {'I', {'D', 'S'}},
    {'J', {'D', 'T', 'U'}},
    {'K', {'D', 'V'}},
    {'L', {'E', 'W'}},
    {'M', {'E', 'Z', 'Y'}},
    {'N', {'F'}},
    {'P', {'F'}},
    {'Q', {'G'}},
    {'R', {'H'}},
    {'S', {'I'}},
    {'T', {'J'}},
    {'U', {'J'}},
    {'V', {'K'}},
    {'W', {'L'}},
    {'Y', {'M'}},
    {'Z', {'M'}}
};

int bfs(char start, char goal) {
    queue<vector<char>> q;
    unordered_map<char, bool> visited;
    q.push({ start });
    visited[start] = true;

    while (!q.empty()) {
        vector<char> path = q.front();
        q.pop();
        char node = path.back();

        if (node == goal) {
            cout << "Shortest path: ";
            for (char vertex : path) {
                cout << vertex << " -> ";
            }
            cout << "\b\b\b   \n";
            return path.size() - 1;
        }

        for (char adjacent : graph[node]) {
            if (!visited[adjacent]) {
                visited[adjacent] = true;
                vector<char> new_path = path;
                new_path.push_back(adjacent);
                q.push(new_path);
            }
        }
    }

    return -1;
}

int main() {
    char start = 'Z';
    char goal = 'C';

    int operators = bfs(start, goal);
    if (operators != -1) {
        cout << "Number of operators on the path found by BFS: " << operators << endl;
    }
    else {
        cout << "Goal state not reachable from the initial state!" << endl;
    }

    return 0;
}

您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 返回顶部 返回列表