java - Hopcroft 最小化问题
问题描述
我正在从下面的维基百科页面实现 Hopcroft DFA 最小化,但出现了问题。看起来 W 每个循环都添加了一个空集,当我阻止添加空集时,结果看起来很古怪:
启动 DFA:
8
Sigma: a b c
------------------------
0: 1 2 3
1: 1 4 5
2: 4 2 6
3: 5 6 3
4: 4 4 7
5: 5 7 5
6: 7 6 6
7: 7 7 7
------------------------
0: Initial State
0,1,2,3,4,5,6: Accepting State(s)
输出:
[7]
[0, 1, 2, 4]
[0, 1, 3, 5]
[1, 4, 5]
[0, 2, 3, 6]
[2, 4, 6]
[3, 5, 6]
https://en.wikipedia.org/wiki/DFA_minimization
这是我的实际 hopcroft 代码:
public Set<Set<Integer>> hopcroftMinimization() {
Set<Set<Integer>> P = new HashSet<>();
Set<Set<Integer>> W = new HashSet<>();
P.add(new HashSet<Integer>(accepting));
P.add(setSubtraction(states, accepting));
W.addAll(P);
while (!W.isEmpty()) {
System.out.println(W.toString());
Object[] wArr = W.toArray();
Object[] pArr = P.toArray();
for (Object A : wArr) {
W.remove(A);
System.out.println(W.toString());
for (char input : validInputs) {
Set<Integer> X = findX((Set)A, input);
for (Object Y : pArr) {
Set<Integer> xAndY = intersection(X, (Set)Y);
Set<Integer> yNotX = setSubtraction((Set)Y, X);
if (!xAndY.isEmpty() && !yNotX.isEmpty()) {
P.remove(Y);
P.add(xAndY);
P.add(yNotX);
if (W.contains(Y)) {
W.remove(Y);
W.add(xAndY);
W.add(yNotX);
}
} else {
if (xAndY.size() <= yNotX.size()) {
W.add(xAndY);
} else {
W.add(yNotX);
}
}
}
}
}
}
return P;
}
这是一个完整的pastebin: https ://pastebin.com/kYyYbCXU
解决方案
这在错误的地方:
for (Object Y : pArr) {
Set<Integer> xAndY = intersection(X, (Set)Y);
Set<Integer> yNotX = setSubtraction((Set)Y, X);
if (!xAndY.isEmpty() && !yNotX.isEmpty()) {
P.remove(Y);
P.add(xAndY);
P.add(yNotX);
if (W.contains(Y)) {
W.remove(Y);
W.add(xAndY);
W.add(yNotX);
}
///////////////////////////
} else { // <<<--- THIS BLOCK
if (xAndY.size() <= yNotX.size()) {
W.add(xAndY);
} else {
W.add(yNotX);
}
}
///////////////////////////
}
它应该在这里:
for (Object Y : pArr) {
Set<Integer> xAndY = intersection(X, (Set)Y);
Set<Integer> yNotX = setSubtraction((Set)Y, X);
if (!xAndY.isEmpty() && !yNotX.isEmpty()) {
P.remove(Y);
P.add(xAndY);
P.add(yNotX);
if (W.contains(Y)) {
W.remove(Y);
W.add(xAndY);
W.add(yNotX);
///////////////////////////
} else { // <<<--- THIS BLOCK
if (xAndY.size() <= yNotX.size()) {
W.add(xAndY);
} else {
W.add(yNotX);
}
}
///////////////////////////
}
}
不确定这是否是唯一的问题,但至少这是一个问题。
推荐阅读
- react-native - 带有 FlatList 滚动和动态高度的 React Navigation 5 顶部栏
- python - 如何在 Windows 上的 anaconda spyder 中导入“opencv”库
- asp.net - SqlParameterCollection 只接受非空的 SqlParameter 类型对象,不接受 DataTable 对象
- php - 在 WooCommerce 的单个产品页面上为低库存产品添加 CSS 类
- c# - DevExpress 错误缺少 using 指令或程序集引用
- typescript - 打字稿生成器功能作为参数
- php - 在 elasticsearch 中为查询定义自定义分析器时出错
- python - 如何使用 urllib3 发出 put 请求
- c# - 如何从包含该值的列表中删除一个值?
- java - 使用按钮将文件添加到 JList