导航最短路径查询个人总结

第一篇：导航最短路径查询个人总结

个人总结

2013110410 云丹久美

这次实践，我们小组通过一个具体的程序实践项目——导航最短路径查询，巩固了已经学习的数据结构知识。例如，对一维数组，二维数组，文件的读写，循环菜单等的巩固。让我对这个专业，这个学科也有些新的认识和更深一个层次的理解。与此同时，也让我以前不懂或是不牢固的知识在实践之中进一步的掌握了。比如我以前一直不懂动态数组的使用，这次通过这个项目的实践掌握了动态二维数组的知识。

除此之外，程序实践课程的学习也大大提高了我的应用能力，如问题分析能力，编码调试能力，团队合作能力等等。

以前刚开始学习数据结构的时候，真的不知道该怎么样才能学好它。也不知道它到底是干什么的。只是一味的认为上课跟着老师走就能把它学的很好。可是学到最后才发现其实学习编程并不是像学习理论知识那样靠死记硬背，它需要的是我们分析问题的能力和想出解决办法的思维。一些错误的思维方式可能会导致整个程序无法正确执行。在当我们被需要写一个程序时，要考虑到所有的可能性，最后从这些可能性里选择最好的解决方法。这样，数据结构提高了我们对待问题的正确思维能力。

老师为我们提供了独立思考的条件，也在上课期间为我们辛勤指导，让我们自己编代码，写程序并调试结果。通过这一过程，编码调试的能力有了些提高。来自软件公司专业的老师也让我们意识到遵守良好的编码格式，工整的编码结构很重要。

在一个小组中，每个人承担不同的功能模块。最后由小组长把这些子模快连接起来。在完成这个系统的过程中我们彼此讨论着要怎么样才能把这个功能模块做出来。团队可以让我们把彼此的想法汇总到一起，然后从每个人的理解角度来分析每个问题的错误原因。让我明白了在软件开发的过程中一个团队的重要性。当然，我也在此次的过程中认识到了自己的不足。在一开始分析数据的时候，看着这么多复杂的数据顿时觉得毫无头绪，代码调试中遇到错误时也是焦头烂额，还是会有畏难情绪的存在，需要今后大量的代码编写练习去克服。

通过这次为期7天的程序实践课程的学习，我收获了很多，也认识到了自身的不足。

总的来说，这次的程序实践课程让我受益匪浅。

第二篇：最短路径教案

13.4最短路径问题

一、教学内容：本节课的主要内容是利用轴对称研究某些最短路径问题，最短路径问题在现实生活中经常遇到，初中阶段，主要以“两点之间，线段最短”“连接直线外一点与直线上各点的所有连线中，垂线段最短”为知识基础，有时还要借助轴对称、平移、旋转等变换进行研究。

本节课以数学史中的一个经典故事----“将军饮马问题”为载体开展对“最短路径问题”的课题研究，让学生经历将实际问题抽象为数学的线段和最小问题，再利用轴对称将线段和最小问题转化为“两点之间、线段最短”的问题。

二、教学目标

1、能利用轴对称解决简单的最短路径问题

2、再谈岁最短路径的过程中，体会“轴对称”的桥梁作用，感悟转化的数学思想。

三、教学重难点

重点：利用轴对称将最短路径问题转化为“两点之间、线段最短”问题。难点：如何利用轴对称将最短路径问题转化为线段和最小问题。

四、教学问题诊断

最短路径问题从本质上说是最值问题，作为初中学生，在此前很少涉及最值问题，解决这方面问题的数学经验尚显不足，特别是面对具有实际背景的最值问题，更会感到陌生，无从下手。

解答“当点AB在直线l的同侧时，如何在l上找到点C，使AC与BC的和最小”，需要将其转化为“直线l异侧的两点，与直线l上的点的线段的和最小”的问题，为什么需要这样转化，怎样通过轴对称实现转化，一些学生会存在理解上和操作上的困难。

在证明“最短”时，需要在直线上任取一点（与所求做的点不重合），证明所连线段和大于所求作的线段和，这种思路和方法，一些学生想不到。

