Silver

最短摘要生成与多模式匹配（三）

2010-01-04T09:21:36Z

Boyer-Moore算法——“坏后缀规则”？

如前贴所述，BM算法的“好后缀规则”实际上有两种情况：“中缀”和“前缀”。

“前缀”没啥问题，但是我发现“中缀”往往会出现“跳转以后朝向注定的失败匹配”，如下图所示：

如上图，在第6位X处发生了miss match，BM算法会跳转到3位，也就是将pat挪到如上表第三行的样子，再从11位开始比较，假设11～7都匹配成功了，但是X!=B，第6位是注定失败的。

那么可否将“中缀跳表”独立出来，匹配过程中判断”好后缀”加上它的前导字符构成的子串是否在pat中存在？如果不存在就是个“坏后缀”。

例如：上图中的“XXY”实际上是“坏后缀”，而不是“好后缀”，因为在pat中根本不存在这样的子串。

如何考虑“坏后缀规则”？

如果要实现这个规则，需要注意两个问题。

如下图，和前面一样，假设在倒数第三位X处发生了miss match，可以跳转到两个位置（如箭头所示），但是有一个跳转是重复的，A=A。

因此可以看出，如果要独立“中缀跳表”，需要考虑两个问题：

某位置的中缀跳转可能不止一个；
跳转中可能存在重复。如果出现重复，需要取最右边的那个。

很容易想到，满足这两个需求，用个哈希表恰好。

一种实现方法

将（二）贴中的计算中缀跳表的地方用一个函数AddInfixJump(i, j);代替，这个函数如下：

/// <summary>

/// 中缀跳表

/// </summary>

static Dictionary<char, int>[] iJumps;

static void AddInfixJump(int i, int j)

    if (j < m - 1)//最后一位采用坏字符移动，这里不需要

        if (iJumps[ j ] == null) iJumps[ j ] = new Dictionary<char, int>();

        //添加中缀跳 能保证从小到大

        if (!iJumps[ j ].ContainsKey(pat[ i ])) iJumps[ j ].Add(pat[ i ], i);

这样去计算中缀跳表，能够保证没有重复，并且右边的跳转肯定是先计算的，所以保留的也是最右边的。

然后在搜索过程中，如果在pat倒数第1位以前发生了miss match（也就是不用“坏字符规则”）的时候，先设置跳转为原来的那个表（比原来少了中缀跳转而已），然后再看看是否有好的“中缀”：

shift = mJumps[ j ];//设置为前缀和坏后缀混合跳转

if (iJumps[ j ] != null &&//存在中缀

    iJumps[ j ].ContainsKey(text[ i ]))//且跳转以后匹配text[ i ]

    shift = m - 1 - iJumps[ j ][text[ i ]];//设置中缀跳 (m-1-j + j-k)

这样能够避免上面出现“注定的失败”了。

实验结果

通过实验我发现，这样改进以后，在随机字符串和英文文章的匹配中，比较次数能够降低10%～30％，但是总体性能提高却不明显。我估计性能肯定是损失在C#的泛型字典Dictionary<>上面了，“坏后缀”的思路应该很好，但是可能需要别的实现方法：比如字符集小的话可以用数组，或者别的语言实现。有人想到好方法麻烦告诉我：）

后记

这和我一直以来的编程经验是相反的：“一般来说，不应该先考虑太细节的优化，算法思想的优化是最重要的”；但是在字符匹配的程序中不完全是这样，字符比较的消耗很小，稍微复杂的逻辑和数据结构都会损失性能，所以凡事都有例外。

有些细节优化却能够提升性能，例如，原版的BM搜索过程是这样的：

var shift = 0;

var k = (int)text[ i ];

if (k < cJumps.Count) shift = cJumps[ k ];

else shift = m;

i += Math.Max(shift, mJumps[ j ]);

贴（二）中，我将其改为：

if (m - j == 1)//末位不匹配

     var k = (int)text[ i ];

     if (k < cJumps.Count) i += cJumps[ k ];

     else i += m;

 else i += mJumps[ j ];

实际上就是当匹配超过1个字符时候，不用去计算“坏字符跳”。这样小改动一点，在随机字符和英文测试中，性能都提高了10％左右。

当然要说明的是，MB算法总体性能相比最原始的BruteForce算法还是有大幅提高的，pat越长越明显。

最短摘要生成与多模式匹配（二）

2010-01-01T07:24:00Z

Boyer-Moore算法

通过学习和借鉴之后，感觉这个算法思想挺精妙，同时也比较复杂。我根据自己的理解写了一个算法，望大家指教。

前面提到过，这个算法是从右往左匹配，根据“坏字符规则”和“好后缀规则”来跳转，避免无谓的比较。

坏字符规则

这个规则比较简单，首先看pat的末位是不是和要查找的文本匹配，如果不匹配，pat里面又没有这个字符，则可以完全跳过这个字符，如下图：

如果pat里面有这个字符，则跳到pat里面最右的这个字符（当然排除自己），如下图中pat的第二个T:

可见这个规则是在末位就不匹配的时候用的，如果已经匹配了几位了，这几位就是“好后缀”了。

好后缀规则

个人觉得，如果要清晰理解这个规则，应该再明确两个概念，一个是“中缀”、一个是“前缀”。

中缀

如下图，在pat＝wowwow中，第3位的w就是中缀，它有两个特点：一是和后缀匹配；二是它前面的字符不能和“后缀”前面的字符一样，否则跳转过去没意义。

下图中，如果匹配到4的时候发生miss match，就跳到2，换个w来比。

另外要注意的是，中缀可能很多，在BM算法中就考虑移动到最右边的这个中缀，如下图，x y 的中缀出现了好多次，如果在8出现mis match，就跳到5，而不考虑2了。

注意，最前面的x y不算中缀，而算“前缀”。

前缀

和后缀匹配的前缀这里简称“前缀”。如果pat＝wowwow，其前缀是w 和wow，长度分别为1 和 3，这说明前缀长度可以是跳跃的，长度为2的前缀不存在。

如AAAcAAAAAAcAAA的前缀长度就有7、3、2、1。

最后，在前缀跳转和中缀跳转中，应该取小的，避免遗漏（中缀跳<前缀跳）。

如果中缀、前缀都不存在，就可以直接跳过整个已经匹配的部分。

算法实现

坏字符表构造

坏字符表理论上可以用哈希表来做，不过我实验了下，字符比较本来运算量就小，用哈希有点费，还是改用数组了，cJump 是坏字符跳表，由于不知道字符集的大小，这里用动态扩展策略。

其中，m = pat.Length;

static List<int> cJump = new List<int>();
static void BuildCharJump()
{
    cJump.Clear();
    for (int i = 0; i < m - 1; i++)
    {
        var k = (int)pat[ i ];
        while (k >= cJump.Count) cJump.Add(m);
        cJump[k] = m - 1 - i;
    }
}

好后缀表构造

好后缀表又称为match jump，可以通过上次帖子介绍的“逆向的MP fail links”来构造，因为是倒着匹配的。

为了便于理解，这里给出一个“逆向MP fail links”的构造过程：

static int[] mJumps;

static void BuildMatchJump()

    if (m < 2) return;//少于一个字符，不存在后缀

    //一、初始化

    var n = m - 1;

    mJumps = new int[ n ];

    for (int k = 0; k < n; k++)

        mJumps[ k ] = (n - k) + m;//初始化为最大移动数

    //二、构造逆向 MP fail links，并计算中缀跳表

    var fails = new int[ m ];//逆向 MP fail links

    int i = n;

    int j = fails[ n ] = m;

    while (true)

        while (j < m && pat[ i ] != pat[ j ])

            if (j < n)// 已匹配长度 +  移动数

                mJumps[ j ] = Math.Min(mJumps[ j ], (n - j) + (j - i));//计算中缀跳，记录最右的中缀

            j = fails[ j ];

        if (i == 0) break;

        fails[--i] = --j;

    //三、计算前缀跳表

    var s = 0;

    while (j < m)//顺着最后一个箭头往前可找到所有前缀

        if (pat[ i ] == pat[ j ])

            var L = m - j;//前缀长度

            for (int k = s; k < m - L; k++)//已匹配长度 + 移动数

                mJumps[ k ] = Math.Min(mJumps[ k ], (n - k) + (m - L));

            s = m - L;

        j = fails[ j ];

