Creative Commons License
本Blog采用 知识共享署名-非商业性使用-禁止演绎 3.0 Unported许可协议 进行许可。 —— Fox <游戏人生>

游戏人生

游戏人生 != ( 人生 == 游戏 )
站点迁移至:http://www.yulefox.com。请订阅本博的朋友将RSS修改为http://feeds.feedburner.com/yulefox
posts - 62, comments - 508, trackbacks - 0, articles - 7

以前在学习非数值算法的时候,曾经了解过动态规划算法(Dynamic programming),以下是对Wikipedia动态规划的翻译,图也是Wikipedia上的,仓促行文,不到之处,请方家指正。

这篇文章的术语实在是太多了,所以我在文中加入了少量注释,一律以粗斜体注明。

本文的不足之处将随时修正,MIT的《Introduction to Algorithms》第15章是专门讲动态规划的。

_____________________________________________________________

动态规划

在数学与计算机科学领域,动态规划用于解决那些可分解为重复子问题(overlapping subproblems,想想递归求阶乘吧)并具有最优子结构(optimal substructure,想想最短路径算法)(如下所述)的问题,动态规划比通常算法花费更少时间。

上世纪40年代,Richard Bellman最早使用动态规划这一概念表述通过遍历寻找最优决策解问题的求解过程。1953年,Richard Bellman将动态规划赋予现代意义,该领域被IEEE纳入系统分析和工程中。为纪念Bellman的贡献,动态规划的核心方程被命名为贝尔曼方程,该方程以递归形式重申了一个优化问题。

在“动态规划”(dynamic programming)一词中,programming与“计算机编程”(computer programming)中的programming并无关联,而是来自“数学规划”(mathematical programming),也称优化。因此,规划是指对生成活动的优化策略。举个例子,编制一场展览的日程可称为规划。 在此意义上,规划意味着找到一个可行的活动计划。

  • 概述

 

图1 使用最优子结构寻找最短路径:直线表示边,波状线表示两顶点间的最短路径(路径中其他节点未显示);粗线表示从起点到终点的最短路径。

不难看出,start到goal的最短路径由start的相邻节点到goal的最短路径及start到其相邻节点的成本决定。

 

 

最优子结构即可用来寻找整个问题最优解的子问题的最优解。举例来说,寻找上某顶点到终点的最短路径,可先计算该顶点所有相邻顶点至终点的最短路径,然后以此来选择最佳整体路径,如图1所示。

一般而言,最优子结构通过如下三个步骤解决问题:

a) 将问题分解成较小的子问题;

b) 通过递归使用这三个步骤求出子问题的最优解;

c) 使用这些最优解构造初始问题的最优解。

子问题的求解是通过不断划分为更小的子问题实现的,直至我们可以在常数时间内求解。

 

 

图2 Fibonacci序列的子问题示意图:使用有向无环图(DAG, directed acyclic graph)而非表示重复子问题的分解。

为什么是DAG而不是树呢?答案就是,如果是树的话,会有很多重复计算,下面有相关的解释。

 

 

一个问题可划分为重复子问题是指通过相同的子问题可以解决不同的较大问题。例如,在Fibonacci序列中,F3 = F1 + F2和F4 = F2 + F3都包含计算F2。由于计算F5需要计算F3和F4,一个比较笨的计算F5的方法可能会重复计算F2两次甚至两次以上。这一点对所有重复子问题都适用:愚蠢的做法可能会为重复计算已经解决的最优子问题的解而浪费时间。

为避免重复计算,可将已经得到的子问题的解保存起来,当我们要解决相同的子问题时,重用即可。该方法即所谓的缓存(memoization,而不是存储memorization,虽然这个词亦适合,姑且这么叫吧,这个单词太难翻译了,简直就是可意会不可言传,其意义是没计算过则计算,计算过则保存)。当我们确信将不会再需要某一解时,可以将其抛弃,以节省空间。在某些情况下,我们甚至可以提前计算出那些将来会用到的子问题的解。

总括而言,动态规划利用:

1) 重复子问题

2) 最优子结构

3) 缓存

动态规划通常采用以下两种方式中的一种两个办法:

自顶向下:将问题划分为若干子问题,求解这些子问题并保存结果以免重复计算。该方法将递归和缓存结合在一起。

自下而上:先行求解所有可能用到的子问题,然后用其构造更大问题的解。该方法在节省堆栈空间和减少函数调用数量上略有优势,但有时想找出给定问题的所有子问题并不那么直观。

为了提高按名传递(call-by-name,这一机制与按需传递call-by-need相关,复习一下参数传递的各种规则吧,简单说一下,按名传递允许改变实参值)的效率,一些编程语言将函数的返回值“自动”缓存在函数的特定参数集合中。一些语言将这一特性尽可能简化(如SchemeCommon LispPerl),也有一些语言需要进行特殊扩展(如C++,C++中使用的是按值传递和按引用传递,因此C++中本无自动缓存机制,需自行实现,具体实现的一个例子是Automated Memoization in C++)。无论如何,只有指称透明(referentially transparent,指称透明是指在程序中使用表达式、函数本身或以其值替换对程序结果没有任何影响)函数才具有这一特性。

  • 例子

1. Fibonacci序列

寻找Fibonacci序列中第n个数,基于其数学定义的直接实现:

   function fib(n)
       if n = 0
           return 0
       else if n = 1
           return 1
       return fib(n-1) + fib(n-2)

如果我们调用fib(5),将产生一棵对于同一值重复计算多次的调用树:

  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

特别是,fib(2)计算了3次。在更大规模的例子中,还有更多fib的值被重复计算,将消耗指数级时间。

现在,假设我们有一个简单的映射(map)对象m,为每一个计算过的fib及其返回值建立映射,修改上面的函数fib,使用并不断更新m。新的函数将只需O(n)的时间,而非指数时间:

   var m := map(0 → 1, 1 → 1)
   function fib(n)
       if map m does not contain key n
           m[n] := fib(n-1) + fib(n-2)
       return m[n]

这一保存已计算出的数值的技术即被称为缓存,这儿使用的是自顶向下的方法:先将问题划分为若干子问题,然后计算和存储值。

自下而上的方法中,我们先计算较小的fib,然后基于其计算更大的fib。这种方法也只花费线性(O(n))时间,因为它包含一个n-1次的循环。然而,这一方法只需要常数(O(1))的空间,相反,自顶向下的方法则需要O(n)的空间来储存映射关系。

   function fib(n)
       var previousFib := 0, currentFib := 1
       if n = 0
           return 0
       else if n = 1
           return 1
       repeat n-1 times
           var newFib := previousFib + currentFib
           previousFib := currentFib
           currentFib  := newFib
       return currentFib

在这两个例子,我们都只计算fib(2)一次,然后用它来计算fib(3)和fib(4),而不是每次都重新计算。

2. 一种平衡的0-1矩阵

考虑n*n矩阵的赋值问题:只能赋0和1,n为偶数,使每一行和列均含n/2个0及n/2个1。例如,当n=4时,两种可能的方案是:

+ - - - - +             + - - - - +
| 0 1 0 1 |             | 0 0 1 1 |
| 1 0 1 0 |             | 0 0 1 1 |
| 0 1 0 1 |             | 1 1 0 0 |
| 1 0 1 0 |             | 1 1 0 0 |
+ - - - - +             + - - - - +

问:对于给定n,共有多少种不同的赋值方案。

至少有三种可能的算法来解决这一问题:穷举法(brute force)、回溯法(backtracking)及动态规划(dynamic programming)。穷举法列举所有赋值方案,并逐一找出满足平衡条件的方案。由于共有C(n, n/2)^n种方案(在一行中,含n/2个0及n/2个1的组合数为C(n,n/2),相当于从n个位置中选取n/2个位置置0,剩下的自然是1),当n=6时,穷举法就已经几乎不可行了。回溯法先将矩阵中部分元素置为0或1,然后检查每一行和列中未被赋值的元素并赋值,使其满足每一行和列中0和1的数量均为n/2。回溯法比穷举法更加巧妙一些,但仍需遍历所有解才能确定解的数目,可以看到,当n=8时,该题解的数目已经高达116963796250。动态规划则无需遍历所有解便可确定解的数目(意思是划分子问题后,可有效避免若干子问题的重复计算)。

通过动态规划求解该问题出乎意料的简单。考虑每一行恰含n/2个0和n/2个1的k*n(1<=k<=n)的子矩阵,函数f根据每一行的可能的赋值映射为一个向量,每个向量由n个整数对构成。向量每一列对应的一个整数对中的两个整数分别表示该列上该行以下已经放置的0和1的数量。该问题即转化为寻找f((n/2,n/2),(n/2,n/2),...,(n/2,n/2))(具有n个参数或者说是一个含n个元素的向量)的值。其子问题的构造过程如下:

