||
意念网络——向量空间二分实验系统
缘起
1. 在已完成的“叠加体演示程序”基础上,和纽约老熊相约以数组二分算法难题为“磨刀石”,对叠加体的应用方法进行探索。试图通过用叠加体来解决数组二分这个“最容易的难题”,来探寻叠加体支撑“特例计算”的具体方案。
2. 前期已经对数组二分算法进行初步的算法实现,意外得到了貌似比传统算法效能有大幅提升的新算法:名为:对称剪枝算法。试算表明:该算法对数组二分求和编码进行状态树的搜索,配以对称失效检验进行状态树剪枝,避免了无效编码的深度遍历,保证了覆盖所有理论可能的状态结点的效果,也就是实现了实际只遍历极少数状态结点就能虚拟穷举地找到对分方案或极小偏差对分方案。为叠加体算法方案探索提供了基线的参照。
3. 算法实验的成功,让作者信心大增,于是,决定借助以往实验系统开发经验和资源,以对称剪枝算法为核心,对数组二分算法进行实验分析系统的设计与开发。并为未来的叠加体实验平台开发进行铺路。
4. 由于数组二分算法实际是对高维的整数分量向量进行按分量和测度进行对分拆解,所以,推广来说,其实质是对向量空间施行“按几何体上的张量测度约束关系进行维度分解”的操作。也就是将高维向量空间中的几何体,按某种测度关系,分解为两个低维子向量空间几何体,即:投影到两个子向量空间中的操作。
5. 由于预见到上述对向量空间进行张量分析的前景,将系统命名为“向量空间二分实验系统”。
系统实现说明
1. 左侧边栏用户界面功能
添加了系统实验管理的一个整体框架。其中包括如下功能:
(1) 系统管理:可设定系统创建向量空间的最小维数和最大维数,并可在限定维数范围内创建向量空间实例。
(2) 空间管理:可在选定的向量空间实例上,设定向量分量的最小位数和最大位数。并可在限定位数范围内创建实验项目。
(3) 项目管理:可在选定项目内维护任务轮次的定义,指定一个任务轮次的任务个数。
(4) 轮次管理:可在选定任务轮次中生成该轮次的计算任务。一个计算任务对应一个需要分量求和对分编码搜索的满足轮次参数设定的向量。
(5) 任务管理:维护在一个实验计划中包含的任务轮次,并可以显示计划中所有轮次的所有任务,这些任务是为一次批处理计算设定的实验计划的计算内容。
(6) 计划管理:可在系统中创建多套实验计划,并选定当前的实验计划进行维护和执行。其中还可指定单个任务执行的附加任务设定。
(7) 执行管理:可选择按深度优先还是宽度优先的两种算法对选定的实验计划进行执行计算。并可动态显示计算进度。
(8) 调节管理:对与计划中执行没有取得完全对分的向量进行分量数值的微调,使得微调后的向量可以取得完全对分的方案。
2. 中间实验分析栏功能
(1) 直方图
l 直方图直接显示每个实验任务的原始向量分量和对称二分后的子向量的数据特征。
l 每一个子栏右侧的蓝色和黑色条线显示了一个原始高维向量的各个分量。
l 左侧的绿色条线显示经求和对分后的得到的子向量求反后的分量。如果是红色,则表示对分求和后的偏差不为0。可以对原始向量进行微调,重新对分求和以得到完全对分的同样的编码。这意味着一个编码是同一组向量的分类标志,也就是:高维向量可以按照“分量求和二分”的操作进行分类,得到相同的二分编码的为一个等价类。
l 二分编码是以向量空间维数为长度大小的一个二进制编码,它代表着对向量每个分量进行分部求和选择与否的操作。其所有可能的状态形成一个2的指数级规模的状态空间,状态空间形成一个以全0为根结点,逐个位翻转组合产生的一个状态树。一个二进制编码代表状态树上的一个结点路径,因此,也称为“结点路径”。一个N维向量空间进行二分求和,理论上就有2^N个编码表示的二分方案。算法的难度来源于要在这个组合爆炸的状态空间中进行特定编码的搜索。
(2) 投影图
l 图中显示10个随机任务的45维向量二分后在二维截平面上的投影。
l 白色结点为二分前的原始向量的投影。
l 绿色结点为对分成功的对称二分子向量的反向量投影。
l 红色结点为对分最小偏差的二分子向量的反向量投影。
l 蓝色连线为二分前后向量的投影配对显示。
l 投影视图支持鼠标滚轮动态改变二维截平面参考旋转角度,显示投影位置动态变化的操作。
(3) 相变图
待实现,以期展现向量二分的计算复杂性随着问题规模参数的变化而突变的现象。
3. 右侧边栏显示配置交互功能
待实现。以期实现对显示图形的数据筛选过滤,图形视图变换参数的设置等功能。
拓展理解和引申问题:
1. 数组求和二分计算可以理解为是高维向量空间的二分测度的空间分解方案的计算。把分量和作为测度,将高维空间分解为两个子空间的张量积。本程序框架是否可作为一个张量分析的备选框架?
2. 本二分求和算法展现了较高的计算效能,可以在什么应用场景中去解决什么问题来测试算法的应用效果?
3. 如何成为叠加体(叠加量)理论的磨刀石?
非常感谢纽约老熊的友情合作与指导,上述问题还请纽约老熊或有兴趣的老师同学有空时给予指点。
邱嘉文 2024年8月14日星期三
参考文章:
附:向量空间二分实验一.最大规模任务计算实验
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-8-15 13:22
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社