Category Archives: 未分类

「编程笔记」Dijkstra算法为什么无法处理带有负权边的图

前言 Dijkstra算法是一种可以计算有向或无向图中单源最短路的算法。其工作模式与图的BFS（广度优先遍历）有些相似，通过类似于广度遍历的方式，逐渐从某个设定好的起点向外推进，一步步的计算出所有点到该点的距离。 本文不过多介绍Dijkstra单源最短路算法本身，如果仍然没有掌握该算法，可以先自行了解该算法的工作模式。下面提供一些可供参考的资料： 知乎：通俗易懂理解——dijkstra算法求最短路径 负权边对于Dijkstra算法的影响 Dijkstra算法工作模式 要了解该影响，首先需要明确Dijkstra算法的工作模式。其维护两个点集合。一个是“仍未确定最优解的点（S）”，一个是“已经确定最优解的点（U）”。且有一个重点：在算法工作期间内，如果某点被认为已经得到最优解，则该点会被从S移动到U，可以认为，从此以后该点已经被Closed（关闭），即解已经确定，且不容被更改。 为了方便，我们称在S中的点为opening vertex，U中的点为closed vertex 当图中出现负权边… 了解这一点后，让我们来看看下面这个图片示例，看看当负权边出现在图中时，可能会对算法造成什么影响： 如上图，假设我们尝试使用Dijkstra算法，计算该图中各个点距离C点的距离。 图中，绿色的点为closed vertex，白色的点为opening vertex，点上方的方框代表该点的，实时更新的计算距离。 1：算法首先锁定C点，将C点到C点的距离标记为0，并认定为最优解，然后根据C点尝试更新与其相连的opening vertex的距离（这里为A，B点，得到更新后距离是为1和5）。 2：剩余的opening vertex中，A距离出发点（C点）最小，距离为1，故锁定A点，（注意：锁定A点说明算法认为A点的最优解就是1，且之后算法也不可能再次更新A点的距离值，因为A点已经为Closed状态了），同时，锁定A点之后，再次更新与A点相连的opening vertex的值（与A点相连的点有B和C，但因为C点为closed vertex，故仅仅尝试更新B点的值），计算得到B点最新距离为min(5, 1+(-10)) = -9 3：最后，锁定B点，算法计算完成。 上方便是Dijkstra算法在示例图中的运行步骤和结果。不难发现，算法对于A点的最短距离出现了计算失误：实际上，A点的最短距离走法并不是C->A (1)，而是C->B->A (-5)。 怎会如此？ 分析之后可以发现，Dijkstra算法的核心，就在于每次都选择S集合中距离最小的点，并将其锁定，再通过这个点进一步更新其他点的距离。但为什么Dijkstra认为S集合中目前距离最小的点就是最优解呢？有没有可能从其他的点出发可以得到更小的距离呢？ 比如在上述的示例图中，锁定C点后，算法认为A点的距离是1，B点的距离是5，所以A点的距离为1一定是最优解。那么有没有可能实际上1并不是C到A的最优解，我们通过B点走其他的路径最终可以得到更小的解呢？ 答案是，当边的权值非负时，不可能，当边的权值存在负值时，则有可能。 当权值非负时，B点已经离出发点有5点的距离，所以所有从出发点出发经B点的路径，其长度必定大于等于5，但是当权值存在负数的时候，这一点就无法确定，经过B点的路径如果后续经过负权边，其路径长度总和也有可能再次小于5，此时，我们就无法确定C->A的1距离一定是最优解了，因为我完全有可能经由B路径得到一条总距离小于1的路径到达A。 上方的论证可能并不全面和严谨，不能作为Dijkstra算法相关特性的严格证明，但对我们进一步理解Dijkstra算法有着一些帮助。 一些有趣的说法 不难发现，实际上Dijkstra算法的设计和「贪心」有着很大的联系，实际上在S集合中选点就是一种贪心的行为。而我们都知道贪心算法的局限性，就是在部分情况下，其可能陷入局部最优解。而我们可以认为，当Dijkstra遇上负权边，就导致了其中贪心部分陷入了局部最优解（只考虑眼前的最短边（比如在5和10两条边中毫不犹豫的选择5），而忽略了目前看似落后的边未来的长期收益（比如那条权值为10的边链接的点，接下来将经过一条绝对值非常大的负权边-10000之类的），这也警示我们不要贪图眼前的小利，眼光应当长远（雾 如果我就是想拿下负权边呢？ 噢亲爱的读者，相信我，不止你一个人有这种想法；实际上上百年前就已经有两名小伙想要拿下他，他们的名字分别是Richard Bellman 和Lester Ford Jr，接下来，就是Bellman Ford算法的表演时间了。 如果你对与这个Bellman Ford算法感兴趣，可以在互联网上找到很多关于这个算法的优质教程，其通过一次次迭代，对边进行Relaxation操作，实现了对于单源最短路径的求解，在本Blog的另外一篇文章「编程笔记」关于Bellman Ford单源最短路算法 中，也对这个算法做出了一些讨论，希望能对您产生一些帮助和启发。

