郭的秀

youxiedongxinengyindaohenduodongxidaodian，youxiezuodebiqitadehao；dazaoshishijidezhuangbei，tishengjiaosezhandouli，qianghuajineng，shuchushanghaibaobiao。zhuanmenweizhongduoyueyewanjiadazaodezhuanshufulijiashiyouxi。liyongjibandeshuxingzuhedapeitiaozhanqiangdamolongyouxidezhengtishifeichangdeyouqude，duozhongbutongdechangjingdengdaizhenidedaolai，jiarudaochuangyishizudeyouxishijieba。破(po)解(jie)60年(nian)前(qian)謎(mi)題(ti)！哥(ge)本(ben)哈(ha)根(gen)大(da)學(xue)研(yan)究(jiu)人(ren)員(yuan)解決(jue)「單(dan)源(yuan)最(zui)短(duan)路(lu)徑(jing)」問(wen)题

新(xin)智(zhi)元(yuan)報(bao)道(dao)

編(bian)輯(ji)：昕(xin)朋(peng)

【新智元導(dao)讀(du)】半(ban)個(ge)世(shi)紀(ji)以(yi)來(lai)，全(quan)世界(jie)的(de)研究人员都(dou)在(zai)努(nu)力(li)解决「单源最短路径」算(suan)法(fa)问题，近(jin)日(ri)，哥本哈根大学的研究人员成(cheng)功(gong)將(jiang)其(qi)解决。

「在壹(yi)个帶(dai)權(quan)有(you)向(xiang)圖(tu)G=(V,E)中(zhong)，每(mei)條(tiao)邊(bian)的权是(shi)一个實(shi)數(shu)。另(ling)外(wai)，還(hai)給(gei)定(ding)V中的一个頂(ding)點(dian)，稱(cheng)為(wei)源。

計(ji)算從(cong)源到(dao)其他(ta)所(suo)有各(ge)顶点的最短路径長(chang)度(du)，這(zhe)就(jiu)是单源最短路径（SSSP）问题。」

半个多(duo)世纪以来，世界各地(di)的研究人员一直(zhi)在努力解决这个问题。而(er)現(xian)在，該(gai)算法谜题終(zhong)於(yu)被(bei)哥本哈根大学计算機(ji)科(ke)学系(xi)的研究團(tuan)隊(dui)成功解决。

負(fu)权值(zhi)SSSP算法：速(su)度快(kuai)、效(xiao)率(lv)高(gao)

論(lun)文(wen)鏈(lian)接(jie)：https://arxiv.org/abs/2203.03456

接受(shou)采(cai)訪(fang)時(shi)，研究人员Christian Wulff-Nilsen称，他們(men)的解决方(fang)案(an)是第(di)一个突(tu)破存(cun)在30多年的 ? ( n (4/3) log W )運(yun)算时間(jian)約(yue)束(shu)的，带有负权值的SSSP組(zu)合(he)算法。

關(guan)于SSSP有兩(liang)个經(jing)典(dian)算法：Dijkstra算法（迪(di)克(ke)斯(si)特(te)拉(la)算法）和(he)Bellman-Ford算法（貝(bei)爾(er)曼(man)-福(fu)特算法），两者(zhe)都有各自(zi)的局(ju)限(xian)性(xing)。

Dijkstra算法运算时间最短，能(neng)達(da)到近線(xian)性时间 O ( m + n log n ) ，但(dan)不(bu)能计算负权值边。

Bellman-Ford算法可(ke)以计算负权值边，但运算时间過(guo)长，达到 O ( mn )。目(mu)前，最顶尖(jian)的解决负权边的SSSP算法都依(yi)賴(lai)于復(fu)雜(za)的連(lian)續(xu)優(you)化(hua)和動(dong)態(tai)代(dai)数和图形(xing)算法。这就导致(zhi)即(ji)使(shi)後(hou)世学者不斷(duan)优化该算法，其运算时间仍(reng)需(xu) ? ( n (4/3) log W )。这个运算时间的约束已(yi)经存在三(san)十(shi)年之(zhi)久(jiu)。