查找算法

最后的查找算法再用两个表就好了：

static public int IndexOf(string pattern, string text, int index)

    if (pat != pattern)

        pat = pattern;

        BuildCharJump();

        BuildMatchJump();

    int i = index + m - 1, j = m - 1;

    while (i < text.Length)

        if (j < 0) return i + 1;//找到

        if (pat[ j ] == text[ i ]) { i--; j--; }

        else

            if (m - j == 1)//末位不匹配

                var k = (int)text[ i ];

                if (k < cJumps.Count) i += cJumps[ k ];

                else i += m;

            else i += mJumps[ j ];

            j = m - 1;

    return -1;

后记

个人觉得MB算法还可以有改进的地方：可以提出一个“坏后缀规则”，因为MB算法构造跳表的时候没有考虑text的内容，所以没办法知道“坏后缀”，明天咱们继续分析这个改进。

最短摘要生成与多模式匹配（一）

2009-12-31T06:21:00Z

问题

《编程之美》有一道题目“最短摘要生成”：若输入“微软亚洲研院使命”三个关键字，查找最短的摘要：

微软研究院的使命是使未来的计算机能够看、听、学，能用自然语言与人类进行交流。 ... 微软亚洲工程院将以微软亚洲研究院的科研成果为依托，创造关键技术、为微软亚洲研究院核心技术的孵化提供有力保证。 ... 微软亚研院的科研环境编辑本段回目录…

书中给出的解法是基于“分词”后的数组的。

那么，如果是客户端蜘蛛临时抓的网页，或者是在一堆文件中查找，这时候没有分词、没有建立倒排表，如何直接生成呢？再加上有中英文混杂的情况（查找某种表达的翻译）？

冰山一角

这时我想到了基于“多模式匹配”改进原书中算法，因此决定研究下经典的AC_BM算法。查阅了很多文献后，意外的发现：小小的“字符串匹配”居然有这么多学问～：），引用一段文献——

“String-matching is a very important subject in the wider domain of text processing. String-matching algorithms are basic components used in implementations of practical software existing under most operating systems. Moreover, they emphasize programming methods that serve as paradigms in other fields of computer science (system or software design). Finally, they also play an important role in theoretical computer science by providing challenging problems…”

这段文字出自 http://www-igm.univ-mlv.fr/~lecroq/string/node1.html ，这个网站上竟有35个单模式匹配算法的详细分析、例子、代码、java动画演示…

多模式匹配在：入侵检测、数据挖掘、DNA配对、文本处理（查找替换）等方面都有广泛的应用。

算法发展简要回顾

先简要回顾下经典的AC_BM算法是怎么来的：

1. 1977年，这三个人改进Morris-Pratt 算法提出了Knuth-Morris-Pratt 算法——将“有限状态自动机”＋“递归/递推”思想用得很精妙。

2. 同年，Stanford和Palo Alto研究院的两个人提出了经典的Boyer-Moore算法，主要思想为：

a) 提出了从右往左匹配的思路；

b) 通过“坏字符移动”＋“好后缀移动”避免无谓的比较；

c) “好后缀移动”借鉴了Knuth-Morris-Pratt 算法。

题外话：这个BM算法就是大家日常“查找替换”时候用的：）

3. 1980年，Horspool简化了Boyer-Moore算法：用实验证明了只采用“坏字符移动”在一般情况下性能足够了。这是因为“好后缀”出现的概率并不大，除非是DNA一类的“小字符集”中的匹配，类似AGTCAAGGTTTC…

4. 1975年，Bell Labs的两个人提出了Aho_Corasick算法，主要思想是构造了“多模式”（多关键字）的“有限状态自动机”（是一棵多关键字树，Knuth-Morris-Pratt 算法是单模式的“有限状态自动机”）

5. 2001年，Silicon Defense的三个人将Aho_Corasick算法和Boyer-Moore算法思想结合起来（因为AC算法没有如BM算法一样很好的跳转，还有优化的空间），就成了AC_BM算法。

由此可以看出，要想搞懂AC_BM算法，得从头一个个来。

引用一个题外话：

AC 算法被用于fgrep1.0（在UNIX中通过-f使用）

BM_AC算法在gre中应用，并被fgrep2.0收用。

Knuth-Morris-Pratt 算法

在单模式匹配中，可把要匹配的关键字看成一个“有限状态自动机”：

例如上图，如要匹配：GCAGAGAG，遇到G就转状态1，再遇到G还是在状态1，遇到C就转状态2… 到8就成功

这个思路挺不错，问题是跳转的条件比较麻烦，于是Morris-Pratt就将其简化为两个：成功s和失败f，如下图所示：

要匹配ABABABCB，成功了就向前，失败了就退回来，再失败了递归退后…如下表：

那么构造的时候可以递推构造，思路挺好：）

那么这个算法最关键就是要构造失败的这些箭头：MP fail links，可以用一个int[]保存。

设要匹配的模式是string pattern; m = pattern.Length; 那么MP fail links可以很简洁地构造：

 int[] Morris_Pratt()
    {
        var fails = new int[m];
        int i = 0;
        int j = fails[0] = -1;
        while (i < m - 1)
        {
            while (j >= 0 && pattern[ i ] != pattern[j]) j = fails[j];
            fails[++i] = ++j;
        }
        return fails;
     }

不知道大家有没发现MP fail links 有个问题，假设遇到：

设要匹配的文本是 string text; 如果text中出现了“…ABAY…”，那么按照MP fail links跳转换过来的还是B（如上表最后一行），肯定匹配不上的，所以Knuth-Morris-Pratt算法就改进了这个问题（将上面while里面改了下），构造KMP fail links：

……
while (i < m - 1)
{
        while (j >= 0 && pattern[ i ] != pattern[j]) j = fails[j];
        i++; j++;
        if (pattern[ i ] == pattern[j]) fails[ i ] = fails[j];
        else fails[ i ] = j;
}
…….

就递推地实现了所有首位字符相同的跳转都合并的效果，如下图所示：

那么在查找的时候，就可以利用 KMP fail links 实现跳转，而且思路和构造的时候类似：

 ……
 int i = index, j = 0;
 while (i < text.Length)
 {
       while (j >= 0 && pattern[j] != text[ i ]) j = fails[j];
       i++; j++;
       if (j == pattern.Length) return i - pattern.Length;//找到
 }

 return –1

后记

今天先写到这里，明天咱们继续研究BM算法，感觉挺巧妙的是利用简短的MP fail links可以找到所有的“中缀”和“后缀”。

需要说明的是，直接利用KMP 搜索效率提高并不明显，因此“查找替换”一般用BM算法。

IBM 中国研究院 Offer 之感言——能力是一种态度

2009-12-01T17:11:00Z

当我对着远程的大屏，给北京的IBM中国研究院几位面试官汇报完30分钟技术报告之后，心里忐忑不安，这已经是终面了…一关关拼得不容易，但却很精彩!

在之后的几天，很高兴接到了来自IBM两位高级经理的电话，分别给我介绍了他们部门情况和项目情况，表示我的报告“印象深刻”，“能力很突出”…真的是非常感谢他们能给我这个机会！

诀窍

我不是聪明过人的天才，但是我相信自己的研究能力，这来源于一个诀窍——我悟出一条“定律”，那就是：能力是一种态度！

简单解释如下：这世界上不缺乏聪明人，但是缺乏懂得运用自己聪明才智的人。

今天的帖子，我希望通过7个真实的故事，去诠释这条定律——能力是一种态度！