教学时，教师可以让学生首先思考“直线l异侧的两点，与直线l上的点的和最小”为学生搭建“脚手架”，在证明最短时，教师要适时点拨学生，让学生体会任意的作用。

五、教学过程

教师引语：现实生活中经常会有这样的生活经历，比如学校虽然为我们铺设了一些石板甬路，方便同学们的行走，但是很多时候我们却并不在这些小路上行走，这样做的目的是什么呢？（学生一起回答）如果用数学知识来解释这种行为，那就是我们曾经学习的“两点之间、线段最短”或“垂线段最短”，我们称这样的问题为最短路径问题（板书课题）现实生活中经常涉及到最短路径问题，这节课我们学习的主要任务就是最短路径问题，并用所学知识探究数学史上著名的“将军饮马问题”。

1、情境引入

相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦，有一天，有一位将军专门拜访海伦，求教一个百思不得其解的问题：从图中的A地出发，到一条笔直的河边饮马，然后到B地，到河边什么地方饮马，可使他所走的路线全程最短？精通数学、物理学的海伦稍加思索，利用轴对称的知识回答了这个问题。这个问题后来被称为“将军饮马问题”。

2、探究解决问题的方法

问题一：这是一个实际问题，我们首先把它抽象为数学问题，请同学们用自己的语言说明这个问题的意思。

师生活动：学生独立思考后小组交换意见，然后尝试回答，相互补充，最后达成共识，教师根据学生的回答写出问题的板书：如图，已知点A和点B在直线L的同侧，在直线L上找一点C，使AC与BC的和最小。

设计意图：让学生将实际问题抽象为数学问题，即将最短路径问题抽象为“线段和最小问题”。

问题二：由上面的问题我们可以联想到下面的问题：A、B分别是直线L异侧的两点，如何在直线L上找到一点C，使AC与BC的和最小？

师生活动：学生独立思考，画图分析并尝试回答，教师补充。

问题三：对于第一个问题，如何将点B移到L的另一侧，B′处，满足直线L上的任一点C，都保持CB与CB′的长度相等？ 问题四：你能利用轴对称的知识找到符合条件的点B′吗？

师生活动：学生独立考，尝试画图，然后小组交流，学生代表汇报交流成果，师生共同补充：只要作出点B关于直线L的对称点B′，就可以满足CB=CB′,再利用问题二中的方法，连接AB′,则AB′与直线L的交点即为所求。

学生叙述，教师板书并画图，同时学生在练习本上画图。

设计意图：通过搭建台阶，为学生探究问题提供“脚手架”将同侧难以解决的问题提转化为异侧容易解决的问题，渗透转化思想。

3、推理证明“最短”

问题五：你能用所学的知识证明AC+BC最短吗？

师生活动：师生共同分析，然后学生说证明过程，教师板书。

证明：在直线L上任取一点C′（与点C不重合），连接AC′,BC′,B′C′.由轴对称的性质可知，BC=B′C,BC′=B′C′.∴AC+BC=AC+ B′C=AB′, AC′+ BC′= AC′+ B′C′

在△AB′C′中，AB′＜AC′+ B′C′

∴AC+BC＜ AC′+ BC′ 即AC+BC最短。

问题六：这里任取一点C′的作用是什么？

师生活动：学生相互交流，教师适时点拨，最后达成共识：若直线L上任取一点C′与A、B两点的距离之和都大于AC+BC，则说明AC+BC最短。

设计意图：让学生进一步体会做法的正确性，提高逻辑思维能力。

问题七：回顾前面的探究过程，我们是通过怎样的过程、借助什么解决问题的？

师生共同总结：首先作其中一点关于直线的对称点，然后连接另一点与对称点之间的线段，通过轴对称将两条线段和转化到同一条线段上去，这条线段与直线的交点即为所求，整个过程利用了“轴对称”和“两点之间、线段最短“的知识。

设计意图：让学生在反思的过程中，体会轴对称的“桥梁”作用，感悟转化思想，丰富数学活动经验。

4、巩固练习

（1）如图，一艘旅游船从大桥AB的P处前往山脚下的Q处接游客，然后将游客送往河岸BC上，再回到P处，请画出旅游船的最短路径。

