(刚见:3月人工智能AlphaGo4比1大胜人类围棋冠军,年底Master在中盘战胜柯洁之后再虐“棋圣”聂卫平,取得55盘全胜。如此使人们发问:你到底是谁答:AlphaGoMaster都是基于图论及相关学科!因为它俩的大脑都是应用图论博士黄士杰安装的。在台湾师范大学计算机系人员专长见黄士杰的硕士博士导师林顺喜唯一研究“演算法”的并有约一半论文是图的。这台湾师范大学正校长也是计算机权威并在这里我们琼州大学是副主编的第18SCI杂志发表论文。在台湾,演算法主要是图论并如这里能改变未来,创造新纪元文明。其实下围棋就是应用图论的博弈,如此和琼州大学合作的美国第九大学学术主席既写图论也写博弈。关于图论的作用在这里见琼州大学师祖叔培养出计算机之父人工智能之父图灵,及见许多图论及哈密顿图诺贝尔奖得主的作用-也在这里见另一个计算机之父、人工智能之父冯·诺依曼也是在琼州大学师祖叔扶植下诞生,我们琼大师祖叔的图论博士的学生Perlis也是全世界第一个获得计算机诺贝尔奖的人。其实,Master横扫人类这主要仅是借助了计算机高速计算和图论算法能力-充其量也仅是某些方面的初级人工智能的试水,远远还不是什么机器的胜利或者机器智能的胜利!但世界最权威的计算机专家撰写的著名科幻小说《抗体》说NP=P被证明之后,AI即人工智能会变得强大无比这也许才使微软总裁比尔×盖茨认为人工智能或将毁灭人类,还有霍金、造火箭的马斯克也坚称人工智能将毁灭人类,而看下面NP=P唯一用哈密顿图描述!正如这里说的天翻地覆的趋势…(搜索“人工智能奖”见只有“吴文俊人工智能科学技术奖”。而吴文俊大师就是推荐我们琼州大学对世界历史上十大天才的猜想的证明在中国最权威杂志发表的。这篇第5篇参考文献是我们琼州大学的论文(前4个参考文献都是书)的哈密顿图博士学位论文摘要就说:作为子图同构哈密顿环问题在机器人路径控制、图同构问题在模式识别计算机视觉处理等具有广泛的应用价值。而“机器人路径控制、模式识别,计算机视觉处理”正是人工智能三个最关键的领域。其值得重视如搜索可见人工智能将统治世界(对这类危言也许先研究无人系统有多大的可能性)它确是当前的热门话题。而关于上面说的计算机之父、人工智能之父图灵(即FoTCS&AI,基于一个学科不可能仅凭一个人就能开创所有的方面,因此若要推选,那就只能看关键的奠基性,如在世界各国最先引用的国际人工智能学会第四届理事长 Nilsson人工智能》第一章第9页说“The first modern article dealing with the possibility of mechanizing human-style intelligence was the one by Alan Turing第一篇讨论人类智能机械化的可能性的文章是由图灵所著的。在这句之前他说:Twentieth-century logicians, including Kurt Godel, Stephen Kleene, Emil Post, Alonzo Church, and Alan Turing, formalized and clarified much of what could and could not be done with logical and computational systems20世纪的逻辑学家Kurt Godel, Stephen Kleene, Emil Post, Alonzo Church, and Turing对哪些能和哪些不能由逻辑和计算机系统完成的任务做了形式化的分类”。国际PR学会首届主席傅京孙、蔡自兴、徐光佑的《人工智能及其应用》说“ChurchTuring和其他一些人关于计算本质的思想,提供了形式推理概念与即将发明的计算机之间的联系。第一批数字计算机看来不包含任何真实智能。早在这些设计之前,ChurchTuring就已发现数子并不是计算的主要方面,它们仅是一种解释机器内部状态的方法。被称为人工智能之父的Turing,不仅创造了一个简单的通用的非数字计算模型,而且直接证明了计算机可能以某种被理解为智能的方式工作”(该书由国务委员兼科技部长宋健院士作序。中国计算机学会主席李国杰院士、中国自动化学会主席戴汝为院士、我国计算机软件开拓者董韫美院士等都发纪念傅京孙的文章,看来傅的话是权威的,而上面他开头说的“ChurchTuring和其他”应是上面Nilsson说的5人,而这5人除Post都是琼州大学祖叔Veblen直接栽培的,了不得!最下面段见人工智能最强的大学以前曾欢迎我去

上面NP=P?问题也是完全基于哈密顿图问题(迄今为止全世界尚未有谁的证明得到公认是解决这NP=P?问题。但我国对它做得最深远的属于给海南琼州大学来信的科技大省第一个指导国外博士后并用十年做了9500个实验无一失败的权威专家,我也不知道这南大院长怎么看到我的网而给我来信邀请我去给他30个博士以及其它研究人员和博士后做报告):

NP=P?问题也是美国克雷数学研究所发布的奖励百万美元千禧年难题Millennium Problems中最受关注的问题(它不仅是千禧年数学问题,更被认为是计算机的世界第一问题,特别是历史上世界十大天才之一认为“如果能证明或否定P=NP全世界的科学家可以放假七天来庆祝NP=P?问题就是仅有下面3行字描述的世界第一问题:

P vs NP Problem

If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This is the essence of the P vs NP question.

Typical of the NP problems is that of the Hamiltonian Path Problem: given N cities to visit, how can one do this without visiting a city twice? If

you give me a solution, I can easily check that it is correct. But I cannot so easily find a solution.

(这上面3行字的意思是“如果容易核对一个解是正确,是否也容易解决这问题?这是PNP问题的实质。NP问题的最优代表是哈密顿路问题:给N个城市去全都访问,如何做这访问以便任何城市都不访问2次?如果你给一个解答,我能容易核对它的正确性。但我不能如此容易发现一个解答”)

这上面3行字的其中“N个城市全都去访问,如何做这访问以便任何城市都不访问2次?”,这是哈密顿路问题的描述,即若这N个城市分别用N个点表示,则这就是N个点的哈密顿路的定义。若都没有访问2次并回到出发城市,这是哈密顿圈的定义,此时的图叫哈密顿图(这里有很多哈密顿图因判定构造等的技术途径方法成果理论…)

图论哈密顿图的重大作用就如界上最大学术视频--计算机科学的演讲视频最多-物理/化学/环境/建筑/哲学等的演讲视频也2百多、Graph Theory即“图论”竟有3百多,并除了运筹学1百多-其余如控制论、概率统计学、博弈论、优化论特别是其它数学学科的演讲视频都不到1

迄今为止,世界各国研究这问题的专家和爱好者不少,很大一部分爱好者是看到上面如此简单的三行字的描述、解决每个问题更有百万美元奖金如此即使没有长久、深入、丰富的哈密顿图以及计算复杂性理论等研究经历的也研究之(甚至对构建NP完全理论的一些基本概念都没有准确把握,却也去研究这问题。若如此,哪你研究的到底是啥问题?(按我看,只要定义、各概念和推理没有半点偏离,证明才是可靠的,这是需要在长期的研究训练中才能自发养成。首先,定义是绝对严格的东西,每一个定义的数和形的范围都不能有半点扩大和缩小,就算有一点扩大,都已是另一推广了的定义。因此,文字可以有偏好,但表达的数和形等的内涵外延的范围是绝对同一。证明过程也要遵循这样的要求。因此,起码要先掌握最基本的定义),而有些研究者甚至都没有掌握起码的与NP问题有关系的几个最直接最基本的概念如非确定型图灵机M=六元组(有穷状态集Q,字母表å包含空格符左端符,初始状态sÎQ,接受状态即停机状态集FÍQ,带上可用符号集G转移函数dQ´G®2 Q´G´{RL}。注意这里的值域即函数象集属域与其它之别)。某些非确定型图灵机M的定义是五元组、有些是七元组,这似乎很奇怪、不应该,不过用几元是基于决定性符号的选取和内含外延的范围,而且这些都是以前各沿用下来的,各类图灵机自动机等也仅是形式化的,因此只要这些定义基本一致就可以。现在我们接着说机M接受输入wÎ(å-{▷,⊔})*,是如果对某个tÎF以及aÎåu,vÎå*,初始格局(s,-w)M*(t, ua-v)非确定型图灵机M= (Q,å,d, s,{y,n})判定语言LÍ(å-{▷,⊔})*,是如果对所有wÎ(å-{▷,⊔})*①存在依赖于Mw的自然数N,使得不存在任何格局W满足(s,-w)MNW,②wÎL iff 对某个aÎåu,vÎå*(s,-w)M*(y, u,a-v)。我们说M计算函数f: (å-{▷,⊔})*↦(å-{▷,⊔})*,是如果对所有wÎ(å-{▷,⊔})*①存在依赖于Mw的自然数N,使得不存在任何格局W满足(s,-w)MNW,②(s,-w)M*(t, ua-v) iff ua=并且v=f(w) 现在可以定NP问题类了,即M存在多项式p(n)使对任何输入x,不存在M的任何格局W满足(s,-w)M p(|x|)+1W,此时被这M判定的所有语言的类都称为NP问题类。还有一个定义是从验证方面给的。其后,利用多项式归约等可确定NP完全问题,以及其它很多概念。但有相关基础的任何人要理解任何相关概念都应该不是难事,而其它概念在相关的书上都有,因此,就不必在此再列其它概念了。困难的是解决问题,就如计算机诺贝尔奖得主Hopcroft这名著上说“这是计算机最深奥的未解问题”,这可以将其相类于我们提出的比陈景润院士的宽机有准确吧解可你哥德巴赫猜想1+2进一步的猜想)。其实,要获得处理NP完全问题的更丰富的方法和技巧等,最好还是要深入地研读组合最优化方面的一些经典优秀的著作,如1963年毕业于哈佛大学的Eugene Lawler教授的组合优化(而且可看到他的学生们的博士学位论文都是做图论的);此外,1963年至今一直在普林斯顿大学任教的Steiglitz教授和他的已成为美国三院院士的组合数学博士合撰的《组合优化》著作也会非常有帮助。特别是,组合最优化是NP完全和很多复杂性等问题和概念形成的源泉。因此,这可洞察本源,其帮助就更利于培养这方面的第六感或说直觉,这对如此艰巨的问题,诚然,严格的逻辑论证和严密的检验是时时都必须居于第一位的,但没有深邃的直觉常常只能找到似是而非的表面实质。当然,上面三个证明,虽然本人相关专业基础、世界前沿工作跟踪赶超以及和本领域最前沿的权威专家合作程度虽有不同,但都不属于爱好者之类。他们肯定知道要多参考更专业的或者说本领域权威专家的证明或相关论著。不过,尽管如此,因对这艰巨问题的证明,常常渗入非常庞杂的技术方法,如此要看出论证是否严谨和环环贯通,需要非常多东西,对某些NP完全问题的证明更是很难看得透彻的,有些复杂的归化证明更是似是而非,等等。特别是一些算法的验证就是权威都常感到难确认。上面三个证明中,杜立智教授的2010年投稿至今已修改20次。而杜立智教授做为上海交大本科并是美国研究生特别是其后进行了这方面很有用的算法软件的多年研究,另外,这5年来他又一直不断修正验证等,如此就也同情他而在这说点他:基于我上面说的很难验证,因这问题的证明很难在权威期刊发表。而在一般期刊发表大家都知道肯定没有严审而和没有发表几乎无区别--也确实因已发表的绝大多数的证明--都是一些半路蹦出来的新人所作--专家们都知道不懂这问题份量和难度的人,才如此轻率。因此,我建议杜立智教授若感到相当自信了的话,可以将自已是如何处理的,主动去向一些国内外权威解释看能否说服他们来参加研讨。当然,这问题非常难验证,几次研讨也很难达成多少共认,但总比这样放在上面网好,而且或许能得到一些好建议。总之,只有这样,才能看出自已是否存在蒙在鼓里之处,或致命之处等。才知道是否有修改价值或应抛弃?(如邀请我去做报告研讨的南京航大宁院长1982年从美国回国就一直研究,另外,1988年就已研究这问题的国防科大研究生院主管招生的副院长姜新文教授最近见他这几年都为此举办研讨会。总之,一般本科出来混几年的都应懂得如何做--那做为上交大本科美国研究生后混了几十年的不可谓不知这些,他肯定仍在为此准备着。可见这问题花了5年仍不如陈景润院士的哥德巴赫猜想那般简单明了,使得现在能收获到的是付出如此多年也就只能先虚晃几枪-呐喊几声-来的阿Q自我补偿安慰。总之,到目前为止,就如教授等使用的都只能称得上是虚招--这不仅是因越研究越感到这问题之艰巨-而没有足够自信更因似乎看到自身和课题本身可能永远…才,诶

除了上面给琼州大学来信的科技大省第一个指导国外博士后的院长用了十年做了9500个实验无一失败而似乎可能证明奖励百万霉院的问题外,下面再列出几个有代表性的都是通过求解哈密顿图问题有多项式时间算法而声称证明20世纪世界排名第一的数学家提出的上面千禧年难题的中国学者的论文:

1国防科技大学研究生院主管招生的副院长姜新文教授的进展也最近也得到很多国内外权威关注

2、武汉科技大学计算机科学与技术学院杜立智教授1964年生,上海交通大学学士,纽约州立大学硕士。在美国等软件公司从事软件开发工作多年):这是杜的证明论文

朱国魂教授2005 7月至20067月日本东京工业大学担任客员研究员,他也公布了他最近的研究,他是“无所不在网络的图论应用国际会议”主席,这是朱的证明论文。以及,浙江师范大学经济与管理学院副院长段文奇教授(他的硕士学位、博士学位论文都做网络相关课题。如2008年出版182页的《网络市场环境…》,段在2010年和美国科学院院士H. E. Stanley合作这里的第146、163篇论文S的博士Barabási就是无标度网络模型的创立者),这是段的证明论文。等等

这里再附一个法教授的博客以参考之:即柳渝教授说1993年获得法国UTC计算机博士,就步入法国PJV大学的教学研究之路,并为NP理论已做了20多年寻师访友之旅。即关于“NP理论的研究,缘起于计算复杂性理论教学的奇怪经验。计算复杂性理论是计算机课程的一部分,但是这部分的讲授,却令自己困惑不已。因为每次讲完后不久,就把讲授的内容几乎忘得一干二尽,只剩下。用于研究之一的各种启发式算法虽也层出不穷,但理论与实践严重脱节,自己不禁问为什么?…”(而关于P vs NP问题,撰写“计算复杂性理论”    世界名著的世界第一的麻省理工学院SS院长Michael Sipser院士就说这问题的解决需要我们的组合数学方法技术

     附麻省理工学院Charles Leiserson Erik Demaine教授算法导论公开课,和1985-1987国际人工智能学会主席麻省里工Patrick Henry Winston教授的人工智能公开课

人工智能其它核心领域与图论的密切关系:做为人工智能核心的机器学习近年来一些经典分支已取得某些突破,一些新分支也涌现和成长,这与图论的成熟有很大关系,如对上面AlphaGo起最关键作用的神经网络与图论北京大学一级教授许进、中国人工智能学会副理事长焦李成和西电科大校长保铮院士早就说:神经网络的深入研究与发展离不开图论,神经网络的深入发展必将对图论中许多问题的进一步研究产生重要的影响等等)Graph Theory and Machine Learning图论与机器学习(关于机器学习这里网页简单介绍它的约30个领域,。我看到中国计算机学会人工智能与模式识别专业委员会一个副主任至今的论文几十篇而且全是它的其中1个领域的,感慨吗、吃惊吗?可就是能把一个领域搞精通也很重要,就比如最近很流行的对上面AlphaGo起最关键作用的源于上面神经网络的深度学习,它也基于概率图等。当然,ML的这些领域许多都有交叉,这也正是AI的特征)Applied Graph Theory in Computer Vision and Pattern Recognition计算机视觉与模式识别中的应用图论等等。设在香港的华为诺亚方舟实验室主要从事人工智能、数据挖掘研究,香港科技大学计算机系主任杨强是该室创办主任并是华人首个国际人工智能学会Fellow以及是华人唯一的国际人工智能学会Councilor-1979年成立的国际人工智能学会在他之前的33159Councilors及以上官员中竟然没有一个华人,杨强也是中国人工智能学会海外理事长,可从他的博客知道更多(国际人工智能学会原叫美国人工智能学会的前3届主席都是计算机诺贝尔奖得主,可美国计算机学会的第123届主席分别是J.H. CurtissJ.W. Mauchly Franz L. Alt,可前者查不到此人的资料、中者从这里的“Patent dispute”见他合造并凭其当上主席的计算机是剽窃别人的、后者是图论大师Karl Menger博士这里中间见图论之父Frank Harary说“Karl Menger的工作是最重要的图论结果之一-再在此的上面第5段见这里与爱因斯坦平起平坐的Kurt Gödel读研究生时和毕业几年内在Karl Menger去美国之前经常参加图论大师Karl Menger的数学研讨会),杨强攻读的硕博士都就读于这里中间段给琼大来信请求担任我们琼州大学杂志审搞人不过在杨强教授来香港科技大学工作之前更早毕业工作于哈佛大学和麻省理工学院的这里第6香港科技大学教授也曾欢迎我去,当然上面美国第9名大学也叫我去合作图算法和机器博弈学习等。最近偶尔注意一下就见人工智能今年在世界各地很多领域行的影响力在推波助浪地演化,但请注意不要被上面误导,因很多学科对人工智能的发展都能起革命性作用,尽量吸取所长为佳,

回主页