1. 我通过qq在课题组做了一次试验，将同一个问题群发给了6个成员，有3个人回复我：“这个我没遇到过，不会做啊…”；有2个去Google了下，大概告诉了解了应该怎么弄；有一个人，做程序试验了不同方法的优劣，告诉我最好的方法是什么。多年以后，对很多问题都报以“没遇到过，不会啊…”的人，和能力在积累的人，虽然一样聪明，但是差距就很大了。

2. 行人仿真系统研发的初期，我突然发现A*算法和Social Force Model特别有意思，就钻了进去，花了一些时间把它们研究透彻…当我兴致勃勃给老板介绍完各种模型算法之后，老板说：“你去给领导介绍这些模型算法是没用的，他们要的是效果，模型是无止境的…”。当时我也很沮丧，但是后来事实证明，我的“不务正业”是对的！因为智能化的动态寻路能力成为了我们系统的核心创新点，也是每次项目介绍中最得意的内容。

3. 给北京做的“城市轨道交通运营辅助决策系统”是要在08奥运前上线的，时间很紧，临近系统调试的时候，北京测试人员突然打电话说发现某些车站之间候选路径似乎少了一条…当时大家都认为可能就是边界条件问题，稍微改改就好了。我研究了下这个K短路算法(其他人负责开发的)发现竟是理论上的缺陷…

一时半会儿又没办法给领导解释清楚，我就决定重写这个部分，用数据来说明。由于时间太紧，在北京回上海的火车上看这些很多文献，凭借着良好的A*算法基础，很快设计出新的算法。通过测试发现，老算法共丢了500多条路径！（总共十几万条左右），这时候大家总算舒了一口气了…

但我并没有罢休，因为匆忙，算法速度不快。继续花了几天，将北京轨道网络中2万多OD之间清分计算时间优化到10多分钟，最后优化到1分钟（在我笔记本上）。上线调试当天，领导赞叹道：“这算法可真是又快又准啊！”

4. 还是上面这个系统的故事：当时北京路网基础数据是一个硕士负责录入的，他毕业以后，上海路网数据没人弄了，老板叫我去做。虽然只是半天时间的体力活，但是心里很不是滋味…

虽然有人劝说：“花个半天搞定算了哦！”但是我决心不用笨办法——我花了一个星期，凭借曾经开发的“二维矢量图形库”，设计出一个智能化的基础数据管理子系统，只需要在图上简单点击，然后拷入excel中的车站名称和代码，系统自动识别，然后再自动生成区间、换乘关系等等6张数据库表需要的全部数据。后来课题组利用这个工具构建了很多路网，因为非常简单，这个子系统也成为了后来863中网络客流仿真系统的基础。

5. 上物流系统课老师提到一个著名的NP问题——Vehicle Routing Problem，要求大家回去写写系统设计书。我当时就决定要开发这个系统，后来的几个星期，我发现遗传算法和自然界的规律真的是如此的吻合，达到了如痴如醉的地步，被女朋友嘲笑为：“整天关在屋里下崽…”后来结果是，我设计的遗传算法，不但能够求解最少需要多车，还能找到总里程很短的方案。

6. 在斯坦福访学主要是参与一个疏散仿真系统的研究。但是，由于有遗传算法的背景，另外一个教授介绍我参加他们的一个课题——办公大楼改造优化方案的辅助决策系统。

刚开始我认为这是一个确定性问题，因此采用A*算法得到了比较好的效果，已经可以满足项目需求了。我想为了作对比，又设计了遗传算法，居然发现在少数情况下能“变异”到更好解。大量实验后，我发现了两种算法虽然原理差别很大，数据结构上却存在内在联系，能够组合成一种具备通用性的框架，解决大量离散优化问题。

完全出于对科学问题本身的痴迷，我并没有罢手——自行设计了一种数据结构替换哈希表，将两个算法性能同时提升10倍之多（在遗传算法中提出了“花名册”的概念），后来又发明一种“交叉算法”，再次将遗传算法提升十几倍。当时测试案例的人说已经完全跟不上了（已经让他反复做了好多次了），因此最后我们paper里面的数据不是我最快的算法得到的。

7. 利用上面的“离散优化问题搜索框架”，我发现还可以解决《编程之美》中的许多问题。在大家都忙于找工作面试的时候，我却整整花了一个月关在寝室里研究《编程之美》，有时候挑战一个题目整整花去1天时间，当时我身边的人都说我“不务正业”，我自己都有点怀疑了。可是事实证明，这份研究不但证明了兴趣，还证明了我的算法能力，对后来找工作很有帮助。

结论

通过上面的故事，我想已经可以证明我这个定律了——能力是一种态度。如果要问态度是什么，那么我想是一种单纯的，没有任何功利的科学态度，对问题本身的执着。

这7个故事也可以用下面这张图串起来，一面的时候时间很短，我就打印了这个图，凭借它去打动面官。

后记

在我编程之美的学习连载里面，大家看到了很多好的点子。但是，它们都是在平时走路、吃饭、散步的时候想出来的，我这个人从来不擅长考试，女朋友嘲笑我——如果你去微软面试估计危险，因为你没有时间散步…

我曾经想过，对于一个博士，面试不一定能看出其水平，但是，如果给他30分钟PPT时间，介绍他的研究，水平就一目了然了。

真的没想到的是，在IBM的后2轮面试，全部一一印证了我曾经的设想…用PPT去演讲是我最擅长的东西，因为太多次的磨练了：）

微软的技术是我多年研究和喜爱的东西，微软也是我多年梦想的企业。但是，如今却迟疑了，IBM这份《智慧地球赢在中国》的白皮书确实令人震撼——它能够站在世界经济大环境的角度务实考虑中国的未来…

方曲序列——一道有趣的搜索核心研发试题

2009-11-04T07:44:00Z

问题

假设有4×4的方阵（里面可放字符串），给现定一个序列，检查这个序列是否在方阵的“连续对角线”上面：

例如：从左上到右下的连续对角线序列可能是：

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
1 5 2 3 6 9 13 10 7 4 8 11 14 15 12 16

分析

刚刚看到此题目，可能有点晕，“连续对角线”是啥？仔细一看，其实就是方阵里面的曲线序列（如下图），我就叫它“方曲序列”吧。

