NP-Hard(NPH)与NP-Complete(NPC)

引言 [singlepic=18468] 上图:艺术陈列馆问题(Art Gellery Problem),是一个NP-Complete问题。这里显示了一种解,四个摄像头覆盖了整个艺术陈列馆的每个角落。 P和NP就不讲了,Assert(不明白P和NP的读者不会到达这里看到这一段话)。 P是否等于NP的问题目前仍有争论,我对算法理解不深,暂时没有自己的看法。具体的讨论可以参见:WikiPedia的P=NP?讨论。不过做点猜想的话,我觉得,从数学美的角度来看,我觉得P=NP。当然,从理性思考角度来看,就像“你觉得有没有外星人”这个问题一样,理性思考的人会毫不犹豫地给出“当然有”的答案,P不应该等于NP。当然大部分计算机科学家认为P≠NP。 If P=NP, then the world would be a profoundly different place than we…

Continue Reading →

凝聚算法在搜索引擎应用设想

同济大学 计算机软件与理论 0720080247 李征 1. 矩阵乘法最优算法 1.1 矩阵与计算机科学 数学的重要性显而易见。数学是各种科学的基础,计算机也不例外。对于计算机学科起着关键性作用的数学分支主要是离散数学,因为计算机处理的数据还是二进制的离散量,对于连续量的处理还处在模拟的阶段。 此外,计算机科学中大量分支涉比如系统结构和计算机网络等等,都需要一定的逻辑学和图论作为其研究的支撑。作为离散数学的核心,矩阵的重要性不言而喻。众多的复杂计算机模型都可以用简单的矩阵来表示,而矩阵的运算也经常代表着重要的计算机物理含义。本文研究的搜索引擎排名评价体系就是其中之一。 1.2 矩阵乘法的理论下界 设A是一个m行n列矩阵 [singlepic=14397,,center] B是另一个n行q列矩阵 [singlepic=14400,,center] 矩阵A和B的乘积是一个m行q列矩阵 [singlepic=14401,,center] 其中 [singlepic=14402,,center]…

Continue Reading →

算法设计技术复习资料

分治技术的基本思想与特点 分治技术的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。 分治法所能解决的问题一般具有以下几个特征: 该问题的规模缩小到一定的程度就可以容易地解决; 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质; 利用该问题分解出的子问题的解可以合并为该问题的解; 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。 分支-限界技术的基本思想 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。 问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜索问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。 在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。 贪心技术的基本思想与特点 贪心技术的基本思想是从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。 该技术的特点是: 不能保证求得的最后解是最佳的; 不能用来求最大或最小解问题; 只能求满足某些约束条件的可行解的范围。 在一般(非0/1)背包问题中,选择什么样的度量标准包,才能使该问题获得最优解?并以该度量为标准,给出背包问题的贪心算法。 在一般背包中,度量物品放入优先顺序的标准是该物品的单位重量的价值度。其用贪心算法描述为: 将物品按其单位重量的价值由高至低排序。…

Continue Reading →

计算机学士的成长之路

1. C语言 毫无疑问, 第一门语言是C语言. 我上大一的时候一样有疑问, 为什么中国的高校那么迂腐, 都什么年代了, 外面都Java了, 我们还在C… 还不是C++. 其实, 事实证明, 后来毕业的时候, 被人称作计算机的强人都是当年C语言程序设计考试考优的那几个人. 一个人对于C语言的态度, 其实一定程度上反映了这个人对于计算机科学和程序设计的热衷程度. 我们二三年级的班主任经常讲, 从事计算机工作, 一定要对编程抱有兴趣, 否则是无论如何也学不好的.…

Continue Reading →

一种随机单词的生成算法

记得当年注册Gmail的时候就对于Gmail的随机单词验证码生成图片比较感兴趣, 因为每次刷新, 获得的随机单词都像是一个单词, 而不是随机字符的组合, 不过就是不认识… 一度认为Google手工找了一堆难词, 然后在当中随机… 今天看Ruby Cookbook的时候极其偶然的发现一个例子, 生成可读单词的算法. 其实就是两个集合, 集合c当中保存aeiou这5个原音字母, 集合v中保存剩下的字母. 然后按照vcvcvc这样的顺序随机出字母组成一个词, 就得到一个可读的类单词. 用在验证码上不错哦~

Continue Reading →

微软MSRA电话面试(第二天)

今天中午就接到MSRA的第二个电话面试,有点奇怪,因为前面几个电话都是晚上,我一直以为微软的前辈们都按照美国时间工作…结果今天在我午睡正香的时候打来了电话,开始问了几个项目的事情,我晕晕乎乎答得语无伦次,我明白他想知道关于开发中遇到的难题,然后我是怎么克服的,无奈实在不清醒…都想不起来了,结果我想他没有得到太多想得到的吧。之后,给我出了一个简单的算法题目要求写出来,听工程院实习的同学讲,当面面试的时候都会直接写在白板上,然后由微软的人录入编译的,这样放给我自己做,我觉得还算是降低难度了吧。 题目是这样的:有一个矩阵,每个元素是一个数,要求,从左上角出发到达右下角,每次只能向右或向下,要求全路线经过的元素和最小,求出路径及这个和的值。要求分别用递归和非递归方法实现之。 结果图: 我花了一下午,写出了这个程序,幸运的是,两种方法的结果竟然相同… 哈哈~~玩笑话,放出代码: [code=’c#’] using System; using System.Collections.Generic; using System.Text; namespace Matrix { class Program { /// ///…

Continue Reading →