NetFlix 合租商品购买须知

本商品本质山为本发卡单纯提供的代理合租服务，商品服务的全部内容是帮助客户找到车友的服务。因此除了帮助各位顾客找到车友之外，理论上本商品不再具有除此之外的任何义务。 如因NETFLIX官方政策更改而导致产品实际服务等级，服务方式，服务状态或其他任何有关产品的状态更改，本发卡概不负责。 本商品严禁倒卖，若工作人员发现购买本站账号后在任何其他平台进行倒卖的行为，我们将有权立即暂停您的账号以及其他任何相关的服务，同时不进行任何补偿。若您有意愿进行商业合作，请联系本发卡工作人员进行进一步交流，我们将欢迎您的到来。 如因用户为按照本发卡工作人员指引和要求使用该产品，如：私自更改密码，私自更改邮箱，将账号违规共享给他人，未按要求设置账户，或其他任何违规行为而导致的任何后果，本发卡概不负责。 购买NETFLIX账号后的实际使用时间将可能因为不同情况而出现差异，如不同月份由于天数不同导致兑换时的天数出现浮动，国际货币价格费率，时差等等均会对最终使用时间造成波动与影响，本商品在售时将按照理论最长使用时间进行标价，但并不代表所有购买的服务均能提供相应时长。

解密答案

第三关 访问题目链接 https://db7f8c8a61184859.fnf.rip ，可以发现有一个 “后台管理” 的按钮，点进去可以看到两行字 password : test 此网站持续建设中…… 可是事情没有那么简单，打开开发者面板，不过 html 中并没有包含其他有用的信息。不过文字只是表面，既然是后台管理，那就应该可以登录而且也给出了密码，但是并没有给出登录的表单，不过可以自己新建一个。 <form action=”/admin” method=”post”> <input name=”passwd” value=”test”> <button type=”submit”>登录</button> </form> 将这一段添加进网站中，根据网页第一行的信息，可以知道密码是 test。不过这样提交后，会返回 403 访问禁止错误。不过，在 403 页面，还有一行信息，CSRF verification failed.，CSRF (Cross-Site Request Forgery)，即跨站请求伪造的意思。如果要避免这个错误，我们需要在表单中添加 csrf_token。csrf_token 一般会存在浏览器的 cookies 中，我们打开开发者面板中的控制台，输入 document.cookie，可以看到有一个 csrftoken，其对应的值就是我们需要的 csrftoken。下一步只需将其添加进表单中就行。 <form action=”/admin” method=”post”> <input name=”csrfmiddlewaretoken” value=”获得的 csrftoken”> <input name=”passwd” value=”test”> <button type=”submit”>登录</button> </form> 这时候再将这表单插入网页，再提交，就过了。