再一想，这样的序列应该有8条。考试的时候时间紧，只能大概写写思路了，回来用VS08调试着搞感觉好很多:( 不适合应试哈哈

我们来分析下，这个题目的关键是，要把握住曲线运动其实是两个方向：

沿斜线运动
斜线平移

那么，再看这些斜线的长度分别为 1 2 3 4 3 2 1，那么我们在枚举到这个序列之和的这些关键带点的时候：

需要平移斜线
需要翻转斜线上的运动方向

解法

有了思路，借助VS08 强大的调试功能，我写了8个方向，通用的，O(N)（N是序列长度）复杂度的 “方曲序列” 函数：

运行函数：PrintWinding(4);

就可以得到 n=4 的时候8条“方曲序列”：

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
13 14 9 5 10 15 16 11 6 1 2 7 12 8 3 4
4 3 8 12 7 2 1 6 11 16 15 10 5 9 14 13
16 15 12 8 11 14 13 10 7 4 3 6 9 5 2 1
1 5 2 3 6 9 13 10 7 4 8 11 14 15 12 16
13 9 14 15 10 5 1 6 11 16 12 7 2 3 8 4
4 8 3 2 7 12 16 11 6 1 5 10 15 14 9 13
16 12 15 14 11 8 4 7 10 13 9 6 3 2 5 1

代码如下：

        static void PrintWinding(int n)
        {
            var square = new string[n, n];
            for (int i = 0; i < square.Length; i++)
                square[i / n, i % n] = (i + 1).ToString();

            var p = new int[] { 0, n - 1 };
            for (int sign = -1; sign <= 1; sign += 2)
                for (int i = 0; i < p.Length; i++)
                    for (int j = 0; j < p.Length; j++)
                        PrintWinding(square, p[ i], p[j], sign);
        }

其中：

        static void PrintWinding(string[,] square, int x0, int y0, int sign)
        {
            int n = square.GetLength(0);//边长

              int xn = Math.Abs(x0 - n + 1);//目标点x
            int yn = Math.Abs(y0 - n + 1);//目标点y

            int dx = Math.Sign(xn - x0);//平移方向x增量
             int dy = Math.Sign(yn - y0);//平移方向y增量

             int stepX = -dx * sign;//斜线方向x增量
             int stepY = dy * sign;//斜线方向y增量

             int flag = sign == 1 ? 0 : 1;

            int x = x0, y = y0;
            int s = 1, k = 1, sum = 1;
            for (int i = 0; i < square.Length; i++)
            {
                Console.Write(square[y, x] + " ");

                if (i + 1 < sum)
                {
                    x += stepX;
                    y += stepY;//沿斜线方向移动
                  }
                else if (i + 1 == sum)
                {
                    stepX *= -1;
                    stepY *= -1;//斜线方向掉头

                      if (k == n) flag = Math.Abs(1 - flag);

                   if ((k & 1) == flag) x += dx;//平移
                      else y += dy;//平移

                     if (s < n) k++;//前半三角
                     else k--;//后半三角

                     sum += k;
                   s++;
                }
            }
            Console.WriteLine();
        }

讨论

有了8个方向，通用的“方曲序列” 函数，我们就不难写出测试某序列是否在”连续对角线“上面的函数了，可以考虑采用PLINQ写个并行算法，多个核的话每个核测试一个（些）方向的序列，找到就返回true。

编程之美——差之毫厘

2009-11-03T12:15:00Z

问题

不理解计算机底层运作机制，有时候会写出很费的代码，这说明了两个问题：

底层透明性做得还不够好；
在这样的技术条件下，我们还需要去多了解底层。

来看两个有趣的例子，问题需求是：求一个二维整数数组的和，非常简单吧？

本帖通过4个解法（后两个是并行算法），说明微小的改动对程序运行效率的巨大影响。

*注：需要注意的是，测试结果是在release下的，debug下代码未优化。

解法一

        static int SumA(int[,] array, int n)
        {
            int sum = 0;
            for (int x = 0; x < n; x++)
                for (int y = 0; y < n; y++)
                {
                    sum += array[y, x];
                }
            return sum;
        }

运行测试函数：Test(SumA, array, n);

得到结果：

SumA: 1073741824, 20.4777841s

其中：

测试函数为：

        static void Test(SumDele Sum, int[,] array, int n)
        {
            int sum = 0;
            Stopwatch watch = new Stopwatch();
            watch.Start();
            for (int i = 0; i < n; i++) sum += Sum(array, n);
            watch.Stop();
            Console.WriteLine("{0}: {1}, {2}s",

            Sum.Method.Name, sum, watch.Elapsed.TotalSeconds);
        }

        delegate int SumDele(int[,] array, int n);

    初始条件为：

            int n = 1<<10;
            int[,] array = new int[n, n];

            for (int x = 0; x < n; x++)
                for (int y = 0; y < n; y++)
                    array[x, y] = 1;

解法二

就改动一行：

        static int SumB(int[,] array, int n)
        {

            ……
                    sum += array[x, y];

            ……
        }

再看运行结果：

SumB: 1073741824, 4.8847906s

在我的机子上居然提高了近4倍多！！（每次运行稍有差异，一般在3~5倍）有些机器甚至更高。

分析

在现在的经济和技术条件下，计算机中存储设备的容量和速度是”鱼和熊掌“的关系，没办法两全，人们只好采用了多级结构来解决：快的、贵的、小的存储设备靠近CUP，反之远离：

在这种结构中，上层会通过缓存部分下层中数据副本来提高访问速度：CUP要去找一个数据，先从近的找，没有”命中“再往下继续。那么CUP访问到一个数据往往也会将其附近的数据一并缓存，可称为Locality特性，在上面例子中，由于：

二维数组在内存中是按行存放的；
CUP会在其缓存附近的数据。

因此，按行循环的时候利用到了大量缓存数据，效率高。这也说明，如果二维数组是按列存放的机器里面就刚好反过来。

解法三

随着多核处理器的逐渐普，为了充分利用多核的硬件资源，微软正在研发下一代并行系列框架（Parallel FX）。目前微软已经将PLINQ和TPL包含在Parallel Extension中，我们可用并行算法来求解下试试：

        static int SumC(int[,] array, int n)
        {
            int m = Environment.ProcessorCount;
            int[] result = new int[m];

            int step = n / m;
            int leftover = n % m;

            Parallel.For(0, m, (i) =>
            {
                int from = i * step;
                int to = from + step + (i < m - 1 ? 0 : leftover);

                for (int x = from; x < to; x++)
                    for (int y = 0; y < n; y++)
                    {
                        result[ i ] += array[x, y];
                    }
            });

            return result.Sum();
        }

这个算法根据机器处理器的数量将任务分块，最后加总结果。我机器的是双核的，因此分了两块并行算。

运行程序得到结果为：

SumC: 1073741824, 10.8568457s

奇怪的是，为何没有提高？？反而差了？

分析

这是由于False Sharing导致的。由于每个核的L1缓存互相独立，因此CPU必须有一种机制，能够确保一个核在它的L1 Cache中改动一个数据后，其他核内L1 Cache中包含这个数据的整个Line就会过期。这意味着其他核在读取地址相同，或者是接近的数据时会遇到L1 Cache Miss。CPU的这种同步机制就是MESI协议。

由于int[] result很小，会被多个CPU缓存，然而一个CPU改动了其值就会导致其它CPU缓存中的副本过期，下次就需要重新加载，因此损失了很多性能…

解法四

解决这个问题，只需要改动3行，将中间结果另外用一个变量保存：

        static int SumD(int[,] array, int n)
        {

         ……
                int temp = 0;
                for (int x = from; x < to; x++)
                    for (int y = 0; y < n; y++)
                    {
                        temp += array[x, y];
                    }
                result[ i ] = temp;

         ……
        }

运行程序得到结果：

SumD: 1073741824, 2.5991568s

这个例子说明了几个问题：

首先，我们需要理解计算机底层的运作机制。
但是，这并不代表应该“刀耕火种”。利用PLINQ，我们甚至都不需要显式地去关心多线程就可以实现并行求解，看上去是“语法糖”，但是它们会逐步改变我们编程的思维方式。

最后将四个解法结果放一起：

SumA: 1073741824, 20.4777841s
SumB: 1073741824, 4.8847906s
SumC: 1073741824, 10.8568457s
SumD: 1073741824, 2.5991568s

参考资料

计算机体系结构与程序性能

Running Queries On Multi-Core Processors

闲话

最近做了某知名网络公司的笔试题，感觉如果公司实际开发也是这么底层的话，那么个人认为其效率不是很高，原因在于：

很多SDE可能在解决同样的问题；
很多SDE可能在犯着同样的错误；
很多TE可能在查找着同样的BUG；

我遇到的几个例子：其招聘网站录入信息时候出现几个BUG，其软件登录也会弹出个找不到文件错误…

一些常用集合算法——之幂集合生成

2009-11-01T13:50:00Z

问题

在开发过程中常常需要处理集合，因此我写了一些常用算法，贴出大家提提意见。

本帖介绍幂集合生成算法。

解法一

思路为：

构造初始序列00…0
如果全部为11…1，则停止
寻找位置最低的0，将其变1
将刚刚那个0前面的都变0

这里可以用到前面帖子构造的“动态有序集合”——BinHeap，共设置两个：一个用于保存0的位置，一个用于保存1的位置：

    public static List<T[]> Subset<T>(IList<T> list)
        {
            var zeros = new BinHeap<int>(false);//0的位置集合（因为不需要建立索引，传入false)
            var ones = new BinHeap<int>(false);//1的位置集合

            List<T[]> subsets = new List<T[]>();
            for (int i = 0; i < list.Count; i++) zeros.Push(i);//初始状态全0

            while (ones.Count < list.Count)
            {
                var i = zeros.Pop();
                while (!ones.IsEmpty && i > ones.Peek()) zeros.Push(ones.Pop());
                ones.Push(i);

                i = 0;
                var arr = new T[ones.Count];
                foreach (var p in ones) arr[i++] = list[p];
                subsets.Add(arr);
            }
            return subsets;
        }

运行结果

输入abcde，得到2^n – 1 个子集：

1:a 2:b 3:ab 4:c 5:ac 6:bc 7:acb 8:d 9:ad 10:bd 11:adb 12:cd 13:adc 14:bdc 15:abcd 16:e

17:ae 18:be 19:aeb 20:ce 21:aec 22:bec 23:abce 24:de 25:aed 26:bed 27:abde 28:ced 29:acde 30:bcde 31:abdec

讨论

这里也没有用一般算法的“扫描”的办法，而是利用的两个“动态有序集合”解决了问题，效率提高很多。

解法二

当然，这个问题也肯定可以用前面连载里面广泛用到的“分级排列（组合）法”。

    public static List<T[]> Subset2<T>(IList<T> list)
        {
            List<T[]> subsets = new List<T[]>();
            var heap = new List<T[]>[list.Count + 1];//0～n级的组合

            for (int i = 0; i < heap.Length; i++) heap[ i ] = new List<T[]>();
            heap[0].Add(new T[0]);

            for (int i = 0; i < list.Count; i++)
                for (int j = i + 1; j > 0; j--)
                    foreach (var p in heap[j - 1])
                    {
                        var subset = new T[p.Length + 1];
                        p.CopyTo(subset, 0); subset[p.Length] = list[ i ];
                        heap[j].Add(subset);//更新j级

                         subsets.Add(subset);
                    }
            return subsets;
        }

运行结果

1:a 2:ab 3:b 4:abc 5:ac 6:bc 7:c 8:abcd 9:abd 10:acd 11:bcd 12:ad 13:bd 14:cd 15:d

16:abcde 17:abce 18:abde 19:acde 20:bcde 21:abe 22:ace 23:bce 24:ade

25:bde 26:cde 27:ae 28:be 29:ce 30:de 31:e

可以看出，顺序稍微有些差异，但结果相同，解法二效率稍高。

一些常用集合算法——之组合生成

2009-11-01T13:40:00Z

问题

在开发过程中常常需要处理集合，因此我写了一些常用算法，贴出大家提提意见。

本帖介绍组合生成算法。

分析

开一个数组，数组元素的值为1表示其下标代表的数被选中，为0则没选中。

首先初始化，将数组前m个元素置1，表示第一个组合选中前m个元素。

然后找到从左到右的第一个“10”组合，将其变为“01”组合，

同时将其左边的所有“1”全部移动到数组的最左端，例如：

1 1 1 0 0 //1,2,3

1 1 0 1 0 //1,2,4

1 0 1 1 0 //1,3,4

0 1 1 1 0 //2,3,4

1 1 0 0 1 //1,2,5

1 0 1 0 1 //1,3,5

0 1 1 0 1 //2,3,5

1 0 0 1 1 //1,4,5

0 1 0 1 1 //2,4,5

0 0 1 1 1 //3,4,5

解法

具体实现的时候，不需要每次“从左往右扫描”——我们可以这样考虑：每次将“10”变为“01”，可能产生新的翻转位置，那么就只需要记录新的翻转位置。

 public static List<T[]> Combination<T>(IList<T> list, int n)
    {

        n = Math.Min(list.Count, n);

        var combs = new List<T[ ]>();

        var selection = new Dictionary<int>(n);//用于记录被选中元素的位置
         Stack<int> pins = new Stack<int>();//记录翻转位置
         for (int i = 0; i < n; i++) selection.TryAdd(i);//初始的时候选中前n个元素
         if (n < list.Count) pins.Push(n - 1);//初始翻转位置

         while (true)
        {
             <添加生成的组合>

             if (pins.Count == 0) break;

             var i = pins.Pop();
             selection.Remove(i);//去掉i
             var j = i + 1;
             selection.TryAdd(j);//选中j
                
             if (j + 1 < list.Count && !selection.ContainsKey(j + 1))
                pins.Push(j);//增加翻转点

               bool adjusted = false;
             <将i左边这些连续的1全部移动到最左>

             if (!adjusted && i - 1 >= 0 && selection.ContainsKey(i - 1))
               pins.Push(i - 1);//增加翻转点 
         }
       return combs;
   }

其中：

<添加生成的组合>代码为：

        int cnt = 0;
       var newComb = new T[ n ];
       foreach (var index in selection) newComb[cnt++] = list[index];
       combs.Add(newComb);

<将i左边这些连续的1全部移动到最左>代码为：

       if (i >= 2)
      {
          int z = 0;//从左数0的数量
            while (!selection.ContainsKey(z)) z++;
           if (z > 0 && z < i)
           {
              var m = Math.Min(z, i - z);
              for (int k = 0; k < m; k++) selection.TryAdd(k); //选中k
              for (int k = i - 1; k >= i - m; k--) selection.Remove(k); //去掉k
              pins.Push(i - z - 1);
              adjusted = true;
           }
       }

运行结果

输入abcdef，选3个：

1:abc 2:dab 3:dac 4:dbc 5:abe 6:ace 7:bce 8:ade 9:bde 10:cde 11:abf 12:acf 13:bcf 14:adf 15:bdf 16:cdf 17:aef 18:bef 19:cef 20:def

讨论

网上大多是“扫描算法”，这里用“翻转点”做了改进——不断构造新的翻转点，直到没办法再翻转。

一些常用集合算法——之全排列生成

2009-11-01T13:10:00Z

问题

在开发过程中常常需要处理集合，我写了一些常用算法，贴出大家提提意见

本帖是最简单的全排列生成算法，因为全排本来列就很费，所以以简洁为重，没太多考虑效率。

解法

        public static List<T[]> Permutation<T>(IEnumerable<T> list)
        {
            List<T[]> permutations = new List<T[]>();

            Permutation(new List<T>(list), 0, permutations);

            return permutations;
        }
        static void Permutation<T>(List<T> list, int h, List<T[]> permutations)
        {
            if (h == list.Count - 1)
            {
                permutations.Add(list.ToArray());
                return;
            }

            for (int i = h; i < list.Count; i++)
            {
                Swap(list, h, i);
                Permutation(list, h + 1, permutations);
                Swap(list, h, i);//撤销交换

              }
       }
        static void Swap<T>(List<T> list, int i, int j)
        {
            if (i != j)
            {
                var temp = list[ i ];
                list[ i ] = list[j];
                list[j] = temp;
            }
        }

运行结果

输入abcd：

1:abcd 2:abdc 3:acbd 4:acdb 5:adcb 6:adbc 7:bacd 8:badc 9:bcad 10:bcda 11:bdca 12:bdac 13:cbad 14:cbda 15:cabd 16:cadb 17:cdab 18:cdba 19:dbca 20:dbac 21:dcba 22:dcab 23:dacb 24:dabc

讨论

算法思路很简单，就是一位一位去填，和全排列计算的思路一致。

此算法在只需要输出或者测试排列的问题中，可以不去生成所有排列的实例，从而节约大量内存。

不用API构造简单自旋锁

2009-10-28T23:16:00Z

问题

想必大家都记得《编程之美》“双线程下载”的精彩例子。这里我们来看一个类似的例子。

分析

由于采用“挂起/唤醒”线程的方式加锁，往往涉及到“用户态/核心态”切换，导致不小的性能损失，因此人们发明了自旋锁，在一些分布式应用程序中，性能得到了10～1000倍的提升。

解法

这里我们来看一个最简单的，不用API构造的自旋锁：

   class 简单自旋锁
    {
        int c1 = 0, c2 = 0, who_wait;

        void WrokA()
        {
            int taskCnt = 0;
            while (taskCnt++ < 5)
            {
                c1 = 1;//请求进入临界区
                    who_wait = 1;
                while (c2 == 1 && who_wait == 1) ;
                DoSomeWork(taskCnt + "A", ref c1);
            }
        }
        void WrokB()
        {
            int taskCnt = 0;
            while (taskCnt++ < 5)
            {
                c2 = 1;
                who_wait = 2;
                while (c1 == 1 && who_wait == 2) ;
                DoSomeWork(taskCnt + "B", ref c2);
            }
        }
        void DoSomeWork(string who, ref int c)
        {
            try
            {
                DoSomeWork(who);
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
            finally
            {
                c = 0;//离开临界区
               }
        }
        void DoSomeWork(string who)
        {
            Console.WriteLine(who + " enters critical section...");

            Console.Write(who + " is working");
            for (int i = 0; i < 10; i++)
            {
                Thread.Sleep(300);
                Console.Write(".");
            }
            Console.WriteLine();

            Console.WriteLine(who + " leaves critical section... \n");
        }

        public void Test()
        {
            var threadA = new Thread(new ThreadStart(WrokA));
            var threadB = new Thread(new ThreadStart(WrokB));

            threadA.Start();
            threadB.Start();
        }
    }

运行程序，得到如下结果：

1A enters critical section...

1A is working..........

1A leaves critical section...

1B enters critical section...

1B is working..........

1B leaves critical section...

2A enters critical section...

2A is working..........

2A leaves critical section...

2B enters critical section...

2B is working..........

2B leaves critical section...

……

讨论

自旋锁需要解决如下问题：

1. 没有试图进入临界区的线程不得阻止其它线程进入；

2. 不能让某线程“刚好每次都进入临界区”，某线程“刚好每次都等待”；

3. 不能出现互相等待的“死锁”；

4. 不能出现进入临界区之前，线程互相“谦让”，导致不确定谁进入的“活锁”。

5. 某线程出错不能影响其它线程。

这个例子只是双线程，我们以后再研究多线程的例子。

汽车加油问题——一道迷惑的面试题

2009-10-28T00:05:00Z

问题

一辆载油500升的汽车从A开往1000公里外的B，已知汽车每公里耗油量为1升，A处有无穷多的油，其他任何地点都没有油，但该车可以在任何地点存放油以备中转，问从A到B最少需要多少油？

分析

这道题目初一看觉得方案太灵活，有点晕，网上所有对此题目的答案千篇一律的是：

题目可归结为求数列 an=500/(2n+1) n=0,1,2,3......的和Sn什么时候大于等于1000,解得n>6

当n=6时，S6=977.57

所以第一个中转点离起始位置距离为1000-977.57=22.43公里

所以第一次中转之前共耗油 22.43*(2*7+1)=336.50升

此后每次中转耗油500升

所以总耗油量为7*500+336.50=3836.50升

看起来很有道理，但是又没有说明为什么？害我抓破脑皮去想：这是为什么？怎么证明的？

不过我们简单推下：3836.50 - 7*(500 - 2*22.43) ＝ 650.52，也就是说第一次中转跑7次会剩下650.52，证明这个答案是错误的！

后来我猜想出一种解释，首先我们需要抓住几个关键点：

1. 运输距离要尽量短，也就是说，我们的方案肯定是先从起点将所有需要的油搬到第一个x公里外的转运点，然后再以此类推，不能来回奔波于多个转运点。

2. 运输效率要尽可能高，也就是说，尽量以最大运输能力去跑——不要因为1、2公升油再跑一趟。

3. 相邻转运点之间跑的次数一定是奇数次。

由此，我们可以倒过来考虑：

1. 车到1000公里外的终点的时候，只需要放0的油在那里，转运次数1，可以求得距离是500；

2. 车到500公里外的转运点的时候，需要放500的油在那里，转运次数3，那么如何保证3次都是运输效率最高的呢？通过保证运运输效率最高，可以求得转运点的距离。上面也是这样求的。

3. 以此类推… 中转次数 1 3 5 7 …

解法一

        /// <summary>
        ///计算在距离x的地方放a的油，跑2n+1次运输效率最高的距离
        /// </summary>
        double Distance(double a, int n)
        {
            return (tankLimit * (n + 1) - a) / (2 * n + 1);
        }//x为距离，a = k(tankLimit - 2x) + 500 – x

        /// <summary>
        /// 在距离x的地方，存放amount的油需要跑的总次数
        /// </summary>
        int Trip(double x, double amount)
        {
            int n = 0;
            while (true)
            {
                var a1 = 2 * n * (tankLimit - 2 * x);//来回运的油量
                var a2 = tankLimit - x;//最后一次运的油量
                var diff = a1 + a2 - amount;
                if (diff >= 0 || -diff <= 0.0001) return 2 * n + 1;//避免计算误差
                n++;
            }
        }

        void Transport()//倒推中转
        {
            int k = 0;
            double a = 0, d = 0;//a是每次中转的总耗油量，d是距离累计

            while (d < 1000)
            {
                var last_a = a;
                var x = Distance(a, 2 * k);
                if (d + x <= 1000)
                {
                    a += (2 * k + 1) * x;
                    k++;
                }
                else
                {
                    x = 1000 - d;
                    a += Trip(x, a) * x;
                }
                d += x;

            Console.WriteLine("a = {0:F} x = {1:F} Trip = {2}", a, x, Trip(x, last_a));
            }
        }

运行程序，可以求得：

a = 500.00 x = 500.00 Trip = 1

a = 1100.00 x = 200.00 Trip = 3

a = 1877.78 x = 155.56 Trip = 5

a = 2751.28 x = 124.79 Trip = 7

a = 2888.89 x = 19.66 Trip = 7

可以看出，如果采用这种运输方法，已经比上面网上流传的答案3836.50升少了很多了。但是，这种1 3 5 7…的运输方法就是最优的么？

解法二

或许我们并不需要1 3 5 7…这样递增这么快，1 3 3 3 5 5 5也可能是很好的方法，因此将程序小改动下：

        double Transport(int factor)
       {
                …
                var lastA = a;
                var x = Distance(a, 2 * k);
                if (x == 0) { k++; continue; }
                if (d + x <= 1000)
                {
                    a += (2 * k + 1) * x;
                    if (cnt++ % factor == 0) k++;
                }
                …

然后去计算factor从1～100的情况下耗油量分别是：

1 2888.88888888889

2 2507.65432098765

3 2376

4 2350.4

5 2340.16

6 2336.064

7 2334.4256

8 2333.77024

9 2333.508096

10 2333.4032384

11 2333.36129536

12 2333.344518144

13 2333.3378072576

14 2333.33512290304

15 2333.33404916122

可以看出，factor >15以后就趋于稳定了。

讨论

由此可以看出，不可以盲目迷信别人的解法（当然包括我现在的解法：）做到这里我们可以猜测，解法二也不能说就是最优了，可能存在一些更加优秀的序列——哈哈，说到这里，大家应该想到，这种问题最适合遗传算法了！我暂时没时间了，如果有兴趣的同学找到更优秀的解法麻烦通知我：）

时分秒针重合——看似简单的面试题

2009-10-27T23:06:00Z

问题

在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？

分析

初看此问题觉得很简单，但是网上各种版本的答案都各不相同，那到底谁是对的呢？

我们可以这样考虑——龟兔赛跑，跑得慢的针终归会被快的一圈一圈超过。那么，分别求出时针分针、分针秒针的重合时间，然后再看是否有相同。

这里都不难，关键是有一个陷阱！请问大家，我说“一圈一圈超过”，是不是每圈都被超过？

先求角速度：（度/秒）

1. 时针：w1 = 360 / 12*3600 = 1/120 d/s

2. 分针：w2= 360 / 3600 = 0.1 d/s

3. 秒针：w3 = 360 / 60 = 6 d/s

设3个针当中，快针角速度为wf，慢针角速度为ws。若快针在一天24小时中，转k = 0, 1, 2, 3, … , n圈的时候，重合慢针的时间为t，则：

wf * t - k*360 = ws*t – [ws/wf * k] *360

t = 360*( k - [k*ws/wf] ) / (wf - ws)

代码如下：

        List<double> Times_Overlap(double wf, double ws)
        {
            var n = (int)(24 * 3600 * wf / 360);
            var times = new List<double>(n);
            for (int k = 0; k < n - 1; k++)
            {
                var t = 360 * (k - (int)(k * ws / wf)) / (wf - ws);
                //t = Math.Round(t);
                if (times.Count == 0 || times[times.Count - 1] != t) times.Add(t);
            }
            return times;
        }

运行程序可以得到（显示出來的时间按秒取整了）：

时针分针重合的时间 Times_Overlap(w2, w1)：

(1) 00:00:00, (2) 01:05:27, (3) 02:10:54, (4) 03:16:21, (5) 04:21:49, (6) 05:27:16, (7) 06:32:43, (8) 07:38:10, (9) 08:43:38, (10) 09:49:05, (11) 10:54:32, (12) 12:00:00, (13) 13:05:27, (14) 14:10:54, (15) 15:16:21, (16) 16:21:49, (17) 17:27:16, (18) 18:32:43, (19) 19:38:10, (20) 20:43:38, (21) 21:49:05, (22) 22:54:32,

分针秒针重合的时间 Times_Overlap(w3, w2)：

(1) 00:00:00, (2) 00:01:01, (3) 00:02:02, (4) 00:03:03, (5) 00:04:04, (6) 00:05:05, (7) 00:06:06, (8) 00:07:07, (9) 00:08:08, (10) 00:09:09, (11) 00:10:10, (12) 00:11:11, (13) 00:12:12, …… 23:53:53, (1412) 23:54:54, (1413) 23:55:55, (1414) 23:56:56, (1415) 23:57:57, (1416) 23:58:58,

时分秒针重合的时间：

00:00:00 12:00:00

讨论

通过Times_Overlap(w2, w1) 算出所有时针和分针重合时间；通过Times_Overlap(w3, w2)算出所有分针和秒针重合时间，可以得到总共重合2次：0点和12点。

需要注意的是，快针和慢针每在0点重合，下一圈快针和慢针将不会相遇。因此，时针和分针相遇22次，时针和秒针相遇1438次，分针和秒针相遇1416次。

巧用A*求解大型01规划

2009-10-16T02:18:00Z

A*算法在路径规划中有非常重要的地位，我在很多项目里面都用到了这个算法，下图是我的一个程序，试验大规模Agent实时寻路情况下算法性能：

摘抄一段原来一篇论文对A*介绍：

Pathfinding is a core component of many intelligent agent applications, ranging in diversity from commercial computer games to robotics. Characters should move in some goal-directed manner, and the program must be able to identify a good path from an origin to a goal, which both avoids obstacles and is the most efficient way of getting to the destination.

Despite the fact that the industry as a whole is quite aware of the "magic A* algorithm", it remains perennial problem because implementation is so very game specific.

言归正传，A*如何求解大型01规划？（对需求的描述请参加前面帖子“我在斯坦福”）。

基于A*的改进搜索算法

A*算法是人工智能中一种典型的启发式搜索算法，所谓启发式搜索就是在状态空间中对每一个搜索的位置进行评估，得到当前估计代价最小的位置，再从这个位置进行搜索直到找到目标。因而避免了大量无效的搜索路径，提高了效率。搜索中的估价是用估价函数表示的：

F(n) = G(n) + H(n)

其中F(n)是节点n的估价函数，G(n)实在状态空间中从初始节点到n节点的实际代价，H(n)是从n到目标节点最佳路径的估计代价。A*算法有两个表：Open表，用于存放待访问节点；Close表，用于存放已访问节点。

如果希望A*搜索01规划的解，那么首先需要将解空间定义为树型结构，利用链式二叉堆(LBH, Linked Binary Heap)，或者二叉堆（参加前面帖子）作为Open表，哈希表作为Close表（或者我自己设计的一种数据结构）。

求解的基本思路为：从树根节点开始搜索，不断从Open表中获取当前最好解进行派生，选出符合条件的子节点加入Open，并利用Close表排除重复节点。在搜索过程中动态更新“削枝”条件，以迅速缩小解空间。

1. 解空间的定义

本帖将解空间定义为树型结构（k叉树，本帖k=27，如图 1所示）：

1. 将所有Current condition的Strategies分别按照Score由高到低排列；

2. 将所有Current condition都选择最高Score的方案作为树根Root，此解为解空间中分数最高者；

3. 对于任意一个解Solution，选出其中一个Current condition，按照1中顺序做一次“降级”（即选择相邻的，分数较低的Strategy）——那么本帖将“降级”得到的解定义为Solution的孩子节点。由此可以看出，Root将会有k个孩子节点；这k个孩子中，每个又可能有k个孩子节点（也可能小于），以此类推。

需要说明的是不同的解可能派生出相同的后代，A*在求解过程中通过Close表排除所有重复节点。

图 1案例解空间结构示意图

2. Compare函数的定义

如前文所述，传统A*算法的Open表中节点是按照估价函数F(n)从低到高保持有序的。F(n)做比节点较之用，其绝对值没有物理含义，此特性和遗传算法的适应度函数及罚函数相似。

根据0-1规划求解特点，本帖利用Compare函数替代了A*算法的估价函数和遗传算法的适应度函数，不但避免了复杂的量纲统一问题，并且更精确反应了解的优劣。

令Solution为解的类型(成员Cost为Solution的价格，Score为改进分数)，budget为用户能接受的总预算，比较函数可以定义为：

其中：

max = s1.Cost s2.Cost ? s1 : s2;

其思想为：当两个解都低于budget的时候，分数高的解优；当至少有一个解高于budget的时候，价格低的解优。

在本帖的“改良A*搜索算法”中，Open表根据“比较函数”保持有序，从优到劣。

3. 算法主要步骤

1. 如1所述，将所有Current condition的Strategies分别按照Score由高到低排列；

2. 将树根节点（即总分最高解）加入Open；

3. 若Open非空，则循环执行：

a) 取出当前最优解s = Open.Pop()；

b) 当s .Cost <= budget时：更新当前最优解集合，若找到更好解, 清理Open表CleanUpOpen();

c) 若s可派生后代，即IsExpandable(s, true)返回true，则生成其所有孩子c_i(i=1,2,…,k)，将IsExpandable(c_i, false) 为true者加入Open表；