师生活动：学生分析解题思路，并相互补充，然后独立完成画图，学生代表上台讲解。基本思路分析：此题中轮船的行走路线共有三段，其中PQ是必经路段，由“两点之间，线段最短”需首先连接PQ，再将河岸BC看成一条直线，这样问题就转化为“点P、Q在直线BC同侧，如何在BC上找一点R，使PR+QR最小”。

设计意图：让学生进一步巩固解决最短路径问题的基本策略和基本方法。

（2）如图，∠XOY内有一点P，在射线OX上找出一点M，在射线OY上找出一点N，使PM+MN+NP最短．

分析：此题的出题背景就是角。本题主要利用了两点之间线段最短的性质通过轴对称图形的性质确定三角形的另两点．

分别以直线OX、OY为对称轴，作点P的对应点P1与P2，连接P1P2交OX于M，交OY于N，则PM+MN+NP最短．

5、课堂小结：教师与学生一起回顾本节课所学主要内容，并请学生回答：（1）本节课研究问题的基本过程是什么？（2）轴对称在所研究的问题中起到什么作用？

6、布置作业：《课时练》第49页1、2、3、4、5、7、8、9

第三篇：《最短路径》教学反思

11月23号下午第三节，我讲了公开课《最短路径》第一课时，学校领导及没课的老师来到报告厅听课，听课后田校长对我讲的这一节课经行了点评，我受益匪浅，所以把感悟以及所学到的总结如下：

1、问题设计要有启发性。在设计问题的时候不可以设计无用的问题，要让学生真正有所思考，并且可以经过思考可以得到结论，在设计问题的时候也不要设计太难的问题，打击学生的积极性，要把难的问题分解，解剖成简单的小问题一步步来解决。

2、课堂引入，要更加的正规，不能太随意。比如在引入的时候可以用蚂蚁找食物的实例引入，可以更形象。

3、引入之后，要复习预备知识。因为所有的知识都是在旧知识的基础上生成的，如果说新知识是冰川露出大海的部分，那旧知识就是藏在大海中的更大的部分，所以要强调从旧知识的基础上生成新知识，调动旧知识环境，衍生新知识，这样有利于学生形成数学体系，所学的内容也不会让学生感觉太突兀，而是自然而然的得到。所以要认真分析预备知识，把新知识放在旧知识的基础上，通过复习慢慢引出新的内容，这样学生更容易掌握，更容易接受，不会产生畏难情绪，反而觉得清松自如。

4、授课的过程中应该环环相扣，一步步上，要讲问题分解，化大为小，化难为易，化繁为简，降低难度，就像是上台阶，一个个的台阶上。

5、注重建模思想。虽然不必要提出来这个名词，但是要让学生能从实际问题中抽象出数学问题，本节课的“将军饮马问题”就是一个实际的问题，要让学生转换成数学问题，抽象出数学问题。

第四篇：最短路径_数据结构课程设计报告

数据结构课程设计

《数据结构》课程设计报告

设计题目：____医院选址____________ 姓名：__________________ 学号：________________ 专业：___________

院系：____________

班级：_________________ 指导教师：_________________

年 1月 3 日

数据结构课程设计

一、问题描述

(1)题目内容：有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总和来说较短。（n>=5）(2)基本要求：

(3)可以输出每一对点间的路径长度；然后选取偏心度，最小的偏心度即为所求。

二、需求分析

(4)本程序的功能包括找出每一对点间的路径长度。(5)然后算出每一对点的偏心度。(6)其中最小的偏心度即为所求。

三、概要设计

操作集合：

(7)public:MGraph(DataType a[],int b[][MaxSize],int n,int e);//初始化邻接矩阵和路径

(8)void Floyd();//弗洛伊德算法的实现(9)void getE();//获取偏心度

(10)void showdist();//把每一对顶点之间的路径权值show出来(11)~MGraph(){} //类的析构函数

四、数据结构设计

(1)DataType vertex[MaxSize];//存放图中顶点的数组(2)int

arc[MaxSize][MaxSize];//存放图中边的数组

(3)string path[MaxSize][MaxSize];//存放从Vi到Vj的最短路径，初始为