面(mian)對(dui)这些(xie)局限，Wulff-Nilsen提(ti)出(chu)了(le)两个问题：

1）带负权边算法的运算能否(fou)达到近线性时间？

2）能否用(yong)簡(jian)单的工(gong)具(ju)达到这个目的？

有沒(mei)有一種(zhong)方法，可以既(ji)要(yao)时间，又(you)要質(zhi)量(liang)呢(ne)？

別(bie)說(shuo)，还真(zhen)有。

Wulff-Nilsen提出的算法为图像(xiang)縮(suo)放(fang)算法，被简易(yi)图像分(fen)解算法Low Diameter Decomposition強(qiang)化。通(tong)常(chang)情(qing)況(kuang)，该分解算法只(zhi)用于非(fei)负权边的图形分解，而该研究的貢(gong)獻(xian)之一就在于将其运用到负权边图像中，加(jia)强负权边SSSP遞(di)歸(gui)缩放算法。

推(tui)导过程(cheng)

Wulff-Nilsen以Johnson的價(jia)格(ge)算法为基(ji)礎(chu)。提出：在图像 G = ( V, E, w )中，令(ling) Φ 为任(ren)意(yi)函(han)数： V→Z 。令 w(Φ) 为权函数：

定義(yi)：， 則(ze)：。 在图像G = (V, E, w )和图像G' = (V, E, w' )中，若(ruo)：1）图像G 中的最短距(ju)離(li)與(yu)图像G’ 中的最短距离相(xiang)等(deng)，反(fan)之亦(yi)然(ran)；2）G 只在G' 含(han)有负权環(huan)时含有负权环，则图像G 与图像G' 相等。

推论2.7考(kao)慮(lv)到任意图像和价格函数Φ 。在 u, v ∈ V 中，

。 而在任意环C 中，

。 因(yin)此(ci)，G 和相等。如(ru)果(guo)， ， 那(na)麽(me)G 和G' 相等。

该算法的目的是在计算价格函数Φ 时，在GΦ 中的所有边权都为非负，假(jia)設(she)不存在负权环。之后就可以在上(shang)运行(xing)Dijkstra算法。

之后，Wulff-Nilsen開(kai)始(shi)介(jie)紹(shao)自己(ji)的算法框(kuang)架(jia)。

首(shou)先(xian)，Wulff-Nilsen假设存在一种算法 Dijkstra（ G,s ），輸(shu)入(ru)無(wu)负权边的图形 G ，顶点 s ∈ V ， G 中的s输出最短路径樹(shu)。运行时间为 O ( m + n log n )。

如果 G 是一个DAG（有向无环图），计算一个价格函数 Φ ，使 具有非负权边是很(hen)简单的：只需在拓(tuo)撲(pu)的v1, ..., vn上循(xun)环，並(bing)设置(zhi) Φ(vi) ，使所有進(jin)入的边权值为非负。

单源最短路径问题的目的是找(zhao)到从给定起(qi)始節(jie)点到網(wang)絡(luo)中所有其他节点的最短路径。

网络表(biao)示(shi)为由(you)节点和它(ta)们之间的连接组成的图形，称为边。

每条边都有一个方向（例(li)如，这可用于表示单向道路）以及(ji)一个权重(zhong)，用于表示沿(yan)该边行駛(shi)的成本。如果所有边权重都是非负的，则可以使用经典的Dijkstra算法在幾(ji)乎(hu)线性的时间內(nei)解决问题。

新結(jie)果在与Dijkstra算法几乎相同(tong)的时间内解决了这个问题，但也(ye)允(yun)許(xu)负边权重。

之后，Wulff-Nilsen提到了组合工具中最重要的两个算法： ScaleDown和 SPmain。

ScaleDown算法分階(jie)段(duan)运行，在最后一个阶段它用ElimNeg（

