如何设计一个吸引顾客的服装网站首页，并包含有效的网站建设知识库？

服装网站首页设计,网站建设 知识库,导航网站的网站地图怎么做,公司建立网站怎么做分录目录 一、单源最短路径1.1 算法基本思想1.2 算法设计思想1.3 算法的正确性和计算复杂性1.4 归纳证明思路1.5 归纳步骤证明 二、最小生成树2.1 最小生成树性质2.1.1 生成树的性质2.1.2 生成树性质的应用 2.2 Prim算法2.2.1 正确性证明2.2.2 归纳基础2.2.3 归纳步骤2.3 Kruskal算… 目录 一、单源最短路径1.1 算法基本思想1.2 算法设计思想1.3 算法的正确性和计算复杂性1.4 归纳证明思路1.5 归纳步骤证明 二、最小生成树2.1 最小生成树性质2.1.1 生成树的性质2.1.2 生成树性质的应用 2.2 Prim算法2.2.1 正确性证明2.2.2 归纳基础2.2.3 归纳步骤2.3 Kruskal算法2.3.1 证明思路2.3.2 归纳步骤证明2.3.3 T是G的最小生成树 2.4 应用数据分组问题2.5 单链聚类 三、多机调度问题四、小结 一、单源最短路径 给定带权有向图G (V,E)其中每条边的权是非负实数。另外还给定V中的一个顶点称为源。现在 要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 1.1 算法基本思想 Dijkstra算法是解单源最短路径问题的贪心算法。   Dijkstra算法有关概念   X∈S←→x∈V且从s到x的最短路径已经找到   初始S{s},SV时算法结束   从s到u相对于S的最短路径从s到u且经过S中顶点的最短路径   dist[u]从s到u相对S最短路径的长度   short[u]从s到u的最短路径的长度   dist[u]short[u] 1.2 算法设计思想 输入有向图G(V,E)V{1,2,…,n},s1   输出从s到每个顶点的最短路径   1.初始S{1}   2.对于i∈V-S计算1到i的相对S的最短路长度dist[i]没有路可记为∞或maxint   3.选择V-S中dist值最小的j将j加入S修改V-S中顶点的dist值   4.继续上述过程直到SV为止 其基本思想是设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。   初始时S中仅含有源。设u是G的某一个顶点把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u将u添加到S中同时对数组dist作必要的修改。一旦S包含了所有V中顶点dist就记录了从源到所有其它顶点之间的最短路径长度。 例如对 右图中的有向图应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。   Dijkstra算法的迭代过程 1.3 算法的正确性和计算复杂性 (1)贪心选择性质   (2)最优子结构性质   (3)计算复杂性   对于具有n个顶点和e条边的带权有向图如果用带权邻接矩阵表示这个图那么Dijkstra算法的主循环体 需要时间。这个循环需要执行n-1次所以完成循环需要时间。算法的其余部分所需要时间不超过。 1.4 归纳证明思路 命题当算法进行到第k步时对于S中每个结点idist[i]short[i]   归纳基础   k1,S{s},dist[s]short[s]0   归纳步骤   证明假设命题对k为真则对k1命题也为真 1.5 归纳步骤证明 假设命题对k为真考虑k1步算法选择顶点v边u,v。需要证明dist[v]short[v] 若存在另一条s-v路径L最后一次出S的顶点为x经过V-s的第一个顶点y再由y经过一段在V-S中的路径到达v 二、最小生成树 设G (V,E)是无向连通带权图即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中耗费最小的生成树称为G的最小生成树。   网络的最小生成树在实际中有广泛应用。例如在设计通信网络时用图的顶点表示城市用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用则最小生成树就给出了建立通信网络的最经济的方案。 2.1 最小生成树性质 用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同它们都利用了下面的最小生成树性质   设G(V,E)是连通带权图U是V的真子集。