全面展开法

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

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

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

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

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

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

在一个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是一个理论模型，它提出的时间比较早，是在
: ...................

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

这么展开除了平行计算之外，有好处吗？

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

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

有点意思。

来看一下简化的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是一个理论模型，它提出的时间比较早，是在
: ...................

指令应该包括左右移动纸带写入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]。
: ...................

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

盹盹盹

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

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