1.3.1 IsExpandable函数定义

令highestScore为当前解的最高分，则IsExpandable函数可定义为：

bool IsExpandable(Solution s, bool add2Close)

1. 若s.Score < highestScore，返回 false，代表s小于当前最好解的，进行剪枝；

2. 若s已在Close表中，返回 false，忽略已经处理过的解；反之,如果add2Close为true，将s加入Close;

3. 返回true, 此解可派生后代；

1.3.2 CleanUpOpen函数定义

利用Lambda表达式，CleanUpOpen()函数可定义为：

void CleanUpOpen()

1. open.Delete( so => !IsExpandable(so, false) );

2. 返回。

其含义为：根据当前条件，清除Open表中所有不可派生节点。

4. A* 算法求解历程

图 2显示了在用户预算为580,465的条件下，A* 算法从根节点(Score = 43.8, Cost = 812,832)，沿可能最优的分支查找，耗时8秒最终到找到最优解(Score = 40.9, Cost = 527,532)的历程。

图 2 A* 算法求解历程

图2可以近一步说明，A*算法依照Compare函数规则，迭代过程中每次从Open表中取出最优节点进行分支，能够迅速从树根达到用户预算附近的分支进行查找，因而在大多数情况下，它能在短时间内找到最优解。

当然也存在例外，如：某些全局最优解可能比较“隐蔽”，也就是说，它的“前辈节点”都比较差。在这种情况下，A*可能需要花费比较长的时间，以此可以通过遗传算法的变异机制来弥补。

