施卫江:P/NP难题的系统论破解

选择字号:   本文共阅读 307 次 更新时间:2020-09-07 13:39:27

进入专题:   NP问题   旅行商问题   辩证法  

施卫江  

  

5.4涨落


   所谓涨落,是指对系统稳定状态(通常维持在:平衡态、对称性、线性区、时间不变性的定态)的偏离。耗散结构理论认为,事物的演化需要由“对称性破缺”来推进,涨落为系统的对称破缺提供可能,这就是“生序原理”——“通过涨落来达到有序”的原理。[18]

  

   涨落并不必然导致系统的相变、有序、演化,即不是充分条件,系统还需对其要素的涨落作出反应并进行相关选择。这是因为系统的结构有其层次性特点,不同层次其功能是各不一样,各级层次的波动是否构成要素的涨落还有待于甄别和判断。

  

   通常涨落耗散定律是发生在称为临界阈值点的附近,在表征涨落相关的空间距离上,以标度(scaling)来呈现——由涨落达成耗散,其根子在于不同要素之间相互起作用,这就要求系统必须出现“巨涨落”,促使系统突破阈值,远离平衡态。

  

   因此,突现问题的关键须从标度上看要素作用,若判定为“巨涨落”,则引起快速突现,否则系统只会作出微弱反应,滞留原有层次依旧,或以小概率而突现。

  

   TSP是一个不稳定系统,它的稳定状态唯有在未解之时。凡是试猜查询都可看作是一次随机猜对的“涨落”,都是对于原有稳定状态的瓦解。即如从n(n-1)/2条边中任意选取n条,经过非线性映射后,试猜就可以看成:该系统n个元素进行的“粒子热运动”,根据热力学相对涨落定律,其涨落度为:。可见,当n趋向于较大值时为微涨落,此即所谓“大数定律的破缺”,这就是说,复杂性系统的演化,往往具有“对初始条件的敏感依赖性”,不遵守严格的决定论。

  

   涨落现象引起的根源在于不同要素,而唯有差异性显著者才真正构成不同要素,形成作用力显著的层级“势位差”,方使得相互作用显著起来,激起巨涨落。

  

   然而TSP为无向强连通图,它的所有端点全是无差别的全连通,端点间的距离即个性差异,仅由一维数组来提供,如此靠一维来激发的涨落,前面已经论述过了,是在同一层级内的不充分开放、近平衡态、近线性区里的短程空间进行的,近似于n个变量的一次方函数关系,即近似线性型。试图将该问题的许许多多次查询(微涨落)依次累加起来,可以构成为一个猜对概率递增的算术级数系列,这系列当然是对TSP系统的稳定态进行算术级数的偏离,然而这一系列“偏离值”的累加在运气糟糕时则为耗费指数式时间,因而在多项式内难以确认有巨涨落。若使对系统“稳定态”的偏离值加大,欲达成几何级数(即非线性)的程度,以促使巨涨落,则须系统的结构成为几何问题形式的二维表达,然而TSP给出条件却莫能。

  