） 来计算价格函数Φ 2。如果ElimNeg终止(zhi)，它将返(fan)回(hui)价格函数ψ′， 讓(rang)

所有边值非负；換(huan)句(ju)話(hua)说，因为， 所以

中不包(bao)含负权值。

这意味(wei)著(zhe)，对于所有 ， 都滿(man)足(zu)条件(jian)（因为 ）。由此證(zheng)明(ming)了 ScaleDown输出的正(zheng)確(que)性。

如果算法终止，则对于所有 和 ， 是積(ji)分，并且(qie)对于所有， 。

这意味着对于所有 ， 。 因此图形G* 具有非负权值。

通过归納(na)法，假设该理(li)论適(shi)用于

， 算法第5行中对ScaleDown

的調(tiao)用满足必(bi)要的输入屬(shu)性。

因此，通过和ScaleDown的Output，可以得(de)到。

由于， 若令 C 为 中任意负权环，由于中的 所有权值都为2n的倍(bei)数，且； 又知(zhi)， 故(gu)与推论2.7不符(fu)。

从而得出结论：如果包含负权环，则算法不會(hui)终止。

由此可以证明，SPmain算法的正确性。

至(zhi)此，Wulff-Nilsen的负权值SSSP解决方案中最重要的两个算法均(jun)证明成立(li)。新算法在保(bao)证近线性时间的同时，成功引(yin)入了负权值。

60年后，尋(xun)求(qiu)答(da)案不僅(jin)为了解谜

去(qu)年，Wulff-Nilsen在同一領(ling)域(yu)取(qu)得了另一項(xiang)突破，结果涉(she)及如何(he)在隨(sui)时间變(bian)化的网络中找到最短路径。他对最近谜語(yu)的解决方案建(jian)立在这项工作(zuo)的基础上。

他認(ren)为，解决SSSP问题可以为算法鋪(pu)平(ping)道路，不仅可以幫(bang)助(zhu)電(dian)动汽(qi)車(che)立即计算到达目的地的最快路线，而且能保证以最节能的方式(shi)做(zuo)到这一点。

Wulff-Nilsen解釋(shi)道：“我(wo)们的算法裏(li)加入了负权这个以前算法没有的維(wei)度。一个实際(ji)的例子(zi)是在山(shan)间駕(jia)驶时，有了负权这一维度，导航(hang)系統(tong)可以为电动车车主(zhu)推薦(jian)下(xia)坡(po)路多的路线，使电动车可以在下坡时进行充(chong)电。”

Wulff-Nilsen还表示，他们的算法不仅可以用于电动车路线規(gui)劃(hua)，还能用于監(jian)測(ce)金(jin)融(rong)業(ye)的投(tou)机行为。他说：“原(yuan)则上，该算法可以用来为中央(yang)銀(yin)行等用戶(hu)預(yu)警(jing)，警告(gao)投机者在投机買(mai)賣(mai)各种貨(huo)幣(bi)。现在，很多不法之徒(tu)利(li)用计算机犯(fan)罪(zui)，但由于我们的算法如此之快，或(huo)许能夠(gou)被用来监测，在人们利用漏(lou)洞(dong)之前及时發(fa)现。”

1959年，當(dang)Dijkstra首次(ci)提出最短距离问题时，可能他也不会想(xiang)到，60多年来，一直有人不断优化这一问题的方案。或许也会驚(jing)訝(ya)，谜题的答案竟(jing)然有如此豐(feng)富(fu)的内涵(han)。

或许，这就是科学的魅(mei)力吧(ba)。

參(can)考資(zi)料(liao)：

https://techxplore.com/news/2022-11-scientists-succeed-algorithmic-riddle-1950s.html

https://science.ku.dk/english/press/news/2022/ucph-researcher-lauded-for-superb-solution-of-algorithmic-riddle-from-the-1950s/返回搜(sou)狐(hu)，查(zha)看(kan)更(geng)多

責(ze)任编辑：