文章 57
评论 106
浏览 280844
用Dijkstra算法求解无向图的最短路径

用Dijkstra算法求解无向图的最短路径

Dijkstra 算法是典型的算法。Dijkstra 算法是很有代表性的算法。Dijkstra 一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用 OPEN, CLOSE 表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。      

世界名画陈列馆问题(回溯法)

世界名画陈列馆问题(回溯法)

算法问题描述: 世界名画陈列馆问题。世界名画陈列馆由 m× n 个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右 4 个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。 算法问题形式化表示 本问题的 m*n 的陈列室的解可表示如下图所示。其中 1 代表在该陈列室设置警卫机器人哨位,0 表示未在该陈列室设置警卫机器人哨位。 最为极端的情况是所有元素的值为 1。那什么情况下是最优解呢?就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为 1 或 0,有 m*n 个元素,有 种可能满足约束条件的矩阵,要从 种可能中遍历找到满足约束条件的 1 的个数最小的矩阵。由此可见这是一个 NP 问题。这里的约束条件就是当某一个元素为 1 时,相邻的 4 个方向上的

鲜衣怒马提银枪,一日看尽长安花,此间少年。