6.“中国邮路问题”为什么归为P类?


   中国邮路问题(Chinese postman problem, CPP)是,一个邮递员送邮件,从邮局出发要走完他负责投递的全部街道(所有街道都是双向通行的且每条街道可以经过不止一次),完成任务后返回邮局。他应按怎样的路线走,使得所走路程最短?

  

   这是一个图历遍的问题,在一个连通的无向图中寻找一最短的闭合路径,且此路径需通过所有边至少一次。解法如下:

  

   若待解图中恰有欧拉回路,因为欧拉回路通过所有的边,则任何一个欧拉回路即为此问题的解。

  

   图1  用图来模拟一个镇的街道,标示红色的路口有奇数条路通过。

  

  

   图2 所有奇数边端点组成的K4完全图。

  

  

   图3 最后的解,红色部份是新增的边及其对应的长度。

  

   若图中不存在欧拉回路,则其中必存在有奇数个边的端点,且这类的端点一定不少于2个。因此有些边需要再重覆一次,使奇数边的端点变为偶数边的端点。

  

   【图1】假设有一个镇有14条路及9个路口(路口分别编号为 1,2, …,9),其路和路口对应的图(边上的数字是各边的长度值)中有4个端点(编号 1, 3, 6 及9)有奇数个边通过,因此这个图不存在欧拉迴路。后续要作的在图中使几个边重覆,使图中所有的端点均有偶数边通过。例如若图中 {1,3} 及 {6.9} 边重复,所有的端点均有偶数边通过。不过增加的长度不一定最少。

  

   为了要确定重复哪个边可以使原图的端点都有偶数边通过,且增加长度最少。先画出所有奇数边的端点的完全图 K4【图2】,边上的数字是从一端点到另一端点(可以经过其他完全图 K4中省略的点)的最短长度。若选择边 {1,6} 及 {3,9},所有端点都经过一次,而总长度4+2=6最短。

  

   【图3】因此原来的图中,连接端点 1 和 6, 端点 3 和 9 的边再重覆一次,所有端点均有偶数个边通过(右边第 3 图)。因此任一个欧拉路径即为此问题的解答,如以下的端点顺序 (1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1) 即为一解。图中红色的部份即为重覆的边。[19]

  

   由此,中国邮路问题被确认为一个P型。我们注意到,这个问题所提供的已知条件,是一个完整的平面图——充分的二维数组:G(V,E),它的每个端点之间都是有差别的,即与临近端点的通路数各不相同,且容易辨认,如此则使解题者快速在视觉上完成“构型”,解题只需三个多项式步骤即可找到所求路径。

  

   参考文献:

   [1][德]黑格尔:《小逻辑·§192·附释》[M] 贺麟译, 上海人民出版社,2009年版。

   [2]舍勒:《人在宇宙中的地位》,贵州人民出版社,1989年版,第40页。

   [3][德]黑格尔:《小逻辑·§80》[M] 贺麟译, 上海人民出版社,2009年版。

   [4]黑格尔:《小逻辑·§80》

   [5]埃德加·莫兰:《复杂思想:自觉的科学》[M],北京大学出版社,2001年版,第159页。

   [6]黄欣荣:《复杂性科学与哲学》[M],中央编译出版社,2007年版,第11-13页。

   [7]转引自:武杰、李润珍:《对称破缺的系统学诠释》,原载《系统科学学报》2008年1期。

   [8]《维基百科》和《百度百科》中均有相关的陈述。

   [9]向成军:《浅论复杂性与思维方式革命》[J],原载《中国校外教育(下旬)》 2019年3期。

   [10]马晓苗:《哥德尔定理证明对自指悖论的化解及其自组织涌现机理》[J],原载《系统科学学报》2020年1期。

   [11]许国志主编:《系统科学与工程研究》[M],上海科技教育出版社,2000年版,第598页。

   [12]苏淼:《关于广谱哲学的交叉性学科特点》[J] , 原载《华北水利水电大学学报(社会科学版)》, 2016 年4期。

   [13]葛宇宁:《辩证法形式化的批判性思考》[J],原载《唐山学院学报》,2016年4期。

   [14][法]埃德加·莫兰:《复杂性思想导论》[M],华东师范大学出版社,2008年版,第95页。

   [15]黄欣荣:《复杂性科学与哲学》[M],中央编译出版社,2007年版,第11-13页。

   [16]转引自:武杰、李润珍:《对称破缺的系统学诠释》[J],原载《系统科学学报》2008年1期。Simon H.A. The Organization of Complex Systems [C]//Howard Patter, ed. Hierarchy Theory. Braziller, New York :1973:205.

   [17][比]普里高津:《从混沌到有序》[M],曾庆宏等译,上海译文出版社,1987年版,第25页。

   [18]武杰、李润珍:《对称破缺的系统学诠释》[J],原载《系统科学学报》2008年1期。

   [19]关于“中国邮路问题”的材料摘录自【维基百科】,经过了笔者编辑。

  

    进入专题:   NP问题   旅行商问题   辩证法  

本文责编:limei
发信站:爱思想(http://www.aisixiang.com),栏目:天益笔会 > 科学精神 > 科学专栏
本文链接:http://www.aisixiang.com/data/122791.html
文章来源:作者授权爱思想发布,转载请注明出处(http://www.aisixiang.com)。

1 推荐

在方框中输入电子邮件地址,多个邮件之间用半角逗号(,)分隔。

爱思想(aisixiang.com)网站为公益纯学术网站,旨在推动学术繁荣、塑造社会精神。
凡本网首发及经作者授权但非首发的所有作品,版权归作者本人所有。网络转载请注明作者、出处并保持完整,纸媒转载请经本网或作者本人书面授权。
凡本网注明“来源:XXX(非爱思想网)”的作品,均转载自其它媒体,转载目的在于分享信息、助推思想传播,并不代表本网赞同其观点和对其真实性负责。若作者或版权人不愿被使用,请来函指出,本网即予改正。
Powered by aisixiang.com Copyright © 2020 by aisixiang.com All Rights Reserved 爱思想 京ICP备12007865号 京公网安备11010602120014号.
工业和信息化部备案管理系统