1) 最上面一行(第k行)具有C(n, n/2)种赋值;

2) 根据最上面一行中每一列的赋值情况(为0或1),将其对应整数对中相应的元素值减1;

3) 如果任一整数对中的任一元素为负,则该赋值非法,不能成为正确解;

4) 否则,完成对k*n的子矩阵中最上面一行的赋值,取k=k-1,计算剩余的(k-1)*n的子矩阵的赋值;

5) 基本情况是一个1*n的细小的子问题,此时,该子问题的解的数量为0或1,取决于其向量是否是n/2个(0, 1)和n/2个(1, 0)的排列。

例如,在上面给出的两种方案中,向量序列为:

((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4
  0      1      0      1              0       0       1      1

((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3
  1      0      1      0              0      0      1      1

((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2
  0      1      0      1              1      1      0      0

((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1
  1      0      1      0              1      1      0      0

((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0))

动态规划在此的意义在于避免了相同f的重复计算,更进一步的,上面着色的两个f,虽然对应向量不同,但f的值是相同的,想想为什么吧:D

该问题解的数量(序列a058527在OEIS)是1, 2, 90, 297200, 116963796250, 6736218287430460752, ...

下面的外部链接中包含回溯法的Perl源代码实现,以及动态规划法的MAPLE和C语言的实现。

3. 棋盘

考虑n*n的棋盘及成本函数C(i,j),该函数返回方格(i,j)相关的成本。以5*5的棋盘为例:

5 | 6 7 4 7 8
4 | 7 6 1 1 4
3 | 3 5 7 8 2
2 | 2 6 7 0 2
1 | 7 3 5 6 1
- + - - - - -
  | 1 2 3 4 5

可以看到:C(1,3)=5

从棋盘的任一方格的第一阶(即行)开始,寻找到达最后一阶的最短路径(使所有经过的方格的成本之和最小),假定只允许向左对角、右对角或垂直移动一格。

5 |
4 |
3 |
2 |   x x x
1 |     o
- + - - - - -
  | 1 2 3 4 5

该问题展示了最优子结构。即整个问题的全局解依赖于子问题的解。定义函数q(i,j),令:q(i,j)表示到达方格(i,j)的最低成本。

如果我们可以求出第n阶所有方格的q(i,j)值,取其最小值并逆向该路径即可得到最短路径。

记q(i,j)为方格(i,j)至其下三个方格((i-1,j-1)、(i-1,j)、(i-1,j+1))最低成本与c(i,j)之和,例如:

5 |
4 |     A
3 |   B C D
2 |
1 |
- + - - - - -
  | 1 2 3 4 5

q(A) = min(q(B),q(C),q(D)) + c(A)

定义q(i,j)的一般形式:

            |-  inf.                                                  j<1 or j>n
q(i,j) = -+-  c(i,j)                                                i=1
            |-  min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)   otherwise.

方程的第一行是为了保证递归可以退出(处理边界时只需调用一次递归函数)。第二行是第一阶的取值,作为计算的起点。第三行的递归是算法的重要组成部分,与例子ABCD类似。从该定义我们可以直接给出计算q(i,j)的简单的递归代码。在下面的伪代码中,n表示棋盘的维数,C(i,j)是成本函数,min()返回一组数的最小值:

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i,j)
    else
        return min(minCost(i-1,j-1),minCost(i-1,j),minCost(i-1,j+1))+c(i,j)

需要指出的是,minCost只计算路径成本,并不是最终的实际路径,二者相去不远。与Fibonacci数相似,由于花费大量时间重复计算相同的最短路径,这一方式慢的恐怖。不过,如果采用自下而上法,使用二维数组q[i,j]代替函数minCost,将使计算过程快得多。我们为什么要这样做呢?选择保存值显然比使用函数重复计算相同路径要简单的多。

我们还需要知道实际路径。路径问题,我们可以通过另一个前任数组p[i,j]解决。这个数组用于描述路径,代码如下:

function computeShortestPathArrays()
     for x from 1 to n
         q[1, x] := c(1, x)
     for y from 1 to n
         q[y, 0]     := infinity
         q[y, n + 1] := infinity
     for y from 2 to n
         for x from 1 to n
             m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
             q[y, x] := m + c(y, x)
             if m = q[y-1, x-1]
                 p[y, x] := -1
             else if m = q[y-1, x]
                 p[y, x] :=  0
             else
                 p[y, x] :=  1

剩下的求最小值和输出就比较简单了:

function computeShortestPath()
     computeShortestPathArrays()
     minIndex := 1
     min := q[n, 1]
     for i from 2 to n
         if q[n, i] < min
             minIndex := i
             min := q[n, i]
     printPath(n, minIndex)

function printPath(y, x)
     print(x)
     print("<-")
     if y = 2
         print(x + p[y, x])
     else
         printPath(y-1, x + p[y, x])

4. 序列比对

序列比对是动态规划的一个重要应用。序列比对问题通常是使用编辑操作(替换、插入、删除一个要素等)进行序列转换。每次操作对应不同成本,目标是找到编辑序列的最低成本。

可以很自然地想到使用递归解决这个问题,序列AB的最优编辑通过以下措施之一实现:

插入B的第一个字符,对AB的剩余序列进行最优比对;

删去A的第一个字符,对AB进行最优比对;

B的第一个字符替换A的第一个字符,对A的剩余序列和B进行最优比对。

局部比对可在矩阵中列表表示,单元(i,j)表示A[1..i]到b[1..j]最优比对的成本。单元(i,j)的成本计算可通过累加相邻单元的操作成本并选择最优解实现。至于序列比对的不同实现算法,参见Smith-WatermanNeedleman-Wunsch

对序列比对的话题并不熟悉,更多的话也无从谈起,有熟悉的朋友倒是可以介绍一下。

  • 应用动态规划的算法

1) 许多字符串操作算法如最长公共子列最长递增子列最长公共字串

2) 将动态规划用于的树分解,可以有效解决有界树宽图生成树等许多与图相关的算法问题;

3) 决定是否及如何可以通过某一特定上下文无关文法产生给定字符串的Cocke-Younger-Kasami (CYK)算法;

4) 计算机国际象棋转换表驳斥表的使用;

5) Viterbi算法(用于隐式马尔可夫模型);

6) Earley算法(一类图表分析器);

7) Needleman-Wunsch及其他生物信息学中使用的算法,包括序列比对结构比对RNA结构预测;

8) Levenshtein距离(编辑距离);

9) 弗洛伊德最短路径算法;

10) 连锁矩阵乘法次序优化;

11) 子集求和背包问题分治问题的伪多项式时间算法;

12) 计算两个时间序列全局距离的动态时间规整算法;

13) 关系型数据库的查询优化的Selinger(又名System R)算法;

14) 评价B样条曲线的De Boor算法

15) 用于解决板球运动中断问题的Duckworth-Lewis方法;

16) 价值迭代法求解马尔可夫决策过程

17) 一些图形图像边缘以下的选择方法,如“磁铁”选择工具在Photoshop

18) 间隔调度

19) 自动换行

20) 巡回旅行商问题又称邮差问题或货担郎问题);

21) 分段最小二乘法

22) 音乐信息检索跟踪。

对于这些算法应用,大多未曾接触,甚至术语翻译的都有问题,鉴于本文主要在于介绍动态规划,所以仓促之中,未及查证。

  • 相关

1) 贝尔曼方程

2) 马尔可夫决策过程

