算法导论求n个点的最小距离
在中文算法导论649页算法：
0：把所有的点按照横坐标排序
1：用一条竖直的线L将所有的点分成两等份
2：递归算出左半部门的这段两点距离d1，右半部门的这段两点距离d2，取d=min(d1,d2) 3：算出"1个在左半部分，另外1个在右半部分"这样的点对的最短距离d3
4：结果=min(d1,d2,d3)
关键就是这第3步貌似这需要n^2的时间，把左边每1个点以及右面每1个点都相比较一下，其实奥秘就在这里。
首先，两边的点，与分割线L的距离超过d的，都可以扔掉了，其次，纵然两个点P1,P2(不妨令P1在左边，P2在右面)与分割线L的距离(程度距离)都小于d，如果它们的纵坐标之差大于d，也没戏了。
就是这两点使得搜索范围大大减小：对左半部分的，与L的距离在d之内的，每1个P1来讲：右半部分内，切合以上两个条件的点P2至多只有六个！
原因就是：
d是两个半平面各自内，任意两点的最小距离，因此在同一个半平面内，任何两点距离都不有可能超过d。
咱们又要求P1以及P2的程度距离不能超过d，垂直距离也不能超过d，在这个d*2d 的小方块内，至多只能放下六个距离不小于d的点。
因此，第3步总的比较距离的回数不超过n*6
第3步的具体做法是：
3.1删除所有到L的距离大于d的点O(n)
3.2把右半平面的点按照纵坐标y排序O(nlogn)
3.3对左半平面内的每个点P1，找出右半平面内纵坐标与P1的纵坐标的差在d以内的点P2，计算距离取最小值，算出d3 O(n*6)=O(n)
改进：咱们对3.2这个排序的O(nlogn)不太满意.
既然全部算法是递归的，咱们可以哄骗第2步的子递归中已经排好序的序列，在第3.2部合并这两个子列，这样3.2的复杂度变成了O(n)。
这样，全般算法就是O(nlogn)的。
代码如下：VC6.0下编译通过
#include"stdafx.h"
#include stdio.h
#include stdlib.h
#include math.h
#define MAX 10000
typedef struct point{
int x,y；
}POINT；
double delta=MAX；
int totalnum；
POINT mem_p1,mem_p2；
int cmx(const void*a,const void*b)//比较x坐标
{
return((POINT*)a)->x-((POINT*)b)->x；
}
int cmy(const void*a,const void*b)//比较y坐标
{
return((POINT*)a)->y-((POINT*)b)->y；
}
double min(double p1,double p2)
{
return p1 p2?p2：p1；
}
double dist(POINT s1,POINT s2)//求两点的距离
{
double dx=s1.x-s2.x；
double dy=s1.y-s2.y；
return sqrt(dx*dx+dy*dy)；
}
void rec_cl_pair(POINT a,int i,int j)
{
double temp,xx；
int k；
if(j-i 3)//小于或等于三个点的时辰可以直接求得最小距离{
qsort(a+i,j-i+1,sizeof(a[0]),cmy)；//按Y坐标自小到大排列xx=dist(a[i],a[i+1])；//两个点的距离
if(j-i= =1) //只有两个点的时侯直接返回
{
if(xx< delta)
{
mem_p1=a[i]；
mem_p2=a[i+1]；
delta=xx；
}
return；
}
double t=dist(a[i+1],a[i+2])；//有三个点的环境
if(t { mem_p1=a[i+1]； mem_p2=a[i+2]； delta=t； } t=dist(a[i],a[i+2])； if(t { mem_p1=a[i]； mem_p2=a[i+2]； delta=t； } return； } k=(i+j)/2； double middle=a[k].x；//中线点 rec_cl_pair(a,i,k)；//求左边点的最小距离 rec_cl_pair(a,k+1,j)；//求右面点的最小距离 int t=0； POINT v[100]； for(k=i；k<=j；k++) { if(a[k].x> middle-delta&&a[k].x< middle+delta) { t++； v[t]=a[k]；//存入离中线距离小于delta的点 } }//t-1为残剩点的个数 qsort(v+1,t,sizeof(v[1]),cmy)；//以Y坐标的巨细进行排序 for(k=1；k< t；k++) { for(int s=k+1；s { temp=dist(v[k],v[s])； if(temp< delta) { delta=temp； mem_p1=v[k]； mem_p2=v[s]； } } } } void close_pair(POINT a) { int n=totalnum； qsort(a+1,n,sizeof(a[1]),cmx)；//a接收的是a+1地址，按X坐标自小到大排列rec_cl_pair(a,1,n)； } void main(int argc,char*argv) { POINT*a； scanf("%d",&totalnum) ；//输入点的总数 a=(POINT*)malloc(sizeof(point)*(totalnum+1))；//多申请1个内存空间a[0]不消 for(int i=1；i=totalnum；i++) scanf("%d%d",&a[i].x,&a[i].y)；//输入点的X以及Y坐标 close_pair(a)； printf("这段点对的距离为：%.3f\n",delta)；//地址从a+1开始 printf("最短距离的两个点为：\n(%d,%d)\n(%d,%d)\n",mem_p1.x,mem_p1.y,mem_p2.x,mem_p2.y)； } Dijkstra单点对全部顶点最短路径算法 /* infinity 无穷 vertex顶点 distance 距离 matrix 建模 start 开始 point 点 goal 目标 */ /*解题大致掌握： 如找出一个起点k，n个终点，此时本程序就是解决找出从起k到1~n各个终点的最短路径。 1> 定义path_cost数组[E_N条边][3] 对应的起点，终点，两点间距离，该数组作用用来记录当前图的数据信息。 2> 定义graph_matrix数组[起点值][终点值]=路径长度，该数组作用用来建成二维表方便操作顶点；该数组下标范围为V_N即多少个顶点。 3> 定义distance数组[顶点值]=最短路径长度，作用是记录最短路径长度。 4> 定义goal[V_N+1]={0};用来记录该顶点是否被访过，1或0表示。 5> 以上声明完毕，将其path_cost信息注入到graph_matrix。 6> 根据起点k，在graph_matrix中找出起点为k的值并用distance记录，即 graph_matrix[k][i]，i为循环量。 7> 将当前原始点k到k的最短路径长度赋为0，goal[k]=1即已选择过。 重点算法： 1> 找出与k为起点的所有终点的最短路径short_distance及终点值short_vertex(顶点);条件是与之指向的终点还没选择过。 2> 此时将此点标记已选择过。 3> 找出当前最短路径+以前顶点做起点的所有终点的最短路径，条件是与之当前终点没被选择过。 重复123步。 */ /*注意：此图为有向图*/ #include #define INFINITE 9999 //无穷，或是不能到达的顶点 #define V_N 6 //6个顶点 #define E_N 10 //10条边 #define BEGIN 1 //从BEGIN起点 #define END 6 //访问的有END个终点 int graph_matrix[V_N+1][V_N+1]; //下标从1开始，图数组 int distance[V_N+1]; //下标从1开始，路径长度 void add_graph_matrix(int path_cost[]) //图建立-邻接矩阵 { int start_point; //边起点 int end_point; //边终点 for (int i=1; i<=V_N+1; i++) for (int j=1; j<=V_N+1; j++) if (i==j) graph_matrix[i][j]=0; //原顶点路径长度为0 else graph_matrix[i][j]=INFINITE; //初始非原顶点i至j路径长度为无穷大for (i=0; i { start_point=path_cost[i*3]; //读取第i条边中的起点 end_point=path_cost[i*3+1]; //读取第i条边中的终点 graph_matrix[start_point][end_point]=path_cost[i*3+2]; //模型图[起点][终点]=路径长度值 } } void print_graph_matrix() //输出图模型 { for (int i=1; i<=V_N; i++) { printf("Vertex(%d):",i); for (int j=1; j<=V_N; j++) if (graph_matrix[i][j]==INFINITE) printf("\tX"); else printf("\t%d",graph_matrix[i][j]); putchar('\n'); } } void short_path(int vertex_i, int vertex_n) { int short_vertex=vertex_i; //记录最短距离的顶点 int short_distance; //记录最短距离 int goal[V_N+1]={0}; //记录顶点是否被选取 for (int i=1; i<=vertex_n; i++) distance[i]=graph_matrix[vertex_i][i]; //找出所有与vertex_i连接的终点其值边长 goal[vertex_i]=1; //原起点被选择 distance[vertex_i]=0; //路径长度在原点为0 for (i=1; i<=vertex_n; i++) { short_distance=INFINITE; for (int j=1; j<=vertex_n; j++) //找出最短距离的顶点 if (goal[j]==0 && short_distance>distance[j]) {//当该顶点没有被选择并且当前顶点的路径长度小于当前已记录路径长度 short_distance=distance[j]; //此时记录新的最短路径长度 short_vertex=j; //记录这个的顶点 } //此时找出了与vertex_i连接的最短路径及顶点 goal[short_vertex]=1; //记录这个最短路径的顶点已被选择 for (j=1; j<=vertex_n; j++) { /*当第j个顶点没有被选择并且当前最短路径加上与当前连接的终顶点路，使之找到当前的起与终点j的最小路径*/ if(goal[j]==0&&distance[short_vertex]+graph_matrix[short_vertex][j] //记录vertex_i到这个新顶点的路径长度 } } } void main() { int path_cost[E_N][3]={{1,2,22},{1,4,80},{1,6,99},{2,3,21},{4,5,10},{5,6,25}, {3,6,14},{3,5,95},{3,4,30},{6,4,13}}; //边的数据{起点，终点，路径长度} add_graph_matrix(&path_cost[0][0]); printf("Graph Matrix:\n"); printf("Vertex[i]:\tV(1)\tV(2)\tV(3)\tV(4)\tV(5)\tV(6)\n"); print_graph_matrix(); short_path(BEGIN,END+1); putchar('\n'); for (int i=1; i<=V_N; i++) printf("Vertex(%d) from all Vertex(%d) short path is: %d\n",BEGIN,i,distance[i]); putchar('\n'); } Dijkstra算法原理主要就是已知源节点（v）和n个节点间代价函数（有向网络矩阵cost），通过不断将节点加入到一个节点子集S 中，使得经过加入S后的各节点的路径代价是最小的，直至S节点包含了所有的n个节点停止。（具体算法阐明网上很多资料）。闲话少说，直接附程序吧～ /* readme:自述文件 first,you need to input the node number, the cost matrix and the source node;首先你必须输入矩阵节点的节点数； then the program will compute the best path.程序计算最佳路径 finally,the program will output the lowest distance to the destination node, the pre-node and show the best path. */ ＃i nclude ＃i nclude //Dijkstra算法实现函数 void Dijkstra(int n,int v,int dist[],int prev[],int **cost) { int i; int j; int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值 int *s ;//定义具有最短路径的节点子集s s = (int *)malloc(sizeof(int) * n); //初始化最小路径代价和前一跳节点值 for (i = 1; i <= n; i++) { dist[i] = cost[v][i]; s[i] = 0; if (dist[i] == maxint) { prev[i] = 0; } else { prev[i] = v; } } dist[v] = 0; s[v] = 1;//源节点作为最初的s子集 for (i = 1; i < n; i++) { int temp = maxint; int u = v; //加入具有最小代价的邻居节点到s子集 for (j = 1; j <= n; j++) { if ((!s[j]) && (dist[j] < temp)) { u = j; temp = dist[j]; } } s[u] = 1; //计算加入新的节点后，更新路径使得其产生代价最短for (j = 1; j <= n; j++) { if ((!s[j]) && (cost[u][j] < maxint)) { int newdist = dist[u] + cost[u][j]; if (newdist < dist[j]) { dist[j] = newdist; prev[j] = u; } } } } } //展示最佳路径函数 void ShowPath(int n,int v,int u,int *dist,int *prev) { int j = 0; int w = u; int count = 0; int *way ; way=(int *)malloc(sizeof(int)*(n+1)); //回溯路径 while (w != v) { count++; way[count] = prev[w]; w = prev[w]; } //输出路径 printf("the best path is:\n"); for (j = count; j >= 1; j--) { printf("%d -> ",way[j]); } printf("%d\n",u); } //主函数，主要做输入输出工作 void main() { int i,j,t; int n,v,u; int **cost;//代价矩阵 int *dist;//最短路径代价 int *prev;//前一跳节点空间 printf("please input the node number: "); scanf("%d",&n); printf("please input the cost status:\n"); cost=(int **)malloc(sizeof(int)*(n+1)); for (i = 1; i <= n; i++) { cost[i]=(int *)malloc(sizeof(int)*(n+1)); } //输入代价矩阵 for (j = 1; j <= n; j++) { for (t = 1; t <= n; t++) { scanf("%d",&cost[j][t]); } } dist = (int *)malloc(sizeof(int)*n); prev = (int *)malloc(sizeof(int)*n); printf("please input the source node: "); scanf("%d",&v); //调用dijkstra算法 Dijkstra(n, v, dist, prev, cost); printf("*****************************\n"); printf("have confirm the best path\n"); printf("*****************************\n"); for(i = 1; i <= n ; i++) { if(i!=v) { printf("the distance cost from node %d to node %d is %d\n",v,i,dist[i]); printf("the pre-node of node %d is node %d \n",i,prev[i]); ShowPath(n,v,i, dist, prev); } } } Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的A* 算法和D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。 其采用的是贪心法的算法策略 大概过程： 创建两个表，OPEN, CLOSE。 OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。 1．访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。 2．从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。 3．遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。 4．重复第2和第3步,直到OPEN表为空，或找到目标点。4．重复第2和第3步,直到OPEN表为空，或找到目标点。4．重复第2和第3步,直到OPEN表为空，或找到目标点。4．重复第2和第3步,直到OPEN表为空，或找到目标点。 #include #define MaxNum 765432100 using namespace std; ifstream fin("Dijkstra.in"); ofstream fout("Dijkstra.out"); int Map[501][501]; bool is_arrived[501]; int Dist[501],From[501],Stack[501]; int p,q,k,Path,Source,Vertex,Temp,SetCard; int FindMin() { int p,Temp=0,Minm=MaxNum; for(p=1;p<=Vertex;p++) if ((Dist[p] { Temp=p; } return Temp; } int main() { memset(is_arrived,0,sizeof(is_arrived)); fin >> Source >> Vertex; for(p=1;p<=Vertex;p++) for(q=1;q<=Vertex;q++) { fin >> Map[p][q]; if (Map[p][q]==0) Map[p][q]=MaxNum; } for(p=1;p<=Vertex;p++) { Dist[p]=Map[Source][p]; if (Dist[p]!=MaxNum) From[p]=Source; else From[p]=p; } is_arrived[Source]=true; SetCard=1; do { Temp=FindMin(); if (Temp!=0) { SetCard=SetCard+1; is_arrived[Temp]=true; for(p=1;p<=Vertex;p++) if ((Dist[p]>Dist[Temp]+Map[Temp][p])&&(!is_arrived[p])) { Dist[p]=Dist[Temp]+Map[Temp][p]; From[p]=Temp; } } else break; } while (SetCard!=Vertex); for(p=1;p<=Vertex;p++) { fout << "========================\n"; fout << "Source:" << Source << "\n Target:" << p << '\n'; if (Dist[p]==MaxNum) { fout << "Distance:" << "Infinity\n"; fout << "Path:No Way!"; } else { fout << "Distance:" << Dist[p] << '\n'; k=1; Path=p; while (From[Path]!=Path) { Stack[k]=Path; Path=From[Path]; k=k+1; } fout << "Path:" << Source; for(q=k-1;q>=1;q--) fout << "-->" << Stack[q]; } fout << "\n========================\n\n"; } fin.close(); fout.close(); return 0; } Sample Input 2 7 00 20 50 30 00 00 00 20 00 25 00 00 70 00 50 25 00 40 25 50 00 30 00 40 00 55 00 00 00 00 25 55 00 10 00 00 70 50 00 10 00 00 00 00 00 00 00 00 00 Sample Output ======================== Source:2 Target:1 Path:2-->1 ======================== ======================== Source:2 Target:3 Distance:25 Path:2-->3 ======================== ======================== Source:2 Target:4 Distance:50 Path:2-->1-->4 ======================== ======================== Source:2 Target:5 Distance:50 Path:2-->3-->5 ======================== ======================== Source:2 Target:6 Distance:60 Path:2-->3-->5-->6 ======================== ======================== Source:2 Target:7 Distance:Infinity Path:No Way! ======================== 示例程序及相关子程序： void Dijkstra(int n,int[] Distance,int[] iPath) { int MinDis,u; int i,j; //从邻接矩阵复制第n个顶点可以走出的路线，就是复制第n行到Distance[] for(i=0;i { Distance=Arc[n,i]; Visited=0; }//第n个顶点被访问，因为第n个顶点是开始点 //找到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。 //相当于寻找u点，这个点不是开始点n for(i=0;i { u=0; MinDis=No; for(j=0;j if(Visited[j] == 0&&(Distance[j] { MinDis=Distance[j]; u=j; } //如范例P1871图G6，Distance=[No,No,10,No,30,100]，第一次找就是V2，所以u=2 //找完了，MinDis等于不连接，则返回。这种情况类似V5。 if(MinDis==No) return ; //确立第u个顶点将被使用，相当于Arc[v,u]+Arc[u,w]中的第u顶点。 Visited[u]=1; //寻找第u个顶点到其他所有顶点的最小路，实际就是找Arc[u,j]、j取值在[0，VerNum]。 //如果有Arc[i,u]+Arc[u,j] //实际中，因为Distance[]是要的结果，对于起始点确定的情况下，就是： //如果(Distance[u] + Arc[u,j]) <= Distance[j] 则： //Distance[j] = Distance[u] + Arc[u, j]； //而iPath[]保存了u点的编号； //同理：对新找出的路线，要设置Visited[j]=0，以后再找其他路，这个路可能别利用到。例如V3 for(j=0;j if(Visited[j]==0&&Arc[u,j] { if ((Distance[u] + Arc[u,j]) <= Distance[j]) { Distance[j] = Distance[u] + Arc[u, j]; Visited[j]=0; iPath[j] = u; } } } } //辅助函数 void Prim() { int i,m,n=0; for(i=0;i { Visited=0; T=new TreeNode(); T.Text =V; } Visited[n]++; listBox1.Items.Add (V[n]); while(Visit()>0) { if((m=MinAdjNode(n))!=-1) { T[n].Nodes.Add(T[m]); n=m; Visited[n]++; } else { n=MinNode(0); if(n>0) T[Min2].Nodes.Add(T[Min1]); Visited[n]++; } listBox1.Items.Add (V[n]); } treeView1.Nodes.Add(T[0]); } void TopoSort() { int i,n; listBox1.Items.Clear(); Stack S=new Stack(); for(i=0;i Visited=0; for(i=VerNum-1;i>=0;i--) if(InDegree(i)==0) { S.Push(i); Visited++; } while(S.Count!=0) { n=(int )S.Pop(); listBox1.Items.Add (V[n]); ClearLink(n); for(i=VerNum-1;i>=0;i--) if(Visited==0&&InDegree(i)==0) { S.Push(i); Visited++; } } } void AOE Trave(int n,TreeNode TR,int w) { int i,w0; if(OutDegree(n)==0) return; for(i=0;i if((w0=Arc[n,i])!=0) { listBox1.Items.Add (V+"\t"+(w+w0).ToString()+"\t"+i.ToString()+"\t"+n.ToString()); TreeNode T1=new TreeNode(); T1.Text =V+" [W="+(w+w0).ToString()+"]"; TR.Nodes.Add(T1); AOETrave(i,T1,w+w0); } } void AOE() { int i,w=0,m=1; TreeNode T1=new TreeNode(); for(i=0;i { Visited=0; } T1.Text =V[0]; listBox1.Items.Add ("双亲表示法显示这个生成树："); listBox1.Items.Add ("V\tW\tID\tPID"); for(i=0;i { if((w=Arc[0,i])!=0) { listBox1.Items.Add (V+"\t"+w.ToString()+"\t"+i.ToString()+"\t0"); TreeNode T2=new TreeNode(); T2.Text=V+" [W="+w.ToString()+"]"; AOETrave(i,T2,w); T1.Nodes.Add (T2); listBox1.Items.Add("\t\t树"+m.ToString()); m++; } } treeView1.Nodes.Clear(); treeView1.Nodes.Add (T1); } int IsZero() { int i; for(i=0;i if(LineIsZero(i)>=0) return i; return -1; } int LineIsZero(int n) { int i; for(i=0;i if (Arc[n,i]!=0) return i; return -1; } void DepthTraverse() { int i,m; for(i=0;i { Visited=0; T=new TreeNode(); T.Text =V; R=0; } while((m=IsZero())>=0) { if(Visited[m]==0) { listBox1.Items.Add (V[m]); R[m]=1; } Visited[m]++; DTrave(m); } for(i=0;i { if(R==1) treeView1.Nodes.Add (T); } } void DTrave(int n) { if (LineIsZero(n)<0) return; for(i=VerNum-1;i>=0;i--) if(Arc[n,i]!=0) { Arc[n,i]=0; Arc[i,n]=0; if(Visited==0) { listBox1.Items.Add (V); T[n].Nodes.Add (T); R=0; } Visited++; DTrave(i); } } void BreadthTraverse() { int i,m; for(i=0;i { Visited=0; T=new TreeNode(); T.Text =V; R=0; } while((m=IsZero())>=0) { if(Visited[m]==0) { listBox1.Items.Add (V[m]); R[m]=1; } Visited[m]++; BTrave(m); } for(i=0;i { if(R==1) treeView1.Nodes.Add (T); } } void BTrave(int n) int i; Queue Q=new Queue(); Q.Enqueue(n); while(Q.Count!=0) { for(i=0;i { if(Arc[n,i]!=0) { Arc[n,i]=0; Arc[i,n]=0; if(Visited==0) { listBox1.Items.Add(V); T[n].Nodes.Add (T); R=0; } Visited++; Q.Enqueue(i); } } n=(int )Q.Dequeue(); } } int MinNode(int vn) { int i,j,n,m,Min=No; n=-1;m=-1; for (i=vn;i for(j=0;j if(Arc[i,j]!=No&&Arc[i,j] Min=Arc[i,j];n=i;m=j; } Min1=n;Min2=m; return n; } int MinAdjNode(int n) { int i,Min,m; Min=No;m=-1; for(i=0;i if(Arc[n,i]!=No&&Visited==0&&Min>Arc[n,i]&&Visited[n]==1) Min=Arc[n,i];m=i; } return m; } int Visit() { int i,s=0; for(i=0;i if(Visited==0) s++; return s; } program dijkstra; var a:array[1..100,1..100]of integer; flag:array[1..100]of boolean; w,x,n,i,j,min,minn:integer; begin readln(n); for i:=1 to n do begin for j:=1 to n do read(a[i,j]); readln; end; fillchar(flag,sizeof(flag),false); flag[1]:=true; minn:=1; for x:=2 to n do begin min:=32767; for i:=2 to n do if (a[1,i] begin min:=a[1,i]; minn:=i; end; flag[minn]:=true; for j:=1 to n do if (j<>minn) and (a[1,minn]+a[minn,j] end; Chapter24 Michelle Bodnar,Andrew Lohr April12,2016 Exercise24.1-1 If we change our source to z and use the same ordering of edges to decide what to relax,the d values after successive iterations of relaxation are: s t x y z ∞∞∞∞0 2∞7∞0 25790 25690 24690 Theπvalues are: s t x y z NIL NIL NIL NIL NIL z NIL z NIL NIL z x z s NIL z x y s NIL z x y s NIL Now,if we change the weight of edge(z,x)to4and rerun with s as the source,we have that the d values after successive iterations of relaxation are: s t x y z 0∞∞∞∞ 06∞7∞ 06472 02472 0247?2 Theπvalues are: s t x y z NIL NIL NIL NIL NIL NIL s NIL s NIL NIL s y s t NIL x y s t NIL x y s t 1 Note that these values are exactly the same as in the worked example.The di?erence that changing this edge will cause is that there is now a negative weight cycle,which will be detected when it considers the edge(z,x)in the for loop on line5.Since x.d=4>?2+4=z.d+w(z,x),it will return false on line7. Exercise24.1-2 Suppose there is a path from s to v.Then there must be a shortest such path of lengthδ(s,v).It must have?nite length since it contains at most|V|?1 edges and each edge has?nite length.By Lemma24.2,v.d=δ(s,v)<∞upon termination.On the other hand,suppose v.d<∞when BELLMAN-FORD ter-minates.Recall that v.d is monotonically decreasing throughout the algorithm, and RELAX will update v.d only if u.d+w(u,v) Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1 第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。 给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。 插入排序算法伪代码 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 Insert A[j] into the sorted sequence A[1..j-1] 4 i ←j-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1 Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1 Chapter2 Michelle Bodnar,Andrew Lohr April12,2016 Exercise2.1-1 314159264158 314159264158 314159264158 263141594158 263141415958 263141415859 Exercise2.1-2 Algorithm1Non-increasing Insertion-Sort(A) 1:for j=2to A.length do 2:key=A[j] 3://Insert A[j]into the sorted sequence A[1..j?1]. 4:i=j?1 5:while i>0and A[i] Chapter2 Getting Start 2.1 Insertion sort 2.1.2 将Insertion-Sort 重写为按非递减顺序排序 2.1.3 计算两个n 位的二进制数组之和 2.2 Analyzing algorithms 当前n-1个元素排好序后，第n 个元素已经是最大的元素了. 最好时间和最坏时间均为2()n Θ 2.3 Designing algorithms 2.3.3 计算递归方程的解 22()2(/2)2,1k if n T n T n n if n for k =?=?+ = >? （1） 当1k =时，2n =，显然有()lg T n n n = （2） 假设当k i =时公式成立，即()lg 2lg 22i i i T n n n i ===?， 则当1k i =+，即12i n +=时， 2.3.4 给出insertion sort 的递归版本的递归式 2.3-6 使用二分查找来替代insertion-sort 中while 循环内的线性扫描，是否可以将算法的时间提高到(lg )n n Θ？ 虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但 是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2()n Θ 2.3-7 给出一个算法，使得其能在(lg )n n Θ的时间内找出在一个n 元素的整数数组内，是否存在两个元素之和为x 首先利用快速排序将数组排序，时间(lg )n n Θ，然后再进行查找： Search(A,n,x) QuickSort(A,n); i←1; j←n; while A[i]+A[j]≠x and i Chapter19 Michelle Bodnar,Andrew Lohr April12,2016 Exercise19.2-1 First,we take the subtrees rooted at24,17,and23and add them to the root list.Then,we set H.min to18.Then,we run consolidate.First this has its degree2set to the subtree rooted at18.Then the degree1is the subtree rooted at38.Then,we get a repeated subtree of degree2when we consider the one rooted at24.So,we make it a subheap by placing the24node under18. Then,we consider the heap rooted at17.This is a repeat for heaps of degree1, so we place the heap rooted https://www.doczj.com/doc/3d9839818.html,stly we consider the heap rooted at23,and then we have that all the di?erent heaps have distinct degrees and are done,setting H.min to the smallest,that is,the one rooted at17. The three heaps that we end up with in our root list are: 23 17 38 30 41 and 1 Chapter10 Michelle Bodnar,Andrew Lohr April12,2016 Exercise10.1-1 4 41 413 41 418 41 Exercise10.1-2 We will call the stacks T and R.Initially,set T.top=0and R.top=n+1. Essentially,stack T uses the?rst part of the array and stack R uses the last part of the array.In stack T,the top is the rightmost element of T.In stack R, the top is the leftmost element of R. Algorithm1PUSH(S,x) 1:if S==T then 2:if T.top+1==R.top then 3:error“over?ow” 4:else 5:T.top=T.top+1 6:T[T.top]=x 7:end if 8:end if 9:if S==R then 10:if R.top?1==T.top then 11:error“over?ow” 12:else 13:R.top=R.top?1 14:T[T.top]=x 15:end if 16:end if 1 Algorithm2POP(S) if S==T then if T.top==0then error“under?ow” else T.top=T.top?1. return T[T.top+1] end if end if if S==R then if R.top==n+1then error“under?ow” else R.top=R.top+1. return R[R.top?1] end if end if Exercise10.1-3 4 41 413 13 138 38 Exercise10.1-4 Algorithm3ENQUEUE if Q.head==Q.tail+1,or Q.head==1and Q.tail==Q.length then error“over?ow” end if Q[Q.tail]=x if Q.tail==Q.length then Q.tail=1 else Q.tail=Q.head+1 end if Exercise10.1-5 As in the example code given in the section,we will neglect to check for over?ow and under?ow errors. 2 8.2-4 :在O(1)的时间内，回答出输入的整数中有多少个落在区间[a...b]内。给出的算法的预处理时间为O(n+k) 算法思想：利用计数排序，由于在计数排序中有一个存储数值个数的临时存储区C[0...k]，利用这个数组即可。 #include Chapter16 Michelle Bodnar,Andrew Lohr April12,2016 Exercise16.1-1 The given algorithm would just stupidly compute the minimum of the O(n) numbers or return zero depending on the size of S ij.There are a possible number of subproblems that is O(n2)since we are selecting i and j so that 1≤i≤j≤n.So,the runtime would be O(n3). Exercise16.1-2 This becomes exactly the same as the original problem if we imagine time running in reverse,so it produces an optimal solution for essentially the same reasons.It is greedy because we make the best looking choice at each step. Exercise16.1-3 As a counterexample to the optimality of greedily selecting the shortest, suppose our activity times are{(1,9),(8,11),(10,20)}then,picking the shortest ?rst,we have to eliminate the other two,where if we picked the other two instead,we would have two tasks not one. As a counterexample to the optimality of greedily selecting the task that con?icts with the fewest remaining activities,suppose the activity times are {(?1,1),(2,5),(0,3),(0,3),(0,3),(4,7),(6,9),(8,11),(8,11),(8,11),(10,12)}.Then, by this greedy strategy,we would?rst pick(4,7)since it only has a two con- ?icts.However,doing so would mean that we would not be able to pick the only optimal solution of(?1,1),(2,5),(6,9),(10,12). As a counterexample to the optimality of greedily selecting the earliest start times,suppose our activity times are{(1,10),(2,3),(4,5)}.If we pick the ear-liest start time,we will only have a single activity,(1,10),whereas the optimal solution would be to pick the two other activities. Exercise16.1-4 Maintain a set of free(but already used)lecture halls F and currently busy lecture halls B.Sort the classes by start time.For each new start time which you encounter,remove a lecture hall from F,schedule the class in that room, 1 Chapter17 Michelle Bodnar,Andrew Lohr April12,2016 Exercise17.1-1 It woudn’t because we could make an arbitrary sequence of MULT IP USH(k),MULT IP OP(k). The cost of each will beΘ(k),so the average runtime of each will beΘ(k)not O(1). Exercise17.1-2 Suppose the input is a1followed by k?1zeros.If we call DECREMENT we must change k entries.If we then call INCREMENT on this it reverses these k changes.Thus,by calling them alternately n times,the total time isΘ(nk). Exercise17.1-3 Note that this setup is similar to the dynamic tables discussed in section 17.4.Let n be arbitrary,and have the cost of operation i be c(i).Then, n i=1c(i)= lg(n) i=1 2i+ i≤n not a power of2 1≤ lg(n) i=1 2i+n=21+ lg(n) ?1+n≤4n?1+n≤5n∈O(n) So,since to?nd the average,we divide by n,the average runtime of each com-mand is O(1). Exercise17.2-1 To every stack operation,we charge twice.First we charge the actual cost of the stack operation.Second we charge the cost of copying an element later on.Since we have the size of the stack never exceed k,and there are always k operations between backups,we always overpay by at least enough.So,the ammortized cost of the operation is constant.So,the cost of the n operation is O(n). Exercise17.2-2 1 Chapter35 Michelle Bodnar,Andrew Lohr April12,2016 Exercise35.1-1 We could select the graph that consists of only two vertices and a single edge between them.Then,the approximation algorithm will always select both of the vertices,whereas the minimum vertex cover is only one vertex.more generally,we could pick our graph to be k edges on a graph with2k vertices so that each connected component only has a single edge.In these examples,we will have that the approximate solution is o?by a factor of two from the exact one. Exercise35.1-2 It is clear that the edges picked in line4form a matching,since we can only pick edges from E ,and the edges in E are precisely those which don’t share an endpoint with any vertex already in C,and hence with any already-picked edge. Moreover,this matching is maximal because the only edges we don’t include are the ones we removed from E .We did this because they shared an endpoint with an edge we already picked,so if we added it to the matching it would no longer be a matching. Exercise35.1-3 We will construct a bipartite graph with V=R∪L.We will try to construct it so that R is uniform,not that R is a vertex cover.However,we will make it so that the heuristic that the professor(professor who?)suggests will cause us to select all the vertices in L,and show that|L|>2|R|. Initially start o?with|R|=n?xed,and L empty.Then,for each i from 2up to n,we do the following.Let k= n i .Select S a subset of the vertices of R of size ki,and so that all the vertices in R?S have a greater or equal degree.Then,we will add k vertices to L,each of degree i,so that the union of their neighborhoods is S.Note that throughout this process,the furthest apart the degrees of the vertices in R can be is1,because each time we are picking the smallest degree vertices and increasing their degrees by1.So,once this has been done for i=n,we can pick a subset of R whose degree is one less than the rest of R(or all of R if the degrees are all equal),and for each vertex in 1 1 算法导论第三次习题课 2008.12.17 2 19.1-1 如果x 是根节点：degree[sibling[x]] > sibling[x] 如果x 不是根节点：degree[sibling[x]] = sibling[x] –119.1-3 略 3 19.2-2 过程略( union 操作) 19.2-3 （1）decrease-key （2）extract-min 过程略 19.2-6 算法思想：找到堆中最小值min ，用min-1代替-∞. [遍历堆中树的根节点] 4 15.1-1 15.1-2 略P195 或P329 15.1-4 f i [j]值只依赖f i [j-1]的值，从而可以从2n 压缩为2个。再加上f*、l*、l i [j]。 Print-station(l, I, j ) //i 为线路，j 为station if j>1 then Print-station(l, l i [j], j-1 ) print “line”I, “station”j; 5 15.2-1 略（见课本） 15.2-2 15.2-4 略 MATRIX-CHAIN-MULTIPLY(A, s, i, j) if j>i x= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j), j) y= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j)+1,j) return MATRIX-MULTIPLY(x, y) else return A i 6 15.3-1 （归纳法）递归调用 枚举15.3-2 没有效果，没有重叠子问题 15.3-4 略 (3)n Ο3/2(4/) n n Θ算法导论 第三版 第24章 答案 英
算法导论 第三版 第21章 答案 英
算法导论第二章答案
算法导论 第三版 第六章 答案 英
算法导论 第三版 第七章 答案 英
算法导论 第三版 第二章 答案 英
算法导论习题答案
算法导论 第三版 第十九章 答案 英
Ch10算法导论 第三版 第十章 答案 英
算法导论 第八章答案
算法导论 第三版 第十六章 答案 英
算法导论 第三版 第十七章 答案 英
算法导论 第三版 第35章 答案 英
《算法导论2版》课后答案_加强版2
相关主题
文本预览