//path[i][j]=“ViVj”

(4)int dist[MaxSize][MaxSize];//存放求得的最短路径长度(5)int vertexNum, arcNum;//图的顶点数和边数(6)int E[MaxSize][2];//获取最小偏心度和该顶点

五、算法设计

1.算法分析

1）对带权有向图的，调用Floyd算法，对每一对顶点间的最短路径长度的矩阵；

2）对最短路径长度矩阵的每列求最大值，即得到各点的偏心度； 3)具有最小偏心度的顶点即为所求。

数据结构课程设计

数据结构课程设计

2.算法实现

#include #include #include using namespace std;

const int MaxSize = 5;template class MGraph { public:，建立具有n个顶点e条边的图

};template MGraph::MGraph(DataType a[], int b[][MaxSize],int n,int e){

} template void MGraph::Floyd(){ int i,j,k;

MGraph(DataType a[], int b[][MaxSize],int n,int e);//构造函数

void Floyd();void getE();void showdist();~MGraph(){} DataType vertex[MaxSize];int arc[MaxSize][MaxSize];int dist[MaxSize][MaxSize];int vertexNum, arcNum;int E[MaxSize][2];

//存放图中顶点的数组 //存放图中边的数组 //存放求得的最短路径长度 //图的顶点数和边数 private:

string path[MaxSize][MaxSize];//存放从Vi到Vj的最短路径，初始为path[i][j]=“ViVj” vertexNum = n;arcNum = e;for(int i=0;i

} arc[i][j]=b[i][j];dist[i][j]=arc[i][j];

//直接放入邻接矩阵

for(int j=0;j

数据结构课程设计

} for(i=0;i

} for(k=0;k

for(i=0;i

}

//顶点i和j之间是否经过顶点k for(j=0;j

} dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=path[i][k]+path[k][j];for(j=0;j

} dist[i][j]=arc[i][j];if(dist[i][j]!=10000)else path[i][j]=“";path[i][j]=vertex[i]+vertex[j];

template void MGraph::showdist(){

} template void MGraph::getE(){

心度。

} for(int i=0;i

}

for(int i=0;i

} for(int j=0;j

“;for(int i=0;i

E[i][0]=i;//存放某一个节点的序号 E[i][1]=0;//存放节点的最短路径，权值。

int max = dist[0][i];//i表示列；j表示行。for(int j=0;j

if(dist[j][i]>max){ } E[i][1]=max;max = dist[j][i];

数据结构课程设计

cout<

} void main(){

代表是无穷。

}

MGraph GM(a,b,5,7);GM.Floyd();GM.showdist();cout<

0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};char a[5] = {'A','B','C','D','E'};int b[5][5] = {

//邻接矩阵,A,B,C,D,E是节点的信息，代表某一个地点。

//存储某两个有向节点间的权值，代表路径长度，10000 int min=E[0][1],k;for(int i=0;i

} cout<<”最佳选址为“<

cout<

if(E[i][1]

} min=E[i][1];k=i;

六、程序测试与实现

1、函数之间的调用关系

Main

Floyd()

showdist()

getE()

2、主程序

void main(){ char a[5] = {'A','B','C','D','E'};

//邻接矩阵,A,B...是节点的信息，代表某一个地点。

数据结构课程设计

int b[5][5] = { //存储某两个有向节点间的权值，代表路径长度，10000代表是无穷。

0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};

MGraph GM(a,b,5,7);

}

GM.Floyd();

GM.showdist();

cout<

GM.getE();

3、测试数据

int b[5][5] = { //存储某两个有向节点间的权值，代表路径长度，10000代表是无穷。

0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};

4、测试结果

七、调试分析

数据结构课程设计

1．在算偏心度的时候；每一列的最大值算错了，下次要注意。

在show的时候也把行和列搞反了；所以以为结果不对其是对的。2．算法的时空分析：(1)时间复杂度:O(n^3)；(2)空间复杂度:O(n^2)[1]

八、遇到的问题及解决办法

1）在算偏心度的时候；每一列的最大值算错了，下次要注意。

解决办法：是把行变，列不变。

