【挑战】计算48种依次泛化的假设情况下,总共有多少种不可再简化的析合范式?

简介: 一种可行的算法: 由于属性泛化后,一个泛化的假设可以对应多个具体假设。 把所有假设按三属性泛化,二属性泛化,一属性泛化,具体属性排序(这样可以保证排在后面的假设不会包含前面的任何一个假设,所以省略了一些包含判断),进行循环枚举,按顺序遍历所有假设组合248种可能(当然绝大部分都提前结束了,不会是那么夸张的量级,虽然也不低):使用栈来实现非递归,如果当前假设还有没被析合式所包含的具体假设,则认为可以入栈,并当前栈大小的长度计数加1,并继续扫描。

一种可行的算法: 
由于属性泛化后,一个泛化的假设可以对应多个具体假设。 
把所有假设按三属性泛化,二属性泛化,一属性泛化,具体属性排序(这样可以保证排在后面的假设不会包含前面的任何一个假设,所以省略了一些包含判断),进行循环枚举,按顺序遍历所有假设组合248种可能(当然绝大部分都提前结束了,不会是那么夸张的量级,虽然也不低):

  • 使用栈来实现非递归,如果当前假设还有没被析合式所包含的具体假设,则认为可以入栈,并当前栈大小的长度计数加1,并继续扫描。
  • 如果当前扫描已经到了最后一个假设,或者所有具体假设已经被全部包含,则退栈。
  • 循环结束条件:当最后一个假设作为第一个压入栈的元素时,认为已经遍历结束。

由于一共有18种具体假设,可以用一个32位整型(变量为hypos_cur)的后18位来表示每一个具体假设。用1表示具体假设没被包含,用0表示具体假设已经被析合式包含。初始的析合式为空,可以设初试值为0X3FFFF。每个假设也对应一个32位整型(假设变量为hypo_const),代表着它所对应了哪些具体假设,如果它包含了某种具体假设,则该位为1。

  • 判断析合式是否包含了全部的具体假设:hypos_cur=0。
  • 判断该假设是否已经被析合范式包含:用hypo_const与hypos_cur做与运算(结果用hypo_tmp表示),如果为0表示已经被包含(判断该假设是否包含了当前的析合式:用hypo_const与hypos_cur做或运算,如果为0X3FFFFF,则认为该假设包含了当前析合式,但由于前面对所有假设做了排序,不可能出现这种情况,所以可以省略该判断)。
  • 当某个假设加入析合范式后(入栈)用hypos_cur与hypo_tmp做异或运算,来更改析合式所包含的具体假设。
  • 出栈时再次用hypos_cur与hypo_tmp做异或,回到加入该假设前的情况。
  • 因为是指数级遍历的算法,所以很慢