中国古典诗词里的“人与自然”

        “人与自然”是古今中外文学的永恒主题。当我们被辛弃疾“我见青山多妩媚，料青山、见我应如是。情与貌，略相似”（《贺新郎》）的词句倾倒之时，也会被爱默生的优美文句所感动：“田野和树林给予的最大快乐是人和植物间玄妙关系的暗示。我并非独自一人，也不是没人认识我。它们向我点头，我向它们点头。”（《爱默生演讲录》，[美]爱默生著，孙宜学译，中国人民大学出版社，2003，P220）文学对自然的态度无疑是对科学主义自然观的反拨，因为科学虽然让我们更真切地发现了自然，但也让我们从合理地利用自然走向占有自然，改变自然，消费自然，破坏自然，而文学对于自然仅仅是审美的。韦勒克说：“审美经验是一种凝神观照的形式，是对审美对象的性质以及性质上的结构的一种喜爱的注意。”（《文学理论》，[美]勒内·韦勒克、奥斯汀·沃伦著，刘象愚等译，江苏教育出版社，P287）      大自然是中国古代诗人取之不尽的灵感源泉，对自然风物的吟诵和对人与自然关系的感悟，成为了中国诗歌源远流长的一个传统，《我见青山多妩媚》这部古典诗词选本就是这一传统的细致梳理。古代的诗人们决不像大多数当代人那样，只会空洞地赞美自然，或者像旅行团那样用金钱和感官消费自然。他们真正呈现了自然的美。      中国古代诗人对于自然的观察非常细致。孔子说，诗不仅可以让我们了解社会，还可以让我们“多识鸟兽草木之名”。和一切艺术美审活动一样，自然审美也需要关于审美对象的知识，但这不是自然科学的解剖和分析，而是用眼睛和心灵观察到的整体知识，是和布封《昆虫记》一样的博物学。春天，晏殊知道“燕子来时新社，梨花落后清明”（《破阵子》）；秦观也知道“有桃花红，李花白，菜花黄”，“正莺儿啼，燕儿舞，蝶儿忙”（《行香子》）。风雨之夜，春眠醒来，孟浩然断定“夜来风雨声，花落知多少”（《春晓》）；李清照则断定“应是绿肥红瘦”（《如梦令》）。细心的苏东坡发现“放生鱼鳖逐人来，无主荷花到处开”（《新城道中》）；杨万里则捕捉到了“小荷才露尖尖角，早有蜻蜓立上头”（《小池》）。      中国古代的诗人能运用出色的语言将自然描述得如画一样生动完美。诗中有画，画中有诗，是中国传统艺术的一大特色，书中几乎每一首描写自然的诗词，都是一幅山水画、花鸟画和风俗画，让我们心旷神怡。“明月松间照，清泉石上流”（王维《山居秋暝》）是清丽的山水小品；“野凫眠岸有闲意，老树着花无丑枝”（梅尧臣《东溪》）是典雅的写意花鸟；“市桥压担莼丝滑，村店堆盘豆荚肥”（陆游《初夏行平水道中》）则是乡村的年画。不仅如此，他们的诗还可以超越图画所提供的视觉审美体验：“两个黄鹂鸣翠柳，一行白鹭上青天”（杜甫《绝句》）是听觉的审美体验；“遥知不是雪，为有暗香来”（王安石《梅花》）是嗅觉的审美体验。      中国古代诗人将情感和人格转化到自然之中，写出的不仅是客观的美景，而且是丰富的心灵与自然的人性。“秋风萧瑟，洪波涌起”，是诗人壮怀激烈的投射（曹操《观沧海》）；“山光悦鸟性，潭影空人心”（常建《题破山寺后禅院》），是诗人对自性的顿悟；“相看两不厌，唯有敬亭山”（李白《独坐敬亭山》），是诗人与青山的默契；“霜禽欲下先偷眼，粉蝶如知合断魂”（林逋《山园小梅》）是诗人清高人格的反衬；“春潮带雨晚来急，野渡无人舟自横”（韦应物《滁州西涧》），是诗人无尽的寂寞与怅惘。      古人有关“人与自然”关系的感悟极具哲理内涵。早在两千多年前，中国的老子就已经思考“道法自然”。从哲学的角度看，“自然”不仅指非人为的天然的宇宙万物及其运动过程，也指思辨意义上的宇宙本体和事物的本质与本性。在中国文化中，“人与自然”的和谐也称作“天人合一”，而“天”的概念非常广泛：宇宙是万物的“天”，男女是伦理的“天”，身体血气是自我的“天”。和谐美丽的生态、和谐互爱的社会、和谐愉悦的身心都是“天人合一”的状态。因此，《我见青山多妩媚》除了选取大量歌颂大自然的山水诗词、边塞诗词，还有歌颂回归自然、回归温情的田园诗和风俗诗，陶渊明向往耕读自由的生活：“既耕亦已种，时还读我书。穷巷隔深辙，颇回故人车”（《读〈山海经〉》），“舂秫作美酒，酒熟吾自斟。弱子戏我侧，学语未成音”（《和郭主簿》）。孟浩然、陆游陶醉于“开轩面场圃，把酒话桑麻”（《过故人庄》），或者“箫鼓追随春社近，衣冠简朴古风存”的乡村田园场景。当然，还有“我本楚狂人，凤歌笑孔丘。手持绿玉杖，朝别黄鹤楼”的狂歌（李白《庐山谣寄户待御虚舟》），“痴儿了却公家事，快阁东西倚晚晴。落木千山天远大，澄江一道月分明”的逸唱（黄庭坚《登快阁》），那是心灵回到自我时的纵情与愉悦。      这本诗词选揭示了一种终极性的审美体验，即作为审美对象的自然不同于人类创造的艺术作品。自然是造物主，是我们的由来和归属，既带有原始的意味也带有终极的意味。也就是说，真正的欣赏自然的过程，不是以欣赏者为中心的，而是以自然为中心的，人类欣赏自然的过程，就是皈依自然的过程。这首先体现在语言会失去描写和形容能力。庄子说“天地有大美而不言”，突然在大自然中领悟到这种大美，邂逅到本体的诗人也不欲言。陶渊明在“采菊东篱下，悠然见南山”之际，却说“此中有真意，欲辨已忘言”（《饮酒》）；陶弘景回答皇帝说“山中何所有，岭上多白云。只可自怡悦，不堪持赠君”（《诏问山中何所有赋诗以答》）；张孝祥在“玉鉴琼田三万顷，着我扁舟一叶”之时，却道“悠然心会，妙处难与君说”（《念奴娇·过洞庭》）。其次表现为人对自然永恒性的赞美、向往和对生命短暂的无尽感伤。东晋女诗人谢道韫赞美巍峨的泰山“非工复非匠，云构发自然”；接着就感慨命运的无常“器象尔何物，遂令我屡迁”（《泰山吟》）；最后表达了回归自然怀抱的愿望“逝将宅斯宇，可以尽天年”。脍炙人口的唐诗《春江花月夜》，以青春的情思抒发于浩渺的宇宙，在“人生代代无穷己，江月年年只相似。不知江月待何人，但见长江送流水”的吟唱中，人类的生命和情感获得了永恒的意义。（徐兴无） 来源