2)在show的时候也把行和列搞反了；所以以为结果不对其是对的。

解决办法：把行和列反一下就好。

九、心得体会

Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX)+ Dis(XB)< Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB)= Dis(AX)+ Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。通过这个学习；把Floyd算法搞懂了；模板也熟练了许多。

第五篇：最短路径教案

最短路径问题

教学目标：

1.理解并掌握平面内一条直线同侧两个点到直线上的某一点距离之和为最小值时点的位置的确定。

2.能利用轴对称平移解决实际问题中路径最短的问题。

3.通过独立思考，合作探究，培养学生运用数学知识解决实际问题的基本能力，感受学习成功的快乐。

教学重点：

将实际问题转化成数学问题，运用轴对称平移解决生活中路径最短的问题，确定出最短路径的方法。

教学难点：

探索发现“最短路径”的方案，确定最短路径的作图及原理。

导学过程：

一、创设情景，引入新知。

前面我们研究过一些关于“两点的所有连线中，线段最短”、“连接直线外一点与直线上各点的所有线段中，垂线段最短”等的问题，我们称它们为最短路径问题．现实生活中经常涉及到选择最短路径的问题，本节将利用数学知识探究实际生活中的最短路径问题。

二、自主学习，探究新知。

问题1（将军饮马问题）

牧马人从A地出发，到一条笔直的河边L饮马，然后到B地，牧马人到河边什么地方饮马，可使所走的路径最短？

2、探索问题：

教师提出问题，引导学生思考：

（1）如何将这个实际问题转化为数学问题？转化的要点是什么？

（2）回忆以前学过的“最短”的知识点，（两点之间，线段最短；垂线段最短），思考：这个问题中的“最短”和以前学过的知识有什么相同点和不同点？（3）、如何把“不同点”化为“相同点”？（4）、如何用图形将问题展现出来？

【学生活动】：学生独立思考，画图分析，并尝试回答，相互补充，师生共同归纳：（1）、将A、B两地抽象为两个点，将河L抽象为一条直线（如图2），则问题转化为：如何在L上找一点C，使AC与BC的和最小（如图3）。转化时要注意条件和结论的转化，以及点、线的抽象。

（2）、相同点：都是两点间的最短距离问题。

不同点：一个是两点在L的同侧；一个是两点在L的异侧，并画图比较（如图4）。（3）利用轴对称的知识找出B点关于直线L的对称点B′,就可以满足C B′= CB,再连接A B′，则A B′与直线L的交点C极为所求。

【教师板书并画图】（如图5）

第一步：作出B点关于直线L的对称点B′

第二步：连接A B′，与直线L的交点为C,则C点即为所求。

证明：略

问题二（造桥选址问题）如图,A和B两地在一条河的两岸,现要在河上造一座桥MN.桥造在何处可使从A到B的路径AMNB最短?（假定河的两岸是平行的直线,桥要与河垂直.)

将实际问题中A，B两地与笔直的河L抽象成 点A.点B和直线a，b.如图：

分析：AM+NB最短，要先确定点N在直线b的位置，如果我先将A点往直线a的垂直方向平移MN个单位 后到A′，由于MN垂直直线a，N点就是M点往直线 b的垂直方向平移MN个单位后到的点，由图形平移后 的对应点之间的线段是平行且相等的，得到AM=A′N.AM+NB最短即A′N+NB最短.转变成了直线b上是找 到一点N，使A′ N+NB最短,连结A′,B,与直线b相交的 一点为N点.证明略.三、巩固练习：

1.∠WXZ内有一点Z，在WZ，ZY上分别有点A，B,当△ABZ的周长最小时，请在图中作出点A，B的位置.2.如图，A、B两地之间有两条河，现要在两条河上各造一座桥MN和PQ.桥分别建在何处才能使从A到B的路径最短？（假定河的两岸是平行的直线，桥要与河岸垂直）

四、课堂小结

1、本节主要知识点：

轴对称的对称知识和两点间的最短距离在“最短路径”这类问题中的运用。实际问题与数学问题的转化。

2、提出问题： 这节课你们学到了什么？还有哪些疑惑？

五、布置作业

新观察