下面将直接贴上代码,供参阅讨论:

  1 #include <vector>
  2 
  3 #include <stack>
  4 
  5 using namespace std;
  6 
  7  
  8 
  9 //按泛化程度排序,保证排在后面的假设不会不会包含前面的任何一个假设
 10 
 11 static const char list[] = {
 12 
 13     0,0,0,
 14 
 15     0,0,1,0,0,2,0,0,3,0,1,0,0,2,0,0,3,0,1,0,0,2,0,0,
 16 
 17     0,1,1,0,1,2,0,1,3,0,2,1,0,2,2,0,2,3,0,3,1,0,3,2,0,3,3,
 18 
 19     1,0,1,1,0,2,1,0,3,2,0,1,2,0,2,2,0,3,
 20 
 21     1,1,0,1,2,0,1,3,0,2,1,0,2,2,0,2,3,0,
 22 
 23     1,1,1,1,1,2,1,1,3,1,2,1,1,2,2,1,2,3,1,3,1,1,3,2,1,3,3,
 24 
 25     2,1,1,2,1,2,2,1,3,2,2,1,2,2,2,2,2,3,2,3,1,2,3,2,2,3,3
 26 
 27 };
 28 
 29  
 30 
 31 //用来派生的抽象类
 32 
 33 class hypos {
 34 
 35 public:
 36 
 37     virtual int insert(int cur) = 0;
 38 
 39 };
 40 
 41  
 42 
 43 //单个的假设类
 44 
 45 /*
 46 
 47 hypo_const  假设对应的具体假设集合
 48 
 49 */
 50 
 51 class hypo :public hypos {
 52 
 53 public:
 54 
 55     hypo(int a, int b, int c) {
 56 
 57         hypo_const = 0;
 58 
 59         vector<char>  p[3];
 60 
 61         if (a == 0) {
 62 
 63             p[0].push_back(1);
 64 
 65             p[0].push_back(2);
 66 
 67         }
 68 
 69         else
 70 
 71             p[0].push_back(a);
 72 
 73         if (b == 0) {
 74 
 75             p[1].push_back(1);
 76 
 77             p[1].push_back(2);
 78 
 79             p[1].push_back(3);
 80 
 81         }
 82 
 83         else
 84 
 85             p[1].push_back(b);
 86 
 87         if (c == 0) {
 88 
 89             p[2].push_back(1);
 90 
 91             p[2].push_back(2);
 92 
 93             p[2].push_back(3);
 94 
 95         }
 96 
 97         else
 98 
 99             p[2].push_back(c);
100 
101         for (unsigned int i = 0;i < p[0].size();i++)
102 
103             for (unsigned int j = 0;j < p[1].size();j++)
104 
105                 for (unsigned int k = 0;k < p[2].size();k++)
106 
107                     hypo_const |= (1 << (p[0][i] * 9 + p[1][j] * 3 + p[2][k] - 13));
108 
109     }
110 
111  
112 
113     //判断是否要加入到析合式 如果还有具体假设没被包含,则加入
114 
115     int insert(int cur) {
116 
117         return (hypo_const & cur);
118 
119     };
120 
121  
122 
123 private:
124 
125     int hypo_const;
126 
127 };
128 
129  
130 
131 //用于压入栈的派生类 用来实现非递归
132 
133 /*
134 
135 hypo_tmp    记录这个假设入栈时,带入了哪些具体假设,出栈时要还原
136 
137 ptr         记录入栈时的位置
138 
139 */
140 
141 class hypo_ss :public hypos {
142 
143 public:
144 
145     hypo_ss(int _ptr,int tmp){
146 
147         hypo_tmp = tmp;
148 
149         ptr = _ptr;
150 
151     }
152 
153     int insert(int cur) {
154 
155         return 0;
156 
157     };
158 
159     int hypo_tmp;
160 
161     int ptr;
162 
163 };
164 
165  
166 
167 //用来循环遍历的类
168 
169 /*
170 
171 sum     各个长度的析合式各有多少种可能
172 
173 ss      用来实现非递归的栈
174 
175 hypos_cur   当前没被包含的具体假设 初始值为0X3FFFF
176 
177 hyposs  48个假设集合
178 
179 */
180 
181 class Traversal :public hypos {
182 
183 public:
184 
185     Traversal() {
186 
187         hypos_cur = 0x3ffff;
188 
189         for(int i=0;i<48;i++)
190 
191             hyposs.push_back(hypo(list[3*i], list[3*i+1], list[3*i+2]));
192 
193     }
194 
195  
196 
197     //循环顺序遍历的主体
198 
199     //cur  初试的位置 设为0
200 
201     int insert(int cur) {
202 
203         //当前指向的位置
204 
205         int ptr = cur;
206 
207         while (1) {
208 
209             //退出条件 当最后一个假设作为第一个入栈的元素 表示遍历完成
210 
211             if (ptr > 47 && !ss.size()) break;
212 
213             //回退条件  扫描到最后或者所有具体假设都被包含
214 
215             if (hypos_cur == 0 || ptr>47) {
216 
217                 hypo_ss hypo_tmp = ss.top();
218 
219                 hypos_cur ^= hypo_tmp.hypo_tmp;
220 
221                 ptr = hypo_tmp.ptr + 1;
222 
223                 ss.pop();
224 
225                 continue;
226 
227             }
228 
229  
230 
231             //入栈条件  如果该假设还有未被包含的具体假设 则入栈,并当前栈大小的计数加1
232 
233             if (int tmp =hyposs[ptr].insert(hypos_cur)) {
234 
235                 hypos_cur ^= tmp;
236 
237                 ss.push(hypo_ss(ptr, tmp));
238 
239                 if (sum.size() < ss.size())
240 
241                     sum.push_back(0);
242 
243                 sum[ss.size() - 1]++;
244 
245             }
246 
247             ptr++;
248 
249         }
250 
251         return 1;
252 
253     };
254 
255     //输出各个长度的可能数
256 
257     void print() {
258 
259         for (unsigned int i = 0;i < sum.size();i++)
260 
261             printf("length %d : %d\n", i + 1, sum[i]);
262 
263     }
264 
265 private:
266 
267     vector<int> sum;
268 
269     stack<hypo_ss> ss;
270 
271     int hypos_cur;
272 
273     vector<hypo> hyposs;
274 
275 };
276 
277  
278 
279 int main()
280 
281 {
282 
283     Traversal traversal;
284 
285     traversal.insert(0);
286 
287     traversal.print();
288 
289     system("pause");
290 
291     return 0;
292 
293 }

 