编程之美学习连载之十三：4.4 离散优化问题搜索框架 overview

2009-10-14T05:39:00Z

本帖概要说明基本思路，名字取得不一定恰当：）

启发式搜索算法A* （可参考http://theory.stanford.edu/~amitp/GameProgramming/）和遗传算法GA分别是精确搜索和近似搜索，两者原理完全不同。但是在研究过程中我发现，它们却有着内在的联系，如数据结构上非常相似，几乎可以一一对应，如下表：

前者原理是在一棵搜索树上，通过启发函数“直捣黄龙”，并尽量“砍枝”；后者原理是“养活”一群物种，通过适应度函数“物竞天择”，尽量保持多样化，让它们交叉，子代尽量继承父代优良基因，并通过变异来跳出局部最优。

若将两个算法并行求解，找到更好的解通知对方：GA可以用来繁殖出更好的解；A*可以提高“砍枝条件”。GA 虽然是近似求解，但是拥有的变异机制常常可以跳出局部最优，因此两种算法结合可以优势互补，我们暂且称此算法为GA*

*注，可能有同学会觉得奇怪，A*是用来规划路径的，怎么拖这里来了，其实改造下它可以用到好多地方。

总体思路如上图，对于一个离散型优化问题：

在一定条件下，A*, GA, GA*三种算法都可以独立求解；
若解空间可以组织成树型结构，那么就可以采用A*精确求解（当然其他两种也可以了）；
若解空间可以组织成树型结构，但是解空间太大，那么可以采用GA*混合求解；
若解空间无法列举，可以尝试设计GA。可以看出，其普适性最广，唯一缺点是不保证最优。

