c++ - 来自 DFA 的长度为 k 的单词

Question

美好的一天，我在生成一个包含所有长度为 k 的单词的列表时遇到了一个严重的问题(生成函数是用于生成所有长度为 k 的单词的函数，另一个函数用于确定一个单词是否被接受) 仅通过使用 DFS 算法来自 DFA，这是我的尝试:

#include<vector>
#include<iostream>
#include<fstream>
#include<string.h>

using namespace std;

vector < pair <int,char> > a[100];

int viz[100], v[100];
char s1[100];

void accepted (int q, char c, char s[100], int x) {
    c = s[x];
    viz[q] = 1;
    cout << q;
    for (int i = 0; i < a[q].size(); i++)
        if (a[q][i].second == c) {
            x++;
            accepted (a[q][i].first, a[q][i+1].second, s, x);
        }
}

void generate (int q, int k) {
    int x = 0;
    v[q] = 1;
    while (x < k) {
        cout << a[q][0].second;
        for (int i = 0; i < a[q].size(); i++)
            if (v[a[q][i].first] == 0)
            {
                cout << a[q][i].second;
                generate(a[q][i].first, k);
            }
        x++;
    }
}

int main() {
    ifstream f ("input.txt");
    int n, m, x, y, i, j, k;
    char c;
    char s[100];
    f >> n >> m;
    for (i = 0; i < m; i++) {
            f >> x >> y;
            f >> c;
            a[x].push_back (make_pair(y,c));
            }
    for (i = 0; i < n; i++) {
        cout << i << ": ";
        for (j = 0; j < a[i].size(); j++)
            cout << a[i][j].first << a[i][j].second << " ";
        cout << endl;
    }
    cout << endl << "Fiite states: 2, 3" << endl << endl;
    cin.get (s,100);
    accepted(0, s[0], s, 0);
    if (viz[2] == 1) cout << endl << "Accepted";
    cout << endl;
    cin >> k;
    generate (0, k);
    cout << endl;
    return 0;
}

我的输入也是这样的:

4 6
0 0 a
0 1 b
1 2 c
2 2 a
2 3 c
3 3 c

DFA 和输出如下所示:

我面临的严重问题是我无法找到一种方法来通过调用生成函数将所有获得的单词正确输出到屏幕上。

Answer 1

我如下更改了您的生成函数。接下来是关于我的想法以及我如何改变它的解释。

void generate (int q, int k, string &s) {
    if (k > 0) {
        for (int i = 0; i < a[q].size(); i++)
        {
            s += a[q][i].second;
            generate(a[q][i].first, k-1, s);
            s.pop_back();
        }
    }
    else {
        cout << s << endl;
    }
}

首先，您正在尝试 DFS 的递归和重复版本的混合，但如果您要使用显式堆栈的重复版本，我怀疑您没有保留堆栈的结构。基本上，您的外部 while 循环是错误的，因为深度应该随着您递归遍历 图形而增加，而不是像您那样使用 while 循环在单个递归级别重复。正如我提到的，您还可以采用重复方法并使用显式定义的堆栈，而不是递归实现 DFS 时内存隐式使用的堆栈。但是通过递归实现更容易、更直观地掌握 DFS，所以我省略了外部循环。

其次，保留一个已访问节点的列表不是一个好主意，因为您想要列出所有 k 长度的字符串并且您的 DFA 不是一个简单的图。 (即可能存在从节点 u 到节点 u 的边)所以我删除了 for 循环内的 if 语句，因为您可以多次访问正常节点。您的方法是基于 DFA 的分支因子的指数，但是如果您的 k 足够小，那么无论如何它都应该起作用。指数方法不是您正在寻找这个问题的解决方案的问题。

第三，可能由于您使用了 while 循环，在每个级别打印单个字符时出现了混淆，这是不正确的。请记住，在深度为 k 的每个节点，您必须从树的根部开始打印所有您遇到的字符。这就是为什么我将一个字符串作为第三个参数添加到您的函数中。不过别担心，它是通过引用传递的，它只会导致您的算法增加 O(k) 空间复杂度，这应该可以忽略不计。

如果在您的 main 函数中使用下面的调用开始遍历，您会发现它可以正常工作。

string S;
generate(0, k, S);