T*******x
发帖数: 8565 | 1 这个词是我发明的，因为我觉得它太形象了。说的是广度优先的树遍历法。我还有几个
名字给它。一个叫波前法，借鉴wave front的用法。还有一个我更喜欢的，叫前锋推进
法。当然，各有千秋。
它从起始条件出发，步步推进，步步全面展开，最后得到的是全部可能路径的集合。当
然，还可以对集合求值，比如求最小值，或者其他aggregate。
从推进步长和路径集合的关系大家看到了什么？我看到了NP问题。在一个给定的问题中
，路径步长通常是问题的尺度，比如邮差问题中目的地数。而路径集合，一般来讲和问
题尺度集合的幂集等势。求幂集的某一aggregate，正是NP问题的特征。
从步步推进，步步展开，步步分叉的推进方法上，我还看到了nondeterministic
Turing machine (NTM) 的实现方法。NTM是一个理论模型，它提出的时间比较早，是在
编译理论初步形成的时候。从这个名字上看，当时还有一些confusion。它是纯理想实
验不可操作的吗？不是。它就是图灵机整体状态路径在每一步分叉。
它也是把递归程序展开成非递归程序的方法。递归程序在形式上关注的是一条路径，
single path，因此是深度优先。而全面展开法关注的是步长，步步推进。 |
T*******x
发帖数: 8565 | 2 辅以一个经典程序说明。跳马问题。
在一个5X5的棋盘上，马的初始位置在(0,0)，马走日，求马不重复走完棋盘的全部路径
集合。
这个问题的尺度是棋盘格数，5X5=25。全部路径的集合和25的排列等势。当然，问题的
约束可以除去很多可能。
函数run是递归方法。它形式上关注single path。
函数run2就是全面展开法。它关注步数，在每一步形成的路径上尤其关注最后一步，在
那一步之后分叉。很像wave front。又如前锋推进。
【在 T*******x 的大作中提到】
: 这个词是我发明的，因为我觉得它太形象了。说的是广度优先的树遍历法。我还有几个
: 名字给它。一个叫波前法，借鉴wave front的用法。还有一个我更喜欢的，叫前锋推进
: 法。当然，各有千秋。
: 它从起始条件出发，步步推进，步步全面展开，最后得到的是全部可能路径的集合。当
: 然，还可以对集合求值，比如求最小值，或者其他aggregate。
: 从推进步长和路径集合的关系大家看到了什么？我看到了NP问题。在一个给定的问题中
: ，路径步长通常是问题的尺度，比如邮差问题中目的地数。而路径集合，一般来讲和问
: 题尺度集合的幂集等势。求幂集的某一aggregate，正是NP问题的特征。
: 从步步推进，步步展开，步步分叉的推进方法上，我还看到了nondeterministic
: Turing machine (NTM) 的实现方法。NTM是一个理论模型，它提出的时间比较早，是在
|
m*****n
发帖数: 3575 | 3 你这种说法有点像行列式的全面展开式，相较于递归式
这么展开除了平行计算之外，有好处吗？ |
T*******x
发帖数: 8565 | 4 差不多。并行计算，这是一个用途。不过现在还说不上用途，这是一个理解事物运行的
模型。量子计算，人脑的搜索和判定算法，我觉得都是以这种方式展开。步长对应着精
度，人脑可以自由地停在某一精度上。
【在 m*****n 的大作中提到】
: 你这种说法有点像行列式的全面展开式，相较于递归式
: 这么展开除了平行计算之外，有好处吗？
|
S*****n
发帖数: 4185 | |
T*******x
发帖数: 8565 | 6 来看一下简化的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)。这就是指数增长的来源。
【在 T*******x 的大作中提到】
: 这个词是我发明的，因为我觉得它太形象了。说的是广度优先的树遍历法。我还有几个
: 名字给它。一个叫波前法，借鉴wave front的用法。还有一个我更喜欢的，叫前锋推进
: 法。当然，各有千秋。
: 它从起始条件出发，步步推进，步步全面展开，最后得到的是全部可能路径的集合。当
: 然，还可以对集合求值，比如求最小值，或者其他aggregate。
: 从推进步长和路径集合的关系大家看到了什么？我看到了NP问题。在一个给定的问题中
: ，路径步长通常是问题的尺度，比如邮差问题中目的地数。而路径集合，一般来讲和问
: 题尺度集合的幂集等势。求幂集的某一aggregate，正是NP问题的特征。
: 从步步推进，步步展开，步步分叉的推进方法上，我还看到了nondeterministic
: Turing machine (NTM) 的实现方法。NTM是一个理论模型，它提出的时间比较早，是在
|
T*******x
发帖数: 8565 | 7 指令应该包括左右移动纸带写入0/1，以及内部状态的变化。所以值域是4S，前面写成4
，太快了，改过来了。
Turing
或1
为
【在 T*******x 的大作中提到】
: 来看一下简化的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]。
|
v*******e
发帖数: 11604 | 8 又发明新词。先谈谈和宽度优先breadth first有什么不同。 |
T*******x
发帖数: 8565 | 9 最后这句话不对。步长对应着精度，多走一步就多一个量级的精度，this is too good
to be true，这实际上是P算法的特征。
人脑的逻辑思维部分应该不是量子计算，一个没有P算法的问题人脑也没办法。反过来
人脑有办法快速估计的问题，我觉得就是某种P算法，计算机如果还没有做到的话，应
该是我们还没有把人脑的算法观察清楚，这是个观察问题。
量子计算倒的确真的是全面展开，而且是展开到底，而不是说展开到一定步长就够了。
但是量子计算肯定也会遇到问题，当qbit数多了以后，应该是精度或测量方面的问题。
但是有可能走入小型化。
【在 T*******x 的大作中提到】
: 差不多。并行计算，这是一个用途。不过现在还说不上用途，这是一个理解事物运行的
: 模型。量子计算，人脑的搜索和判定算法，我觉得都是以这种方式展开。步长对应着精
: 度，人脑可以自由地停在某一精度上。
|
T*******x
发帖数: 8565 | 10 没什么不同。这个属于换个角度看问题，或者指出联系。
【在 v*******e 的大作中提到】
: 又发明新词。先谈谈和宽度优先breadth first有什么不同。
|
v*******e
发帖数: 11604 | 11
没什么不同就不要发明新词啊。
【在 T*******x 的大作中提到】
: 没什么不同。这个属于换个角度看问题，或者指出联系。
|
T*******x
发帖数: 8565 | 12 我不是说了嘛，换个角度看问题。
【在 v*******e 的大作中提到】
:
: 没什么不同就不要发明新词啊。
|