这个搜索框架具备良好的可扩展性，可以解决很多问题，下面简单列出UML类图，后续连载再step by step解释吧：）

复杂性科学——挑战牛顿时代以来建立的科学体系

2009-10-13T08:50:00Z

无论在设计系统和算法时、还是软件开发过程中，我都感到非常受益于复杂性科学思想的指导。

复杂适应系统、多智能体仿真也是我博士研究的主攻方向之一。

为了方便后续连载中的算法解释，本帖先对复杂性科学做简单介绍。

什么是复杂性科学？

“复杂性科学”是继：

1、“老三论” （一般系统论、信息论、控制论）

2、“新三论” （耗散结构、协同学、突变论）

3、“混沌理论”

之后的第四代系统科学理论，被誉为“21世纪的科学” 。

既然这么讲，21世纪之前的科学是什么呢？

还原论

还原论（Reductionism）主张把高级运动形式还原为低级运动形式的一种哲学观点。牛顿在其代表作《原理》第一版中，多次表示，认为机械运动是自然现象的终点，一切自然现象都可以还原，归结为机械运动。

基于还原论的思想，从哲学、化学、物理、医学到生物学、心理学...人们建立了一整套科学体系，可谓成绩斐然，奠定了当代人类文明的基础。

简单来说，其核心思想是：分割＋分析，那么分割体现在哪些地方？