3) 贪心算法

  • 参考
  • Adda, Jerome, and Cooper, Russell, 2003. Dynamic Economics. MIT Press. An accessible introduction to dynamic programming in economics. The link contains sample programs.
  • Richard Bellman, 1957, Dynamic Programming, Princeton University Press. Dover paperback edition (2003), ISBN 0486428095.
  • Bertsekas, D. P., 2000. Dynamic Programming and Optimal Control, Vols. 1 & 2, 2nd ed. Athena Scientific. ISBN 1-886529-09-4.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001. Introduction to Algorithms, 2nd ed. MIT Press & McGraw-Hill. ISBN 0-262-03293-7. Especially pp. 323–69.
  • Giegerich, R., Meyer, C., and Steffen, P., 2004, "A Discipline of Dynamic Programming over Sequence Data," Science of Computer Programming 51: 215-263.
  • Nancy Stokey, and Robert E. Lucas, with Edward Prescott, 1989. Recursive Methods in Economic Dynamics. Harvard Univ. Press.
  • S. P. Meyn, 2007. Control Techniques for Complex Networks, Cambridge University Press, 2007.
    • 外部链接

    _____________________________________________________________

    关于动态规划,这只是一篇译文,后面将根据实际问题具体写点动态规划的应用。

  • posted @ 2008-05-07 20:43 Fox 阅读(31026) | 评论 (9)编辑 收藏

    Author: Fox

    首先声明:本人没有解决掉这个问题。

    相比第一道让CPU占用率曲线听你指挥对Windows系统中CPU占有率概念的考察和对API的使用,以及第二道中国象棋将帅问题对抽象建模的考察。这道题目才算是一道算法题吧?之前那两道尤其是中国象棋将帅问题总有点脑筋急转弯的味道。

    题目:星期五的晚上,一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢?自然是算法问题。有个同事说:

    “我以前在餐馆打工,顾客经常点非常多的烙饼。店里的饼大小不一,我习惯在到达顾客饭桌前,把一摞饼按照大小次序摆好——小的在上面,大的在下面。由于我一只手托着盘子,只好用另一只手,一次抓住最上面的几块饼,把它们上下颠倒个个儿,反复几次之后,这摞烙饼就排好序了。

    我后来想,这实际上是个有趣的排序问题:假设有n块大小不一的烙饼,那最少要翻几次,才能达到最后大小有序的结果呢?

    你能否写出一个程序,对于n块大小不一的烙饼,输出最优化的翻饼过程呢?

    排序问题是数据结构和算法中比较重要的一个了,之前在一篇被同事成为标题党的文章中因为提到排序中关于(非)稳定排序的概念还被很多TX鄙视了一番,甚至引来人身攻击,现在想来都有些后怕。

    这道题目一眼看上去最先让我想到的居然是那道经典的汉诺塔(Tower of Hanoi)问题(当然,汉诺塔不算排序问题)。

    1) 相似点★:

    a. 都要不断调整位置,最终实现从小到大排好;

    b. 都要借助中间量进行调整。

    2) 不同处★:

    a. 汉诺塔有多出来的两根针,翻烙饼只有一只手,明确说明没有第三只手;

    b. 汉诺塔一次只能移动一个,翻烙饼没限制;

    c. 汉诺塔要保证小的始终在上面,翻烙饼没限制;

    d. 汉诺塔移动之前就有序,所以其移动次数是固定的,算法的逻辑也固定(不管是递归还是栈操作),翻烙饼没有这个前提。

    3) 把题目用程序语言描述一下吧★:

    a. Input : n.

    b. Process : generate n random number 0-(n-1), sortting.

    c. Output : 0, 1, ..., n-1, and move times num.

    4) 存储结构★★★:

    我最开始想到的是:这一摞烙饼其实就是一个双链表,每翻一次相当于将头节点H与某非头节点N进行如下变换:

    H->next = N->next

    N->prior = H->prior = NULL

    N->next->prior = H

    如果使用普通的双链表,这儿就有一个很明显的问题,H和N之间的所有节点(如果有的话)的前趋prior和后继next互换了,对于n比较大的情况,这个操作明显浪费时间啊(交换前趋prior和后继next和题目要求的翻几次似乎也没有关系吧?只是我作为一个一线的Coder考虑的太具体了)。如果摒弃前趋和后继的概念,又该怎样描述呢?

    唐朝禅宗大师青原行思曾说:参禅之初,看山是山,看水是水;禅有悟时,看山不是山,看水不是水;禅中彻悟,看山仍然山,看水仍然是水

    俗:日,扯那么多,什么意思?

    师:前趋不是前趋,后继不是后继。

    俗:日,前趋不是前趋,难道是后继吗?

    师:然也。

    Fox:O, my God!整点实际的吧!翻转一次之后,前趋视为后继,后继视为前趋,第奇数次翻转的前趋是后继,第偶数次翻转的后继是前趋。

    整个链表的形态如下:

    H:Head, F:First, G:F's next, B:C's prior, C:Change, D, C's next, L:Last.

    H<==>F<==>G<=...=>B<==>C<==>D<=...=>L

    F与C交换的操作如下(Word、PS画图),n表示next,p表示prior:

    这里只需要修改F、D节点的prior,H、C节点的next,其他节点不变。

    后面想了一下,这种方式很难在不添加flag或者对换n、p的情况下正常操作,没有找到好的方法L如果你有好的方法不妨告诉我

    最后只好作罢,何苦呢?直接使用数组就完了嘛J!既然是数组,除了翻转移动麻烦一点,理解和操作还是很容易的。

    果然不是搞数学、算法出身的,一上来考虑的就是如何存储^.^'''',而不是算法本身。

    更可笑的是,扯了半天,最后居然还是用数组

    5) 算法分析★★★★★:

    冒泡排序思想:

    最关键的是要抽象出随机数列特征(含当前和移动后数列特征的抽象),并尽量使每一次翻转有效(所谓有效,即尽量保证每一次操作都向最后的有序靠近而非背离 )。

    师:要使大头在后,应使大头在后。

    俗:日,这是什么狗屁逻辑?

    师:因果。在前既是在后。

    俗:USA, CNN(操你娘)。

    师:翻转。既不在前,也不在后,使之在前,使之在后。

    俗:日,什么东西?既不在前,也不在后,不前不后,难道在中间啊?

    师:然也。

    Fox:O, my God!整点实际的吧!整个过程分为n轮,在第i(i=0, 1, ..., n-1)轮:

    a. 找到大头n-i,是否有序?是,转g;

    b. 是否大头在后?是,转f;

    c. 是否大头在前?是,转e;

    d. 将队头(第一个元素)与大头n-i对调(别忘了是翻转,中间元素也变序了),++times

    e. 将队头n-i与第n-i个元素对调,++times

    f. ++i,转a;

    g. 输出序列(0, 1, ..., n)和翻转次数times;OVER:D。

    快速排序思想:

    在最开始的时候,我就想到使用快速排序的思想,先使整个数列局部有序,最后调整使全部有序。悲哀的是,在我考虑 4 3 1 2这个数列的时候,我断定还要通过上面的方式重新像冒泡排序一样重新来过,立即放弃想法,于是给了上面的思路,而且坚定的认为这个方法已经很好。结果,下午GR告诉我他的反例:4 3 1 2 --> 2 1 3 4|--> 1 2| 3 4,“|”表示从该处翻转。

    我必须承认,这才是好的方法,我过分拘泥于不去改动已经有序的部分。然而,这家伙只知道反驳我,却无法给出算法。

    我只好自己重新考虑局部有序之后的问题。

    十分钟后,我有了如下的答案(目前我能想到的最佳答案),但不得不承认,表述算法比给出一种情况对应的解要麻烦的多的多的多,假定A、B满足A==B-1,即A、B为相邻数列(为简单记,元素和数列统称数列)。则A、B的组合类型有8种:B(O)A(O)、B(C)A(O)、B(O)A(C)、B(C)A(C)、A(C)B(O)、A(O)B(O)、A(C)B(C)、A(O)B(C),O表示正向(obverse)C表示逆向(reverse),以1 2 3 4为例:

    B(O)A(O):3 4 1 2<2>B(C)A(O):4 3 1 2<4>B(O)A(C):3 4 2 1<5>、B(C)A(C):4 3 2 1<7>;

    A(C)B(C):2 1 4 3<1>A(O)B(C):1 2 4 3<3>A(C)B(O):2 1 3 4<6>、A(O)B(O):1 2 3 4<8>。

    对应操作规则如下:

    a. 0x0101: B(O)A(O) --> B(C)A(O); 3

    b. 0x0001: B(C)A(O) --> A(C)B(O); 2

    c. 0x0101: B(O)A(C) --> B(C)A(C);1

    d. 0x0000: B(C)A(C):如果当前只剩A、B两个子列,则翻转一次成A(O)B(O)1 2 3 4为最终结果,否则,认为B(C)A(C)可以作为一个逆序有序数列考虑,暂时无需翻转;

    e. 0x1010: A(C)B(C) --> A(O)B(C); 3

    f. 0x1110: A(O)B(C) --> B(O)A(C);  2

    g. 0x1011: A(C)B(O) --> A(O)B(O);1

    h. 0x1111: A(O)B(O):A、B可以作为一个有序数列考虑如果当前只有A、B两个子列,则正序序列A(O)B(O)1 2 3 4为最终结果

    上面规则的制定其实是反向导出的,遵循的原则是,正序有序的A(O)B(O)和逆序有序的B(C)A(C)可以看作一个序列,A(C)B(O)、B(O)A(C)可一步达到,B(C)A(O)、A(O)B(C)可两步达到,B(O)A(O)、A(C)B(C)可三步达到。即对于4个元素,最坏的的A(C)B(C)需要4步(对应于上面的冒泡法却只需要3步L)。而且当元素比较多的时候,记住1、2个有序子列是可行的,但对于完全无序的数列,分析出所有有序子列,既不现实,也无必要。

    修改规则如下:队头无序&&相邻数列有序||队头有序,翻转队头;否则,将队头连同该元素一同翻转

    由此可见,这算法还要改进:

    a. 判断Array[0]是否正序连续(连续个数nNum1),如果nNum1==n,转i,如果nNum1!=1,转c;

    b. 判断Array[0]是否逆序连续(连续个数nNum1),如果nNum1==n,翻转Array,转f;

    c. 从下标nNum1开始查找Array[0]+1(bObserve = true)和Array[0]-1(bObserve = false)的下标nStart2,如果nNum1==nStart2bOrder1==true,转e,如果nNum1!=1,置nEnd2=nStart2

    d. 判断( bObserve == true&&Array[nStart2]+1==Array[nStart2+1] ) || ( bObserve == false&&Array[nStart2]==Array[nStart2+1]+1 ),true则置nEnd2=nStart2,false则置nEnd2=nStart2+1;

    e. 翻转Array[0] to Array[nEnd2],转a;

    f. 输出Arraytimes

    这样来看,改进后的算法竟简单了许多!

    不幸的是:按上面给出的算法翻转合并1 3 5 6 4 8 7 9 2 0:

    1 3 5 6 4 8 7 9| 2| 0

    2 9 7 8 4 6 5| 3| 1 0

    3 5 6| 4| 8 7 9 2 1 0

    4 6| 5| 3 8 7 9 2 1 0

    5 6| 4 3 8 7 9 2 1 0

    6 5 4 3 8| 7| 9 2 1 0

    7 8 3 4 5| 6| 9 2 1 0

    进入死循环了……

    很明显应该是下面这个样子:

    1 3 5 6 4 8 7 9 2| 0

    9 8 7 4 6 5| 3 1 2 0

    5 6 4| 7 8 9 3 1 2 0

    6 5 4 7| 8 9 3 1 2 0

    4 5 6 7 8 9 3| 1 2 0

    3 4 5 6 7 8 9 1 2| 0

    1 9 8 7 6 5 4 3 2| 0

    2 3 4 5 6 7 8 9 1| 0

    9 8 7 6 5 4 3 2 1 0|

    0 1 2 3 4 5 6 7 8 9

    执行9次翻转。算法如何得到呢?

    a. 确定最小无序完整子集SnSn中含n>1个连续数);

    b. 将Sn最前面的有序子集Soo>1)加以考虑,一个子集?两个子集?

    ______________________________________________________________________________

    O, my God!

    这个问题,从前天晚上到现在,思考、分析、抽象了至少有15个小时以上了:

    a. Apr.18th-19th: 23:00 - 01:30

    b. Apr.19th: 11:00 - 13:00

    c. Apr.19th-20th: 22:00 - 05:30

    d. Apr.20th: 11:00 - 15:00

    结果是,到现在无法给出一个最优的翻转算法。一个周末都花在这上面了,准备放弃L

    LP催着我让我回学校,是该回去了!

    posted @ 2008-04-20 14:59 Fox 阅读(3948) | 评论 (13)编辑 收藏

    Author: Fox

    晚上没有加班,打游戏打到9点过,后面就又看了一道《编程之美》的题目《中国象棋将帅问题》。

    题目:下过中国象棋的朋友都知道,双方的“将”和“帅”相隔遥远,并且它们不能照面。在象棋残局中,许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子(如图1-3所示)(为了下面叙述方便,我们约定用A表示“将”,B表示“帅”):

    1-3副本

    AB二子被限制在己方3×3的格子里运动。例如,在如上的表格里,A被正方形{d10, f10, d8, f8}包围,而B被正方形{d3, f3, d1, f1}包围。每一步,AB分别可以横向或纵向移动一格,但不能沿对角线移动。另外,A不能面对B,也就是说,AB不能处于同一纵向直线上(比如Ad10的位置,那么B就不能在d1d2以及d3)。

    请写出一个程序,输出AB所有合法位置。要求在代码中只能使用一个变量。

    在纸上画了半天,Soft从台湾给带的长寿都让我抽完了,总算对得起这会儿工夫……

    我的思路大致如下:

    1) 只能使用一个变量nNum ==> 只能使用一个循环,nNum只能用来表示A、B位置的组合,nNum最大为9×9-1=80;

    2) 如何用nNum表示一个A、B位置的组合?

    下图表示A(红色)B(蓝色)所在位置:

    6 7 8
    3 4 5
    0 1 2
    6 7 8
    3 4 5
    0 1 2

    nNum%9表示A的位置nNum/9表示B的位置,如nNum==15,A==6B==1

    3) 如何确定A、B位置的合法性?

    规则都指定了,合法性的确定也就很简单了:A%3 != B%3。

    OK,剩下的输出就很简单了,为了好看一点,这里希望直接按题目给的图表示出A、B的位置,如:“A:d10, B:e3”,还有颜色:D。

    A的行号:A/3+8;

    A的列号:A%3+d;

    B的行号:B/3+1;

    B的列号:B%3+d;

    代码如下(注释掉的部分只是为了输出更“漂亮”一点):

     

     1 #include <stdio.h>
     2 //#include <windows.h>
     3 
     4 //HANDLE hStdout;
     5 //CONSOLE_SCREEN_BUFFER_INFO csbiInfo;
     6 //WORD wOldColorAttrs;
     7 
     8 int _tmain(int argc, _TCHAR* argv[])
     9 {
    10     //hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
    11     //GetConsoleScreenBufferInfo(hStdout, &csbiInfo);
    12     //wOldColorAttrs = csbiInfo.wAttributes;
    13 
    14     int nNum = 81;    // nNum表示所有位置(含非法),故nNum = 3 * 3 * 3 * 3
    15     while( nNum-- )
    16     {
    17         if( nNum%9%3 != nNum/9%3 )
    18         {
    19             //SetConsoleTextAttribute(hStdout, FOREGROUND_RED | FOREGROUND_INTENSITY);
    20             printf("A:%x%02d ", nNum%9%3+0xd, nNum%9/3+8);
    21             //SetConsoleTextAttribute(hStdout, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    22             printf("B:%x%02d  ", nNum/9%3+0xd, nNum/9/3+1);
    23         }
    24         if!(nNum%9) )
    25             printf("\n");
    26     };
    27     printf("\n");
    28     //SetConsoleTextAttribute(hStdout, wOldColorAttrs);
    29     return 0;
    30 }

    输出:

    点击查看更清晰原图:D

    PS: 刚写完,没有来得及总结更多,急着向LP炫耀。但上面的思路应该比较清晰了,也不管书上的答案了,反正我感觉我这点代码效率应该也不会低到哪儿吧:-)?

    posted @ 2008-04-18 00:26 Fox 阅读(3978) | 评论 (8)编辑 收藏

    Author: Fox

    前两天在买《计算机程序设计艺术》中文版的时候,偶然发现《编程之美》这本书,当时翻了一下,看到“让CPU占用率曲线听你指挥”这样的题目确实让人为之一动。写一段代码,可以让CPU占有率曲线画出平滑的正弦曲线,有点意思:-)。

    当然,最后没有买这本书,虽然我可以肯定这是本好书。

    我从CSDN读书上找到几节,闲来读一读。今天来讨论一下《让CPU占用率曲线听你指挥》。

    题目:写一个程序,让用户来决定Windows任务管理器(Task Manager)的CPU占用率。程序越精简越好,计算机语言不限。例如,可以实现下面三种情况:

    1.    CPU的占用率固定在50%,为一条直线;

    2.    CPU的占用率为一条直线,但是具体占用率由命令行参数决定(参数范围1~ 100);

    3.    CPU的占用率状态是一个正弦曲线。

    在讨论具体实现之前,一个非常重要的问题是:什么是CPU占用率

    编程之美》写道:“在任务管理器的一个刷新周期内,CPU忙(执行应用程序)的时间和刷新周期总时间的比率,就是CPU的占用率,也就是说,任务管理器中显示的是每个刷新周期内CPU占用率的统计平均值。

    打开“Windows 任务管理器”,“性能”中有“CPU使用记录”一项,给出的就是CPU占有率曲线。

    至于一个刷新周期到底是多长,书中似乎没有明确给出,只是说“大约是1秒钟更新一次”,我打开Windows自带的时钟,也感觉大约是1秒钟。

    另外的常识是:

    单核环境下,空死循环会导致100%的CPU占有率。双核环境下,CPU总占有率大约为50%,四核会不会是25%左右呢?(我没有四核,只能猜测了,估计各核间切换也会耗掉点时间,因为我的双核环境并没有出现一核100%,另一核空闲的情况)。

    当CPU整个刷新周期(绝大多数时间)空闲时,CPU占有率趋于0。

    书中给出的正弦实现如下:

    1 #include "Windows.h"
    2 #include "stdlib.h"
    3 #include "math.h" 
    4 
    5 const double SPLIT = 0.01;
    6 const int COUNT = 200;
    7 const double PI = 3.14159265;
    8 const int INTERVAL = 300;
    9 
    10 int _tmain(int argc, _TCHAR* argv[])
    11 {
    12     DWORD busySpan[COUNT];  //array of busy times
    13     DWORD idleSpan[COUNT];  //array of idle times
    14     int half = INTERVAL / 2;
    15     double radian = 0.0;
    16     for(int i = 0; i < COUNT; i++)
    17     {
    18         busySpan[i] = (DWORD)(half + (sin(PI * radian) * half));
    19         idleSpan[i] = INTERVAL - busySpan[i];
    20         radian += SPLIT;
    21     }
    22     DWORD startTime = 0;
    23     int j = 0;
    24     while (true)
    25     {
    26         j = j % COUNT;
    27         startTime = GetTickCount();
    28         while ((GetTickCount() - startTime) <= busySpan[j]) ;
    29         Sleep(idleSpan[j]);
    30         j++;
    31     }
    32     return 0;
    33 }


    在单核环境(P4 2.40)下,其表现还是不错的:

    点击查看大图

    在双核环境(Core2 E4500)下,就有点差强人意不尽人意了:

    点击查看大图

    不过,总还能看出是正弦曲线。

    上面两图的问题:

    1) 单核时曲线不够平滑,是由于QQ等程序占用CPU所致;

    2) 双核时曲线更加抖动,我的理解是除其他程序影响外,由于线程没有固定运行在一个CPU上导致的,后面看到书上提到线程迁移,个人感觉这个叫法欠妥啊,总觉得线程迁移令人费解。

    可以立即想到的是:让进程在指定处理器上运行(处理器亲缘关系),由Windows提供了两个API可以做到这一点:GetCurrentProcessSetProcessAffinityMask的。

    修改之后的代码如下:

    1 #include "Windows.h"
    2 #include "stdlib.h"
    3 #include "math.h" 
    4 
    5 const double SPLIT = 0.01;
    6 const int COUNT = 200;
    7 const double PI = 3.14159265;
    8 const int INTERVAL = 300;
    9 
    10 int _tmain(int argc, _TCHAR* argv[])
    11 {
    12    SetProcessAffinityMask(
    13         GetCurrentProcess(),
    14         0x00000001          //cpu mask
    15         );
    16 
    17     DWORD busySpan[COUNT];  //array of busy times
    18     DWORD idleSpan[COUNT];  //array of idle times
    19     int half = INTERVAL / 2;
    20     double radian = 0.0;
    21     for(int i = 0; i < COUNT; i++)
    22     {
    23         busySpan[i] = (DWORD)(half + (sin(PI * radian) * half));
    24         idleSpan[i] = INTERVAL - busySpan[i];
    25         radian += SPLIT;
    26     }
    27     DWORD startTime = 0;
    28     int j = 0;
    29     while (true)
    30     {
    31         j = j % COUNT;
    32         startTime = GetTickCount();
    33         while ((GetTickCount() - startTime) <= busySpan[j]) ;
    34         Sleep(idleSpan[j]);
    35         j++;
    36     }
    37     return 0;
    38 }


    双核环境(Core2 E4500)修改之后的输出如下:

    点击查看大图

    我理想中的表现是:

    1) 曲线是平滑的,最好不因其他应用程序或操作的执行而改变;

    2) 不管是单核还是双核,峰值皆为100%,谷值为0。

    对于第一点,其实就是保证任一刷新周期中的CPU占有率都可以被精确控制在0-100之间,如果你可以使CPU一直保持50%(而不是近似的上下波动),产生一条平滑的曲线就很easy了。

    问题的关键在于,除了当前你写的程序可以控制,其他程序或操作如何控制?或者说:如何控制CPU的运行情况才是关键之处

    PS: 一晚上老是断网,搞得思路频频被打断,兴致也损了大半。总之,《编程之美》还是值得玩味一把吧:D。

    posted @ 2008-04-17 00:20 Fox 阅读(11090) | 评论 (10)编辑 收藏

    Author: Fox

    本文写给满足以下条件的你(前面4点对应只读的你,后面4点对应只写的你):

    1) 经常阅读别人的Blog,所谓经常,平均每天阅读量在100篇左右;

    2) 不希望花费大量时间在输入网址、鼠标点击和滚动上;

    3) 有固定的阅读习惯,指专注于某一领域、某些特定的Blog;

    4) 尚未使用或刚使用Google Reader并愿意使用Google Reader

    5) 经常更新自己的Blog,所谓经常,平均每月更新1篇或以上;

    2) 不希望花费大量时间在复制、粘贴上;

    3) 希望多与其他人交流;

    4) 尚未使用或刚使用Windows Live Writer并愿意使用Windows Live Writer

    1、For只读的你

    1) 启用Google Reader

    做互联网的就是做互联网的,GoogleGoogle Reader有个帐号就能开启。

    之前写过一个给我GF看的一点东西,这儿对于启用Google Reader不再赘述了,有需要的TX可以看一下或者直接Google

    2) 添加RSS地址

    首先要找到RSS地址,大多数网站提供的Blog,RSS地址都摆在显眼的地方,对于QQ空间这种算不上Blog的Blog来说,QQ空间的RSS也存在,比如,QQ号码为10000的用户,它的RSS就是:http://feeds.qzone.qq.com/cgi-bin/cgi_rss_out?uin=10000

    找到RSS地址之后,就可以将其添加到订阅列表里面了。

    3) 关于OPML

    如果你想共享或备份你的订阅,Google Reader具有“导入/导出”功能,不提供具体的使用方式了,Google吧。

    4) 星标和标签

    看过的好文希望下次再读,就加个星标吧。

    RSS太多,就使用标签吧。

    觉得我这儿写的太简单,就Google吧,或者看看Google Reader的四个常用小技巧

    2、For只写的你

    1) 使用Windows Live Writer

    做软件的就是做软件的,Microsoft的这个Windows Live Writer是要下载安装的。

    具体如何去用,下载下来自然就会用了。

    友情提示:Live Writer的格式、超链接、查看、草稿、帐户、日志、分类列表,都很好用。

    2) 关于CSS

    我不太喜欢Blog的页面太乱,一会儿五号字,一会儿二号字,一会儿宋体,一会儿楷体。

    我喜欢把一些我认为重要的地方链接的内容突出显示,以前没添加CSS的时候,每次都要自己去一个一个的修改链接的字体和颜色,浪费很多时间,如果你的Blog支持CSS,就去看一下怎么使用吧,比如我的CSS就很简单:

    <style type=text/css>
    #top a{ border-bottom:1px dashed; color:white;  }
    #top a:link{ border-bottom:1px dashed; color:white; }
    #top a:hover{ border-bottom:1px dashed; color:white; }
    #top a:visited{ border-bottom:1px dashed; color:white; }
    .post a:link{ border-bottom:1px dashed; color:maroon; }
    .post a:hover{ border-bottom:1px dashed; color:maroon; }
    .post a:visited{ border-bottom:1px dashed; color:maroon; }
    .postbody a{ color:white; background:maroon;  }
    .postbody a:link{ color:white; background:maroon;  }
    .postbody a:hover{ color:white; background:maroon; }
    .postbody a:visited{ color:white; background:maroon; }
    </style>

    我还使用了DevToolBar帮助我确定了CSS。

    3) 添加Google专用的订阅

    我为此还专门PS了一张图片,你可以将下面的代码放到“公告”里面,当然,你想放到哪儿就放到哪儿:

    <br />订阅到:<br />
    <a href="http://fusion.google.com/add?source=atgs&feedurl=http%3A//www.cppblog.com/Fox/Rss.aspx"><img src="http://www.cppblog.com/images/cppblog_com/Fox/6064/o_GoogleRss.jpg" border="0" alt="添加 游戏人生 到 Google 阅读器"></a><br />

    我这儿是有图片的,只有文字的就是这样:

    <br />订阅到:<br />
    <a href="http://fusion.google.com/add?source=atgs&feedurl=http%3A//www.cppblog.com/Fox/Rss.aspx">添加 游戏人生 到 Google 阅读器</a><br />

    上面的www.cppblog.com/Fox/Rss.aspx是我的RSS地址,你要换成你的:-)。

    4) 关于邮箱地址

    不要把邮箱地址直接放在页面上,我之前曾经这样做,后面每天收到不少的垃圾邮件,就取消了,因为这年头,写个邮箱地址搜索器,然后发垃圾邮件太easy了。

    PS: 好用的东西还很多,因为我自己是GFans,所有在工作、学习和生活中使用了Analytics、Gmail、iGoogle、Picasa、Reader、Talk、笔记本、快讯、日历、网页历史记录、网站管理员工具、文件,反正都是免费的,而且用来比较方便,一个帐号可以搞定很多东西:D。

    posted @ 2008-04-15 15:59 Fox 阅读(1809) | 评论 (3)编辑 收藏

    Author: Fox

    John von Neumann说:Any one who considers arithmetical methods of producing random digits is , of course, in a state of sin.

    所以,在讨论算法实现随机数的时候,总是说“伪随机数”。

    现在,应用最广的随机数生成算法是由Derrick Henry Lehmer1951年给出的线性同余法

                  Xn+1 = ( aXn + c ) mod m,  n>=0.

    上一篇伪随机数的论述中,并没有给出X0, a, c, m的取值规则,只是给出了ANSI CMicrosoft Visual C++的实现。

    在这儿我们可以自己先思考一下,我们期望从上式中得到的随机数应该满足:

    1) 上式的输出足够随机,这是最基本的要求;

    2) 上式给出尽量多的输出,越接近m个越好(不可能超过m),即周期尽量长,最好为m,这样才能保证上式满足均匀分布m个数在周期m中各出现一次m个数出现的概率相等);

    3) 上式的生成速度足够快。

    最容易想到的,m的取值为计算机字大小(如2^32或2^64)

    但是这儿有个很严重的问题:Xn低位的随机性很弱。原因如下:

    令d|m, 且

                  Yn = Xn mod d

                  Yn+1 = ( ( aXn + c ) mod m ) mod d

                          = ( aYn + c ) mod d

    上述表达式的意义即:Yn为Xn低k位(d=2^k),这样的Yn序列形成周期为d甚至更短的同余序列。举例说明:d为2^1时,Yn为Xn的最低位(可假定为1或0),若Yn+1 != Yn,则Yn+2 == Yn必定成立,仅当a、c皆为奇数时Yn、Yn+1将0、1交替,否则,为常数(0或1)。

    暂时抛开随机性不管,先找到周期为m的随机序列中的取值规则。

    Donald KnuthThe Art of Computer Programming, Volume 2: Seminumerical Algorithms中的3.2.1.2节对m, a, c和X0取值规则的表述:

    1) gcd(c, m) = 1. 即c, m互素,再白一点,c, m除1之外没有其他公因子;

    2) 任给质数p, p|m ==> p|(a-1). 即m%p==0,则(a-1)%p==0。

    3) 4|m ==> 4|(a-1). 即m%4==0,则(a-1)%4==0。

    这个证明过程对于我这样的数论基础不是很扎实的搞应用技术的人来说有点难以理解了。有兴趣的话,还是去看3.2.1.2的证明吧:-)。

    上面的规则告诉我们,满足了上述规则后,可以保证序列周期为m。对于前面提到的关于随机性的问题,既然Xn低位的随机性比较弱,可以只取Xn的高位作为输出。高位的随机性和统计意义由a, c确定,其取值涉及统计检验,具体的也还是看3.3吧。

    这篇文章解决了具有统计意义的随机数的部分理论问题。

    PS: 之前曾经BS过Windows Live Writer,当时觉得Writer编辑功能太少,不能直接设定链接文字的字体颜色,知道CSS可以设定之后,又觉得Word 2007编辑的Blog转成html之后太大,而且也知道Word 2007上面是可以设置链接的target为_blank的。现在发现Writer还是很不错的了,原来是可以设定格式的,也可以直接编辑html,而且可以Web预览,链接还可以加入到链接词汇表,挺方便的。

    越来越发现Wikipedia是个和Google一样的好东西!

    posted @ 2008-04-15 14:01 Fox 阅读(4296) | 评论 (3)编辑 收藏

    转自:http://www.cppblog.com/Bugs/archive/2008/04/01/45903.html

    基本要求:
    1、有软件工程思想,熟悉面向对象思想。
    2、有良好的编码风格和文档编写习惯
    3、熟悉C++语言,了解STL
    4、了解多线程程序设计技术
    5、热爱游戏、有游戏开发经验者优先
    6、有团队开发精神优先

    客户端程序员:
    1、了解DirectX编程技术,有良好的数学、各种算法基础优先
    2、有图形开发经验者优先
    3、熟悉UI编程技术优先
    4、熟悉引擎开发者优先

    服务器端程序员:
    1、熟悉通信以及网络安全技术. 熟悉TCP/IP协议及相关编程技术优先
    2、有关系数据库编程及概念经验(MySql、PostgreSQL、MS Sql)
    3、了解分布式服务器架构技术优先
    4、了解Lua、Python有游戏脚本系统设计经验优先

    办公地点:成都
    有意向的朋友跟贴或发简历到本博左侧邮箱。

    posted @ 2008-04-11 12:41 Fox 阅读(842) | 评论 (2)编辑 收藏

    Author: Fox

    一、随机数

    软件实现的随机数生成器(random number generator, RNG)生成的随机数列大多是惟定数列,因此一般被称作伪随机数(pseudorandom number, PRN),而基于热噪声(thermal noise)光电效应(photoelectric effect)放射性衰变(radioactive disintegration)等不可预知的物理现象实现的硬件随机数生成器(hardware random number generator)生成的随机数才被认为是真随机数(truly random number)。PRN在计算机领域主要用于仿真(simulation)和密码学(cryptography)。

    本文仅讨论伪随机数软件实现算法,并且仅讨论满足均匀分布(uniform distribution, UD)的伪随机数发生器(pseudorandom number generator, PRNG)。非均匀分布(non-uniform distribution, NUD)的PRNG可通过满足均匀分布的PRNG与非线性函数生成。

    本文讨论的PRNG应满足以下三点:

    a. 在取值空间内满足UD,即等概率取得取值空间内任意值。

    b. 充分随机,即该随机数列周期(period)应尽量长。此点由所谓的熵(entropy)度量。

    c. 唯一输入或称种子(seed)对应唯一输出PRN。这一点ms是计算机的强项,也是PRN惟定的根源,也是算法被破解的根源。

    由于PRN sequence(PRNS)惟定,所以算法的安全性主要取决于熵的选择和算法的复杂性

    二、可预测PRNG与不可预测PRNG

    所谓可预测(determined)PRNG,也被称为统计意义上的PRNG(statistic PRNG),一般只有一个seed,而对于同一个seed,生成的PRNS是惟定的。

    不可预测(indetermined)PRNG,从理论上讲,不可预测的PRNG是不存在的,这儿指密码学安全的PRNG(cryptographically secure PRNG, CSPRNG)。

    三、常用PRNGs

    1、线性同余发生器(linear congruential generators, LCG)

    单博伟标准库rand()函数的缺陷以及Blitz++随机数生成的简介中给出了The C Programming Langurage 2nd的实现,我手头没有这本书,所以无从查证,FallHunter应该还有吧。

     1 unsigned  int  next  =   1 ;
     2
     3 /*  rand: return pseudo-random integer on 0..32767  */
     4 int  rand( void )
     5 {
     6  next  =  next  *   1103515245   +   12345 ;
     7   return  (unsigned  int )(next / 65536 %   32768 ;
     8 }

     9
    10 /*  srand: set seed for rand()  */
    11 void  srand(unsigned  int  seed)
    12 {
    13  next  =  seed;
    14 }

    VS2003中给的实现是:

     1 /* **
     2 *rand.c - random number generator
     3 *
     4 *       Copyright (c) Microsoft Corporation. All rights reserved.
     5 *
     6 *Purpose:
     7 *       defines rand(), srand() - random number generator
     8 *
     9 ****************************************************************************** */

    10
    11 #include  < cruntime.h >
    12 #include  < mtdll.h >
    13 #include  < stddef.h >
    14 #include  < stdlib.h >
    15
    16 #ifndef _MT
    17 static   long  holdrand  =   1L ;
    18 #endif   /* _MT */
    19
    20 /* **
    21 *void srand(seed) - seed the random number generator
    22 *
    23 *Purpose:
    24 *       Seeds the random number generator with the int given.  Adapted from the
    25 *       BASIC random number generator.
    26 *
    27 *Entry:
    28 *       unsigned seed - seed to seed rand # generator with
    29 *
    30 *Exit:
    31 *       None.
    32 *
    33 *Exceptions:
    34 *
    35 ****************************************************************************** */

    36
    37 void  __cdecl srand (
    38         unsigned  int  seed
    39         )
    40 {
    41 #ifdef _MT
    42
    43         _getptd() -> _holdrand  =  (unsigned  long )seed;
    44
    45 #else   /* _MT */
    46         holdrand  =  ( long )seed;
    47 #endif   /* _MT */
    48 }

    49
    50
    51 /* **
    52 *int rand() - returns a random number
    53 *
    54 *Purpose:
    55 *       returns a pseudo-random number 0 through 32767.
    56 *
    57 *Entry:
    58 *       None.
    59 *
    60 *Exit:
    61 *       Returns a pseudo-random number 0 through 32767.
    62 *
    63 *Exceptions:
    64 *
    65 ****************************************************************************** */

    66
    67 int  __cdecl rand (
    68          void
    69         )
    70 {
    71 #ifdef _MT
    72
    73         _ptiddata ptd  =  _getptd();
    74
    75          return ( ((ptd -> _holdrand  =  ptd -> _holdrand  *   214013L
    76              +   2531011L >>   16 &   0x7fff  );
    77
    78 #else   /* _MT */
    79          return (((holdrand  =  holdrand  *   214013L   +   2531011L >>   16 &   0x7fff );
    80 #endif   /* _MT */
    81 }


    2、LFG, LFSR等

    限于篇幅,有兴趣的TX可以参考后面的资料,主要是Wikipedia,上面给的算法还是非常详细的,CSPRNGs包括Blum Blum Shub、Fortuna等。

    如果出于安全性的考虑,PRNG的输出不应直接作为种子。在《构建安全的软件》一书中,作者认为“一个好的PRNG具有这样的性质:给足够的熵,即使攻击者知道全部的算法细节,还是不能猜出生成的数据流”。

    三、PRNG的安全测试

    FIPS-140标准包含了对RNs的测试规范。这个标准我也没有去仔细看,所以没法给出更多的信息。被提到的测试包有DIEHARD、pLab

    四、随机数在游戏中的应用

    1、随机数为游戏带来更多的不确定性,不确定性产生可玩性

    这个应该是所有游戏的根本了吧。游戏中玩家、怪物、NPC的很多属性都是一个范围,比如攻击就有最小攻击和最大攻击,每次的实际攻击伤害总在二者之间。

    同样的,玩家乐此不疲的一次次“洗装备”、“碰运气”。其他类推吧。

    2、游戏的AI更多的依赖于随机数

    如果怪物、NPC的AI一切尽在玩家的掌握中,游戏的乐趣就大大降低了,这一点在单机游戏中有着很好的体现。War3中,人机对战,电脑的战术并不单一(但还是有规律可循,人类玩家尚且如此),这其中固然有多方面 的因素。但随机数的功劳也不容抹杀。

    3、随机数减少数据存储,一个种子可以代替一批数据

    游戏中含有大量数据,如果每一项都要存取,对时间和空间都是一个考验。对于场景中随机生成的怪物信息,如果给定一个相同的种子。呃,是不是要简单一些呢?

    五、相关内容

    至于为什么PRNGs大多使用素数,需要更多的数论知识,对密码学有了解的TX应该能够体会到安全和数论之间的紧密联系。因为手头没有数论的书,所以不多加妄测了。到时写论文的时候,再填充上吧。

    六、参考文献

    1. 构建安全的软件. [美]John Viega, Gary McGraw. 钟向群, 王鹏 译.  北京. 清华大学出版社, 2003.

    2. Pseudorandom number generator及相关链接. http://en.wikipedia.org/wiki/Pseudorandom_number_generator

    3. PRNG - Pseudo-Random Number Generator. http://statmath.wu-wien.ac.at/prng/

    -------------------------------------------------------------------------

    PS01:手上的几本书

    从几位TX那儿拿的几本书,放在桌上大半年了,一直没有怎么翻过。想想周末还给他们算了,于是就拿过来翻翻,立此存照,如果以后用到的话,再来查。

    a. 《用TCP/IP进行网际互联》Vol. III,主要是针对Linux/POSIX套接字的C/S架构实现。因为MMORPG的C/S架构多依赖于TCP,上面第8、10-16章的内容可以关注一下。

    b. 《构建安全的软件》,上面关于开源、闭源的口水(Chap. 4),关于缓冲区溢出(Chap. 7),关于随机数(Chap. 10),关于数据库安全(Chap. 14),关于客户端安全(Chap. 15),都是值得一看的东西。

    c. 《UNIX环境高级编程》,进程控制(Chap. 8)、线程控制(Chap. 12)、进程通信(Chap. 15, 17)、套接字(Chap. 16)、数据库(Chap. 20)。

    d. 《UNIX网络编程》Vol.I,如果涉及到泛UNIX操作系统下网络编程,可以当作参考书翻。

    e. 《计算机安全原理》,加密(Chap. 5)、认证(Chap. 6)、协议安全(Chap. 7)、入侵检测(Chap. 13)、恶意攻击(Chap. 15)、灾难恢复(Chap. 19)。

    PS02:微软宣布不会抬高收购Yahoo价格

    消息来自Wall Street Journal,不过当天可是April Fool

    PS03:关于Wikipedia

    不是说Wikipedia被禁的吗?很久没有访问过了,这么好的东西,被封了还是很遗憾的。

    PS04:有问题

    发现问题,找Google;解决问题,找Wikipedia

    PS05:欢迎补充

    -------------------------------------------------------------------------

    Added on Apr.10th

    今天从CodeProject上看到一篇文章Applied Crypto++: Pseudo Random Number Generators),作者Jeffrey Walton对密码学和安全比较有研究。

    Jeffrey Walton对Knuth的The Art of Computer Programming Vol.2中关于随机数的部分作了概括。

    这篇文章从一个工程师的角度给出了随机数的应用和实现,很具有参考性。

    作者还从FIPS 140-2标准中引用了下面一段话:

    Random Number Generators fall into one of two classes: deterministic and nondeterministic. A deterministic RNG consists of an algorithm that produces a sequence of bits from an initial value called a seed. A nondeterministic RNG produces output that is dependent on some unpredictable physical source that is outside human control.

    这一段话很好的说明,依赖于算法的RNG所生成的随机数列只可能是伪随机数,真随机数依赖于不可预测的物理源

    posted @ 2008-04-03 02:35 Fox 阅读(6673) | 评论 (15)编辑 收藏

    Author: Fox

    在以前写 MMORPG中游戏世界的构建 时,提到服务器架构的分类。大多数情况下,每一种不同的服务器只会与其对应的一个服务器和多个客户端通信。比如,GameServer(GS)只会与WorldServer(WS)通信,也就是说GS只作为WS的客户端。这次,由于项目需求,新增加了一个SomeServer(SS)作为GS的服务器。

    一、SS网络连接分析

    由于需要和大量GS建立网络连接,所以SS使用了IOCP模型。鉴于 上一次写IOCP 时遭到 Kevin TX的鄙视,所以决定今天多写一点。SS的网络模型大致如下:

    0、服务器主线程启动;

    1、初始化Winsock,SDK func: WSAStartup ();

    2、创建一个使用overlapped I/O的socket,SDK func: WSASocket();

    3、绑定端口,将本地地址与创建的socket关联起来,SDK func: bind();

    4、创建IOCP对象,SDK func: CreateIoCompletionPort();

    5、创建工作者线程,CreateWorkerThreads();

    6、开始监听,SDK func: listen();

    7、接受客户端连接,SDK func: WSAAccept();

    8、当有新的连接请求到达时,将WSAAccept返回的对应的客户端socket关联到IOCP;

    9、处理WSASend() or WSARecv()。

    在实际处理时,可能会根据需要建立额外的线程处理socketopt命令,甚至建立专门处理WSAccept的线程。

    关于工作者线程WorkerThread:

    通过GetQueuedCompletionStatus(),获取I/O类型和对应的socket,如果为接收则通知接收完成并继续新的WSARecv(),如果为发送则通知发送完成。

    二、GS网络连接分析

    GS上对于SS客户端采用的是WSAEventSelect模型,通过网络事件触发相应操作。

    0、服务器主线程启动;

    1、初始化Winsock,SDK func: WSAStartup ();

    2、创建一个使用overlapped I/O的socket,SDK func: WSASocket();

    4、绑定端口,将本地地址与创建的socket关联起来,SDK func: bind();

    5、创建网络事件,SDK func: CreateEvent();

    6、设置网络事件的响应,SDK func: WSAEventSelect();

    7、等待网络事件,SDK func: WSAWaitForMultipleEvents();

    8、分析网络事件类型并处理,SDK func: WSAEnumNetworkEvents()。

    这里之所以采用CreateEvent而不是WSACreateEvent,是因为由CreateEvent创建的事件允许为auto reset的,而WSACreateEvent创建的事件是manually reset的。

    三、实现过程中的小插曲

    在GS的客户端实现中遇到几个问题。

    首先是在消息处理上,GS发到SS的消息,SS并没有完全接受到,而SS发送到GS的消息一切正常。后来跟了一下SS消息队列,发现SS居然可以收到GS发送到WS的消息!然后就在GS上找原因,原来是WS在和SS共用消息队列,以前GS只对应一个服务器,无所谓共用。现在加了SS,自然要分开处理,否则WS和SS都可能收到发给对方的消息。

    后面一个bug从周一开始已经强奸了我四天了。即使SS已经关闭,WSAEnumNetworkEvents返回的事件对应FD_CONNECT的iErrorCode值始终为0。因为中间涉及到多线程和多个服务器分别对应的客户端,连接到WS的没有问题,就是SS的客户端有问题。到今天上午为止,我已经把GS的网络处理逻辑全部静态分析了一遍,没有任何发现。临近中午吃饭的时候,不得已只好用WS的客户端socket去连接SS,居然出现同样问题!而我的WS和SS都是放在我机器上的,这样来看,就只有端口不同了!

    果然,当我把SS的监听端口修改之后,问题解决了。因为我是使用8088端口监听GS连接的。当我把端口换成80,同样问题再次出现,而且SS无法通过80端口监听。

    接下来提几个问题:

    1、 被卡巴斯基监控的端口8088和服务器开启的监听端口8088有什么联系?为什么没有冲突?卡巴仅仅只是从该端口获取数据吗?为什么网络事件的FD_CONNECT的对应iErrorCode为0(表明连接成功)?

    2、 80是常规http端口,它与8080、8088这些http端口的区别在哪儿?这些端口绑定成功与否的原则是什么?

     

    PS:文中关于IOCP和WSAEventSelect模型更为详细的实现,可以参考 Network Programming for Microsoft Windows 2nd 的第五章:Winsock I/O Methods。

    最后写完了,发觉自己写的很垃圾,完全就是记流水帐。转念一想,为什么呢?自己基础不扎实嘛,第一次接触IOCP和网络模型,也就这样了。

    今天太晚了,要睡了,上面的问题明天再考虑吧 J

    posted @ 2008-03-28 01:41 Fox 阅读(3638) | 评论 (8)编辑 收藏

    Author: Fox

    昨天越俎代庖面试了一个家伙。

    看完了他的笔试题目,感觉后背有点凉,但这些东西看看也就过去了,说实话,那些C++的题目多少有点BT

    但我一直觉得DS的东西,如果你当初学的时候是很认真学习过并思考过的,其实是不需要去记忆的,所以我就问了一个关于稳定排序和不稳定排序的问题。我想,只要你理解了各种排序算法的思想,很easy。

    只是这哥们儿忘记了什么是稳定排序,我还以为他把快速排序、堆排序当作稳定排序只是没记住。看来,老师从小教育的"一道题目你即使不会也要尽量去答"这种思想遗毒颇深。如果抱着这种思想做程序员,公司多半要垮掉。

    想一想稳定排序的概念吧:两个同值元素(不知为什么,我一直记得严老师书上用的是49,看来我还是在读死书死读书,最后可能会读书死L)在排序前后相对位置保持不变,即本来在前面的还在前面(所谓"尘归尘,土归土",看来最近思想有点消极,难怪没有激情L)。再想想各种排序的思想,我们很容易得到这样的结论:最普通的O(n2)的算法,一个一个从前比到后,自然不会影响到同值元素的相对位置,而O(nlogn)的算法,由于多路比较,可能导致本来相对位于后面的元素先比较和移动,造成不稳定。这样一想,自然知道简单的插入、选择、归并排序都是稳定的,而改进的高效率的算法则不稳定。

    后面另一个同事在询问他做的Demo的事情,因为是DX的东西,我不懂,没插嘴,就随便看他的简历。

    看到其中一项,有提到他曾经给大一、大二的学生做过C++培训。我本没打算提他笔试中的C++部分的,但既然曾经为人师表(因为我曾经做过学生、也做过老师),C++基础掌握到这种程度就不对了。尤其对于一个空的C++类默认生成哪些成员函数居然写的一塌糊涂(友情提示:你也不用BS他,如果你没有看过Lippman的《Inside of the C++ Object Model》,建议你先不要发言J)。

    我一般对语言特性不太敢发表观点(因为我的C++基础不扎实L),但我对简单的算法或思想小有兴趣(没有你想象中那么高)。可是,笔试中唯一的一个需要coding的题目他又没写。我只好说,C++的东西你掌握怎么样我也可以不看,但这个memcpy的实现,你怎么也得有点想法吧?不然怎么去写代码呢?刚好在面他之前,还和同事讨论过memcpy的问题(如果你给出one byte by one byte的实现会遭BS的J,因为你居然没有考虑过计算机系统本身的数据处理)。

    本来还想问他一个关于sizeof()的问题,后来觉得也没什么必要,关于union的对齐,要按照单位最长的成员对齐这一点自己都觉得有点BT就算了。

    其实,我想说的是,很多东西,你不能认为你掌握的很好(除非你真的掌握的很好),所谓很好,拿C++来说,就是把你认为你好的地方,你可以不翻其他东西,把它写下来,基本跟ISO C++保持90%以上的相似度就可以了。当然,这样说有点贱了。

    毕竟,做游戏程序员(其他也差不多吧)需要的是:

    带着激情去编码,带着虚心去学习,带着挑战去交流,带着压力去工作。

    激情,能让你的思维满具创意,代码极其飘逸;

    虚心,能让你的知识不断积累,从而达到厚积薄发;

    挑战,能让你的团队充满活力,交流活泼严谨;

    压力,能让你的心态保持平衡,胜不妄喜,败不惶馁。

    因为自己这两周心态受到非智力因素干扰,日子过得有点浑噩。写下来,主要是为了放松一下,也提醒自己。

    不怕无知,但怕无畏。

    -----------------------------------------------------------------

    PS:补记于2008/03/26

    还是把上午写的一个mymemcpy放上来吧。里面没有对des < src + len的重叠情况进行讨论,因为大致google了一下,似乎很少人这样做(倒不是因为不能实现)。

    void *mymemcpy( void *src, void *des, size_t len )
    {
     char *tempsrc = (char *)src;
     char *tempdes = (char *)des;

     size_t offset = len / 4;
     for( size_t i=0; i<offset; ++i )
     {
      *(unsigned long *)tempdes = *(unsigned long *)tempsrc;
      tempdes += sizeof(unsigned long);
      tempsrc += sizeof(unsigned long);
     }
     
     offset = len - len % 4;
     for( size_t i=0; i<offset; ++i )
     {
      *tempdes++ = *tempsrc++;
     }
     return des;
    }

    刚才想求证一下memcpy在地址重叠的情况下,是否会考虑从后往前copy的情况。结果看到云风的blog上很早的一篇文章,也是讲memcpy的,角度不同。

    我想澄清一点,我写这篇blog的初衷只是总结几个技术问题,因此就没有把面试的前因后果讲一下,反倒让很多朋友误解,以为我怎么怎么样了。

    事实情况是,这几个问题都是本来的笔试题目当中的,面试的TX从上午10:00前后做到11:30过,等我和另一个同事13点过去的时候,我一直没怎么说话。只是在一边看他的简历和题目,文中已经说了,是看到他的简历之后才提的问题。当时是有10道左右的C++题目,他做对的其实只有一道。

    而且,我在提问题的时候也都将问题跟他一起分析了的(除了memcpy之外),自我感觉说话还是很得体的,写文章的风格是另一码事儿。

    我没有丝毫瞧不起这位TX的意思,也完全没有显摆的想法。

    PS :忽然想到自己最近为什么癖性十足,因为最近在关注一个家伙的 Blog ,如果不侵权,我想用用他的 Blog 的名字《 不许联想 》,作者是带三个表王小峰(《三联生活周刊》记者)。所以,如果有人想拍我,建议先看看他的东西,学习一下措辞 J 。一个同事,说天涯也行,我个人觉得天涯有点相互吹捧的味道。

    恶心,但没有恶意 J

    posted @ 2008-03-20 21:17 Fox 阅读(4065) | 评论 (52)编辑 收藏

    仅列出标题
    共7页: 1 2 3 4 5 6 7