全面展开法

TheMatrix
楼主 (未名空间)

这个词是我发明的,因为我觉得它太形象了。说的是广度优先的树遍历法。我还有几个名字给它。一个叫波前法,借鉴wave front的用法。还有一个我更喜欢的,叫前锋推进法。当然,各有千秋。

它从起始条件出发,步步推进,步步全面展开,最后得到的是全部可能路径的集合。当然,还可以对集合求值,比如求最小值,或者其他aggregate。

从推进步长和路径集合的关系大家看到了什么?我看到了NP问题。在一个给定的问题中,路径步长通常是问题的尺度,比如邮差问题中目的地数。而路径集合,一般来讲和问题尺度集合的幂集等势。求幂集的某一aggregate,正是NP问题的特征。

从步步推进,步步展开,步步分叉的推进方法上,我还看到了nondeterministic
Turing machine (NTM) 的实现方法。NTM是一个理论模型,它提出的时间比较早,是在编译理论初步形成的时候。从这个名字上看,当时还有一些confusion。它是纯理想实
验不可操作的吗?不是。它就是图灵机整体状态路径在每一步分叉。

它也是把递归程序展开成非递归程序的方法。递归程序在形式上关注的是一条路径,
single path,因此是深度优先。而全面展开法关注的是步长,步步推进。

TheMatrix

辅以一个经典程序说明。跳马问题。

在一个5X5的棋盘上,马的初始位置在(0,0),马走日,求马不重复走完棋盘的全部路径集合。

这个问题的尺度是棋盘格数,5X5=25。全部路径的集合和25的排列等势。当然,问题的约束可以除去很多可能。

函数run是递归方法。它形式上关注single path。

函数run2就是全面展开法。它关注步数,在每一步形成的路径上尤其关注最后一步,在那一步之后分叉。很像wave front。又如前锋推进。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 这个词是我发明的,因为我觉得它太形象了。说的是广度优先的树遍历法。我还有几个
: 名字给它。一个叫波前法,借鉴wave front的用法。还有一个我更喜欢的,叫前锋推进
: 法。当然,各有千秋。
: 它从起始条件出发,步步推进,步步全面展开,最后得到的是全部可能路径的集合。当
: 然,还可以对集合求值,比如求最小值,或者其他aggregate。
: 从推进步长和路径集合的关系大家看到了什么?我看到了NP问题。在一个给定的问题中
: ,路径步长通常是问题的尺度,比如邮差问题中目的地数。而路径集合,一般来讲和问
: 题尺度集合的幂集等势。求幂集的某一aggregate,正是NP问题的特征。
: 从步步推进,步步展开,步步分叉的推进方法上,我还看到了nondeterministic
: Turing machine (NTM) 的实现方法。NTM是一个理论模型,它提出的时间比较早,是在
: ...................

m
minquan

你这种说法有点像行列式的全面展开式,相较于递归式

这么展开除了平行计算之外,有好处吗?
TheMatrix

差不多。并行计算,这是一个用途。不过现在还说不上用途,这是一个理解事物运行的模型。量子计算,人脑的搜索和判定算法,我觉得都是以这种方式展开。步长对应着精度,人脑可以自由地停在某一精度上。

【 在 minquan (三民主义) 的大作中提到: 】
: 你这种说法有点像行列式的全面展开式,相较于递归式
: 这么展开除了平行计算之外,有好处吗?

SnowDen

有点意思。
TheMatrix


来看一下简化的Deterministic Turing Machine (DTM) 和 Nondeterministic Turing Machine (NTM)。

假定alphabet有两个,0和1。纸带无穷长,只能左右移动,记为0和1。内部状态集合为S,状态数至少为2。这就是最简化的图灵机模型。什么是“一个图灵机”?图灵机是一套规则,对于纸带当前数字和内部当前状态的组合,给以一个左右移动纸带并写入0或1的指令,以及内部状态的变化。也就是说图灵机是一个函数,它的定义域是[2S],即
alphabet数乘以内部状态
集合,它的值域是[2X2XS]=[4S],即左右移加写入0/1的组合。所以一个图灵机表示为 T:[
2S]-->[4S]。