1. 研究方法：例如从“物体->分子->原子….”研究下去，试图通过分析微粒来理解整体的行为；

2. 科学体系的分割：大家都知道Ph.D.是博士，其实代表的是哲学和医学，在古代科学体系没有如此细的分割。

随着科学的发展，“还原论”出现了什么问题？

还原论的缺陷

1. 对分割的“微粒”了解以后，就能了解整体么？

2. 割裂了学科之间的应有的联系－－而在当代学科之间的“交叉，融合”越来越多，例如：2002 年诺贝尔经济学奖获得主卡尼曼将经济学和心理学结合起来创立“前景理论”，从而指明了经济学发展的新方向。

3.人们发现了“还原论误区”－其至上而下的“简化思维方式”，无法解释现实生活中遇到的大量问题，越来越不适应对复杂问题的理解（最初最活跃的是经济学领域）。

复杂性科学的创立与发展

80年代美国，几位在物理学和经济学不同领域的诺贝尔奖金的获得者，盖尔曼（Gell-Mann）,安德森（Anderson）、阿诺（KArrow），认识到复杂系统的重要意义，并聚集了一批物理、经济、生物、计算机等方面的研究人员，在SantaFe成立了一个研究所，这就是著名的桑塔费研究所（简称SFI，http://www.santafe.edu/ ），并将研究复杂系统的这一学科称为复杂性科学（Complexity Seience）。

80年代我国，钱学森以其深刻的洞察力，预见到复杂系统的意义及发展。他提出了“开放的复杂巨系统”的概念，并于1992年，对于复杂系统的研究方法，提出“从定性到定量的综合集成研讨厅体系”的设想。后来的戴汝为院士在此领域做了许多研究。

复杂系统涵盖极广，几乎无处不在

无论是生物系统、经济系统、生态系统，还是人工复杂系统（计算机系统、计算机网络等）都属于复杂性科学的研究范围。

集智俱乐部上面有一些比较好的基础介绍http://www.swarmagents.com/complex/

下面我们来举几个实际例子，说明复杂性科学相关研究情况。

六度空间理论

1967年，哈佛大学的社会心理学家米尔格兰姆(Stanley Milgram)就设计了一个连锁信件实验。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的160个人，信中放了一个波士顿股票经纪人的名字，信中要求每个收信人将这套信寄给自己认为是比较接近那个股票经纪人的朋友。朋友收信后照此办理。最终，大部分信在经过五、六个步骤后都抵达了该股票经纪人。六度空间的概念由此而来。

这个连锁实验，体现了一个似乎很普遍的客观规律：社会化的现代人类社会成员之间，都可能通过“六度空间” 而联系起来，绝对没有联系的A与B是不存在的。这是一个更典型、深刻而且普遍的自然现象。那么，怎样用数学理论揭示 “六度分隔现象”？这是现代数学领域又一个重大的数学猜想。

不管理论如何深奥，“六度分隔”和互联网的亲密结合，已经开始显露出商业价值。人们在近几年越来越关注社会网络的研究，很多网络软件也开始支持人们建立更加互信和紧密的社会关联，这些软件被统称为“社会性软件”（Social Software）。

此研究属于；“复杂性科学/复杂网络/小世界网络”。

Internet研究

尽管万维网在通讯中越来越重要，但它仍然不可控。因为任何个人或机构都能够建立起一个带有任意数量网页和连接的网站。这种不规则地增长将产生一个巨大而又复杂的网络。

获取该网络一张完整的拓扑结构图的困难程度由商业搜索引擎的有限性充分显示出来，北部之光（Northern Light）搜索引擎具有最大的覆盖范围，估计只能检索该网络的38％。尽管在绘制和表示互联网基础结构特性方面已做了大量工作，但在搜索信息中网络拓扑结构实质是什么仍知之甚少。

Réka Albert, Hawoong Jeong等学者，通过研究求得了当前Internet的直径为18.59，说明在网络中任选两个网页，从一个网页平均点击19次就可找到另一个网页。

我利用复杂系统思想解决的问题

在研究过程中，我利用复杂系统思想解决了许多实际问题：

1. 大型整数规划求解，进而扩展到一般离散型优化问题的搜索。

2. 物流配送线路优化问题，即车辆路线问题（VRP，Vehicle Routing Problem）是组合优化领域中的著NP问题。可以看作TSP（Travelling salesman problem）的可扩展。

3. 多智能体行人仿真系统，和针对城市轨道交通网络的辅助决策系统…

4. …

创新

个人觉得比较大的创新往往来自于对问题“回溯”（武学里面称之为“万法归宗”，可谓最高境界），不固步自封，不限于当前视野，out of box，保持开放心态，博取众家之长。

后续连载如有机会，我想具体介绍主要算法，希望对大家有参考，也欢迎批评指正。