目录
相关文章
|
7月前
|
算法 搜索推荐 图计算
图计算中的社区发现算法是什么?请解释其作用和常用算法。
图计算中的社区发现算法是什么?请解释其作用和常用算法。
139 0
|
15天前
|
机器学习/深度学习 Python
堆叠集成策略的原理、实现方法及Python应用。堆叠通过多层模型组合,先用不同基础模型生成预测,再用元学习器整合这些预测,提升模型性能
本文深入探讨了堆叠集成策略的原理、实现方法及Python应用。堆叠通过多层模型组合,先用不同基础模型生成预测,再用元学习器整合这些预测,提升模型性能。文章详细介绍了堆叠的实现步骤,包括数据准备、基础模型训练、新训练集构建及元学习器训练,并讨论了其优缺点。
33 3
|
2月前
|
编解码 算法 数据可视化
lintsampler:高效从任意概率分布生成随机样本的新方法
在实际应用中,从复杂概率密度函数(PDF)中抽取随机样本的需求非常普遍,涉及统计估计、蒙特卡洛模拟和物理仿真等领域。`lintsampler` 是一个纯 Python 库,旨在高效地从任意概率分布中生成随机样本。它通过线性插值采样算法,简化了复杂分布的采样过程,提供了比传统方法如 MCMC 和拒绝采样更简便和高效的解决方案。`lintsampler` 的设计目标是让用户能够轻松生成高质量的样本,而无需复杂的参数调整。
29 1
lintsampler:高效从任意概率分布生成随机样本的新方法
|
6月前
McCabe复杂度(理论与示例说明)
McCabe复杂度(理论与示例说明)
112 0
|
算法 调度 决策智能
【两阶段鲁棒优化】利用列-约束生成方法求解两阶段鲁棒优化问题(Python代码实现)
【两阶段鲁棒优化】利用列-约束生成方法求解两阶段鲁棒优化问题(Python代码实现)
334 0
【两阶段鲁棒优化】利用列-约束生成方法求解两阶段鲁棒优化问题(Python代码实现)
Matlab:如何利用层次分析法(升级版)计算具有多重指标的判断矩阵的一致性检验和权重
Matlab:如何利用层次分析法(升级版)计算具有多重指标的判断矩阵的一致性检验和权重
370 0
|
机器学习/深度学习 数据挖掘 Python
统计回归模型中的一些概念解释
统计回归模型中的一些概念解释
149 0
|
存储 数据可视化 数据挖掘
知识点丨重测序数据进行kinship亲缘关系分析、构建IBS矩阵的方法与介绍
知识点丨重测序数据进行kinship亲缘关系分析、构建IBS矩阵的方法与介绍
知识点丨重测序数据进行kinship亲缘关系分析、构建IBS矩阵的方法与介绍
|
编解码 自然语言处理 数据可视化
MIM方法为什么简单高效?可视化和大规模实验给出了答案
MIM方法为什么简单高效?可视化和大规模实验给出了答案
218 0
MIM方法为什么简单高效?可视化和大规模实验给出了答案
|
机器学习/深度学习 自然语言处理 达摩院
模型精度再被提升,统一跨任务小样本学习算法 UPT 给出解法!
UPT是一种面向多种NLP任务的小样本学习算法,致力于利用多任务学习和预训练增强技术,在仅需要标注极少训练数据的情况下,提升大规模预训练语言模型在多种场景下的模型精度。