问题描述:         有一个需要使用每个资源的n个活动组成的集合S= {a1,a2,···,an },资源每次只能由一个活动使用。每个活动a都有一个开始时间和结束时间,且 0<= s < f < 。一旦被选择后,活动a就占据半开时间区间[s,f]。如果[s,f]和[s,f]互不重叠,则称两个活动是兼容的。该问题就是要找出一个由互相…

2021年5月4日 0条评论 27点热度 阅读全文

  问题描述:         有一个需要使用每个资源的n个活动组成的集合S= {a1,a2,···,an },资源每次只能由一个活动使用。每个活动a都有一个开始时间和结束时间,且 0<= s < f < 。一旦被选择后,活动a就占据半开时间区间[s,f]。如果[s,f]和[s,f]互不重叠,则称两个活动是兼容的。该问题就是要找出一个由互相…

2021年5月4日 0条评论 18点热度 阅读全文

对一个带权有向图G=(V,E),给定一个源顶点S,找出S到图中其他顶点v的最短路径即单源最短路径问题。该问题还有很多变体,像单终点最短路径、单对顶点最短路径、每对顶点间的最短路径等等。 最短路径问题是具有最优子结构的:一对顶点间的最短路径包含了该路径上的顶点间的最短路径。直观上理解,如果该路径上的两个顶点间的路径pij不是最短路径,那么用这两个顶点间的最短路径代替pij,那么就会出现一条更短的路径,与前面所说的最短路径矛盾。(具体证明参见算法导论P358)。 需要说明的是负权值边和松弛技术。Dijkstra算法是不…

2011年11月1日 0条评论 10点热度 阅读全文