刷题 标签

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

  |   0 评论   |   649 浏览

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

微软编程比赛里面的一道难度系数 5% 的编程题目如下:

image
image

Dijkstra 算法是用来求解图中顶点到另外其他顶点的最短路径的,根据题目,我们可以把每两个岛屿往来所花的最少金币当成图中的边权值,由此可以用 Dijkstra 算法来解决这个问题。

image

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

  |   0 评论   |   333 浏览

算法问题描述:

世界名画陈列馆问题。世界名画陈列馆由 m× n 个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右 4 个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。

算法问题形式化表示

本问题的 m*n 的陈列室的解可表示如下图所示。其中 1 代表在该陈列室设置警卫机器人哨位,0 表示未在该陈列室设置警卫机器人哨位。

问题描述

最为极端的情况是所有元素的值为 1。那什么情况下是最优解呢?就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为 1 或 0,有 m*n 个元素,有 种可能满足约束条件的矩阵,要从 种可能中遍历找到满足约束条件的 1 的个数最小的矩阵。由此可见这是一个 NP 问题。这里的约束条件就是当某一个元素为 1 时,相邻的 4 个方向上的