固定一个内部状态数S,可以有多少种不同的图灵机?也就是问有多少种不同的函数,
从[2S]-->[4S]。显然,(4S)^(2S)种。每一种可以编号,叫做一个图灵机的哥德尔数。

以上说的是DTM。

NTM的模型可以这样给出,[2S]本身不足以决定[4S]了,要加一个问题尺度集合,记为Q。也就是说[2S] x Q -->[4S]。这里有个假设,即存在Q。固定S和Q,总共有多少种NTM?(4S)^(2S×Q)=((4S)^Q)^(2S)。这就是指数增长的来源。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 这个词是我发明的,因为我觉得它太形象了。说的是广度优先的树遍历法。我还有几个
: 名字给它。一个叫波前法,借鉴wave front的用法。还有一个我更喜欢的,叫前锋推进
: 法。当然,各有千秋。
: 它从起始条件出发,步步推进,步步全面展开,最后得到的是全部可能路径的集合。当
: 然,还可以对集合求值,比如求最小值,或者其他aggregate。
: 从推进步长和路径集合的关系大家看到了什么?我看到了NP问题。在一个给定的问题中
: ,路径步长通常是问题的尺度,比如邮差问题中目的地数。而路径集合,一般来讲和问
: 题尺度集合的幂集等势。求幂集的某一aggregate,正是NP问题的特征。
: 从步步推进,步步展开,步步分叉的推进方法上,我还看到了nondeterministic
: Turing machine (NTM) 的实现方法。NTM是一个理论模型,它提出的时间比较早,是在
: ...................

TheMatrix

指令应该包括左右移动纸带写入0/1,以及内部状态的变化。所以值域是4S,前面写成4,太快了,改过来了。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 来看一下简化的Deterministic Turing Machine (DTM) 和 Nondeterministic
Turing
: Machine (NTM)。
: 假定alphabet有两个,0和1。纸带无穷长,只能左右移动,记为0和1。内部状态集合为
: S,状态数至少为2。这就是最简化的图灵机模型。什么是“一个图灵机”?图灵机是一
: 套规则,对于纸带当前数字和内部当前状态的组合,给以一个左右移动纸带并写入0
或1
: 的指令,以及内部状态的变化。也就是说图灵机是一个函数,它的定义域是[2S],即: alphabet数乘以内部状态
: 集合,它的值域是[2X2XS]=[4S],即左右移加写入0/1的组合。所以一个图灵机表示

: T:[
: 2S]-->[4S]。
: ...................

c
coho18

你发明这个方法,是受到你老婆和党委书记做爱场景的启发,遍历全身, 全面展开

盹盹盹

【在TheMatrix(TheMatrix)的大作中提到:】
:这个词是我发明的,因为我觉得它太形象了。说的是广度优先的树遍历法。我还有几个名字给它。一个叫波前法,借鉴wave front的用法。还有一个我更喜欢的,叫前锋推进法。当然,各有千秋。
:它从起始条件出发,步步推进,步步全面展开,最后得到的是全部可能路径的集合。当然,还可以对集合求值,比如求最小值,或者其他aggregate。
:从推进步长和路径集合的关系大家看到了什么?我看到了NP问题。在一个给定的问题中,路径步长通常是问题的尺度,比如邮差问题中目的地数。而路径集合,一般来讲和问题尺度集合的幂集等势。求幂集的某一aggregate,正是NP问题的特征。
:从步步推进,步步展开,步步分叉的推进方法上,我还看到了nondeterministic
:Turing machine (NTM) 的实现方法。NTM是一个理论模型,它提出的时间比较早,是在编译理论初步形成的时候。从这个名字上看,当时还有一些confusion。它是纯理想实
:验不可操作的吗?不是。它就是图灵机整体状态路径在每一步分叉。
:它也是把递归程序展开成非递归程序的方法。递归程序在形式上关注的是一条路径,:single path,因此是深度优先。而全面展开法关注的是步长,步步推进。
:☆ 发自 iPhone 买买提 1.24.11
verdelite

又发明新词。先谈谈和宽度优先breadth first有什么不同。