-
2020-10-05 14:27:39两点之间最短距离
这是我的一个测试,也是我学习html的/起点,他们说一个合格的程序员必须学会html,我比他们起步晚了一些,可是我认为还来的及,以后我就用html来记录我的学习记录了。
问题的提出:
在二维平面的n个点上,找出其中的一对点,使得在n个点组成的所有的点中,该点对的距离最小。
一维:最接近点对问题
方法一:(暴力法)
直接使用双层遍历来计算每一对点的距离,另外新建一个变量记录两点之间距离最小的值,但是如此一来时间复杂度就变为O(n2),方法二:(分治法)
分治法的思路:
- 划分成子规模点集S1和S2;
- 找到S1和S2的最小距离d;
- 合并S1和S2:利用d在S1的(m-d,m]和S2(m,m+d]中找到最大点和最小点,即p3和q3.选出最小距离,完成合并。
m如何选择
m=(max(s)+min(s))/2;
代码:
talking is cheap,show me the code;
二维最接近点的问题:/*根据算法随便写的,返回的是两个点之间最小的距离,不是两个点的坐标,如果有问题,欢迎指正*/ /*这里的坐标默认为正序的*/ #include<iostream> #include<vector> using namespace std; int search(vector<int> target) { int n=target.size(); if(n<2) //如果分到一个元素就返回最大数值 return INT_MAX; int mid=n/2; //中线 vector<int> temp_left; vector<int> temp_right; temp_left.insert(temp_left.begin(),target.begin(),target.begin()+mid); //中线分割 temp_right.insert(temp_right.begin(),target.begin()+mid,target.end()); int p=search(temp_left); int q=search(temp_right); int d=temp_right.front()-temp_left.back(); cout<<temp_right.front()<<" "<<temp_left.back()<<endl; return d>min(p,q)?min(p,q):d;}//返回两边和贯穿中间的最小的两点距离 int main(){ int a[6]={-9,-6,0,4,7,9}; vector<int> target(a,a+6); cout<<search(target); return 0; }
思路与一维的最接近点对相似。
- 选取中垂线l:x=m来作为分割直线。
- 递归的在S1和S2找出其最小距离d1和d2,并设d=min{d1,d2},S中最接近点对或是d,或者是某个{p,q}
- 合并起来
// 随便写思路的如果有误,请指正(注意返回的是两点之间的距离,不是坐标) #include <iostream> #include <math.h> #include<algorithm> using namespace std; struct point { int x, y; }; double distance(struct point p1, struct point p2) { return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y,2)); } double search(struct point p[],int pl,int pr) { if (pl == pr) return INT_MAX; int mid = (pl + pr) / 2; double d_left = search(p, pl, mid); double d_right = search(p, mid + 1, pr); double temp_d = min(d_left, d_right); while (abs(p[pl].y - p[mid].y) > temp_d&&pl < pr)//如果仅仅是单边距离就已经大于上一次比较返回的d就没必要在接下来的敌方继续比较了。 pl++; while (abs(p[pr].y - p[mid].y) > temp_d&&pl < pr) pr--; for (int i = pl; i < pr; i++) { for (int j = i + 1; j < pr; j++) { if (temp_d < abs(p[i].x - p[j].x))//同理与上面的注释 break; else temp_d = min(temp_d, distance(p[i], p[j]));//找到最小的距离 } } return temp_d; } int main() { struct point p[100]; int n; cin >> n; for (int i = 0; i < n; i++) { cin >> p[i].x; cin >> p[i].y; } cout<<search(p, 0, n - 1); }
更多相关内容 -
Java版本实现9宫格或者多宫格的两点距离最短的算法
2019-01-07 00:19:58Java版本实现9宫格或者多宫格的两点距离最短的算法。各种大厂的面试题中的最基本算法知识,实现两点之间的最短距离实现方法。 -
python广度优先搜索得到两点间最短路径
2020-12-24 17:52:46要实现的是输入一张 图,起点,终点,输出起点和终点之间的最短路径。 广度优先搜索 适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度:... -
C语言寻找无向图两点间的最短路径
2020-12-25 21:33:04本次程序利用邻接表实现无向图,并且通过广度优先遍历找到两点之间的最短路径。 2.广度优先遍历 广度优先遍历(BFS)和深度优先遍历(DFS)是图结构中最常用的遍历方式。其中广度优先遍历配合上队列能够找到两点之间的... -
两点之间最短距离:贪心算法 (DIJKSTRA算法)
2021-12-15 21:45:46顶点表示城市,边表示各个城市之间的交通关系,所带权值为两个城市间的耗费。 这个交通咨询系统可以回答旅客提出的各种问题,例如:如何选择一条路径使得 从A城到B城途中中转次数最少;如何选择一条路径使得从A城到B...在交通网络日益发达的今天,针对人们关心的各种问题,利用计算机建立一
个A城市的交通咨询系统。在系统中采用图来构造各个城市之间的联系,图中
顶点表示城市,边表示各个城市之间的交通关系,所带权值为两个城市间的耗费。
这个交通咨询系统可以回答旅客提出的各种问题,例如:如何选择一条路径使得
从A城到B城途中中转次数最少;如何选择一条路径使得从A城到B城里程最
短;如何选择一条路径使得从A城到B城花费最低等等的一系列问题。
#include<stdio.h> #define max1 1000 int a[10][10]; int dist[10]; int path[10]; int set[10]; int min; int v; void fun(int n) { if(n==0) { printf("A"); } else{ fun(path[n]); printf("->%c",n+'A'); } } int main() { for(int i=0;i<=5;i++) { for(int j=0;j<=5;j++) { a[i][j]=max1; } } a[0][1]=10; a[0][3]=30; a[0][4]=100; a[1][2]=50; a[2][4]=10; a[3][2]=20; a[3][4]=60; dist[0]=0; path[0]=-1; set[0]=1; for(int i=1;i<=4;i++) { if(a[0][i]>0) { path[i]=0; dist[i]=a[0][i]; } else { path[i]=-1; dist[i]=max1; } } for(int k=1;k<=4;k++) { printf("%d ",dist[k]); } printf("\n"); for(int k=1;k<=4;k++) { printf("%d ",path[k]); } printf("\n"); for(int k=1;k<=4;k++) { printf("%d ",set[k]); } printf("\n"); for(int i=1;i<=4;++i) { min=max1; for(int j=1;j<=4;++j) { if(set[j]==0&&dist[j]<min) { v=j; min=dist[j]; } } set[v]=1; printf("当前所用的中间的值:%d\n",v); for(int j=1;j<=4;++j) { if(set[j]==0&&dist[v]+a[v][j]<dist[j]) { printf("前一个:%d 数组:%d 相加:%d 现在:%d\n",dist[v],a[v][j],dist[v]+a[v][j],dist[j]); dist[j]=dist[v]+a[v][j]; path[j]=v; } } printf("当前所改变的值:"); for(int k=1;k<=4;k++) { printf("%d ",dist[k]); } printf("\n"); for(int k=1;k<=4;k++) { printf("%d ",path[k]); } printf("\n"); for(int k=1;k<=4;k++) { printf("%d ",set[k]); } printf("\n"); } for(int i=1;i<=4;i++) { printf("%c:",i+'A'); fun(i); printf("\n"); } }
-
任意两点间的最短距离 动态规划算法
2010-05-13 21:10:59任意两点间的最短距离,使用动态规划算法实现 -
JTS两个空间几何图形间最短距离,及最短距离间的两个坐标
2019-10-12 14:38:53记录下 java jts 求两个空间几何图形间最短距离,及最短距离间的两个坐标. 如:求一个点到一条直线的垂直坐标 -
如何求地球上两点之间的最短距离_初中数学求线段之和最小的问题,知识点题型汇总...
2020-11-14 15:13:16我们经常在考试当中看到求线段之和最小的问题,首先来看下这几个数学模型:模型1:两点之间线段最短要在l找点P,使得PA+PB最短,这模型最简单,两点之间线段最短。模型2:将军饮马问题在l上找一点P,使得PA+PB最短,...我们经常在考试当中看到求线段之和最小的问题,首先来看下这几个数学模型:
模型1:两点之间线段最短
要在l找点P,使得PA+PB最短,这模型最简单,两点之间线段最短。
模型2:将军饮马问题
在l上找一点P,使得PA+PB最短,作对称。其中BA’就是最短的值
模型3:两动点找三角形周长最小
在OA,OB上找点M、N,使得△PMN周长最小,把P关于OA,OB分别作对称,然后连接两个对称点,交点记为所求,然后周长最小值为P’P’’
模型4:两动点加垂线段最短
在OA上找一点M,使得M到OB的距离与M到P的距离之和最短。作P关于OA的对称点,然后在对称点P’上作OB的垂线,交点即为所求,P’N就是最短值。
模型5:四边形周长
如图,点P,Q为∠MON内的两点,分别在OM,ON上作点A,B。使四边形PAQB的
周长最小。
总结一句话,要在哪找点,我们就关于谁作对称!是不是很好理解?
一
题型1:直线类
例题1.如图,A、B两个小集镇在河流CD的同侧,分别到河的距离为AC=10千米,BD=30千米,且CD=30千米,现在要在河边建一自来水厂,向A、B两镇供水,铺设水管的费用为每千米3万,请你在河流CD上选择水厂的位置M,使铺设水管的费用最节省,并求出总费用是多少?
作点B关于直线CD的对称点B',连接AB',交CD于点M
则AM+BM = AM+B'M = AB',水厂建在M点时,费用最小
如右图,在直角△AB'E中,
AE = AC+CE = 10+30 = 40
EB' = 30
所以:AB' = 50
总费用为:50×3 = 150万
一
题型2:角类
如图∠AOB = 45°,P是∠AOB内一点,PO = 10,Q、P分别是OA、OB上的动点,求△PQR周长的最小值.
一
题型3:三角形类
如图,等腰Rt△ABC的直角边长为2,E是斜边AB的中点,P是AC边上的一动点,则PB+PE的最小值为 。
如图,在△ABC中,AC=BC=2,∠ACB=90°,D是BC边的中点,E是AB边上一动点,则EC+ED的最小值为_______。
在直角△DBC'中
DB=1,BC=2,根据勾股定理可得,DC'=√5
如图,在等边△ABC中,AB = 6,AD⊥BC,E是AC上的一点,M是AD上的一点,且AE = 2,求EM+EC的最小值。
一
题型4:矩形类
如图,若四边形ABCD是矩形, AB = 10cm,BC = 20cm,E为边BC上的一个动点,P为BD上的一个动点,求PC+PD的最小值。
作点C关于BD的对称点C',过点C',作C'B⊥BC,交BD于点P,则C'E就是PE+PC的最小值。
直角△BCD中,CH =20/5
直角△BCH中,BH = 8
△BCC'的面积为:BH×CH = 160
所以 C'E×BC = 2×160 则CE' = 16
一
题型5:菱形类
如图,若四边形ABCD是菱形, AB=10cm,∠ABC=45°,E为边BC上的一个动点,P为BD上的一个动点,求PC+PE的最小值。
一
题型6:直角梯形类
已知直角梯形ABCD中,AD∥BC,AB⊥BC,AD=2,BC=DC=5,点P在BC上移动,则当PA+PD取最小值时,△APD中边AP上的高为( )
一
题型7:圆类
已知⊙O的直径CD为4,∠AOD的度数为60°,点B是︵AD的中点,在直径CD上找一点P,使BP+AP的值最小,并求BP+AP的最小值.
如图,MN是半径为1的⊙O的直径,点A在⊙O上,∠AMN=30°,B为AN弧的中点,P是直径MN上一动点,则PA+PB的最小值为( )
A.2√2 B.√2
C.1 D.2
一
题型8:一次函数类
在平面直角坐标系中,有A(3,-2),B(4,2)两点,现另取一点C(1,n),当n =______时,AC + BC的值最小.
点C(1,n),说明点C在直线x=1上,所以作点A关于直线x=1的对称点A',连接A'B,交直线x=1于点C,则AC+BC的值最小
设直线A'B的解析式为y=kx+b,则
-2=-k+b
2=4k+b
解得:k = (4/5) b = - (6/5)
所以:y = (4/5)x-(6/5)
当x = 1时,y = -(2/5)
故当n = -(2/5)时,AC+BC的值最小
一
题型9:二次函数类
如图,在直角坐标系中,点A的坐标为(-2,0),连结OA,将线段OA绕原点O顺时针旋转120。,得到线段OB.
(1)求点B的坐标;
(2)求经过A、O、B三点的抛物线的解析式;
(3)在(2)中抛物线的对称轴上是否存在点C,使△BOC的周长最小?若存在,求出点C的坐标;若不存在,请说明理由.(注意:本题中的结果均保留根号)
一
题型10:建桥选址类
如图,村庄A、B位于一条小河的两侧,若河岸a、b彼此平行,现在要建设一座与河岸垂直的桥CD,问桥址应如何选择,才能使A村到B村的路程最近?
一
题型11:立体图形
一只蚂蚁欲从圆柱形桶外的A点爬到桶内的B点处寻找食物,已知点A到桶口的距离AC为12cm,点B到桶口的距离BD为8cm,CD的长为15cm,那么蚂蚁爬行的最短路程是多少?
垂线段最短型
如图,在锐角△ABC中,AB=4√2,∠BAC=45°,∠BAC的平分线交BC于点D,M、N分别是AD和AB上的动点,则BM+MN的最小值是____.
-
(来点有用的)含障碍的两点最短路径算法完整代码
2019-07-29 14:18:06含有各种障碍物的,水平面两点间最短的距离算法。就相当于计算你从一个地方走到另一个地方,最短的路径。 注意:不是图论!不是节点!不是Dijkstra!不是Floyd! -
求两点间的最短距离
2022-03-10 20:47:11公式: 解法一: import math # 第一个点(x1,y1) x1 = int(input("请输入第一个点的横坐标:")) y1 = int(input("请输入第一个点的纵坐标:")) print("第一个点的坐标是:",(x1,y1))...# 最短距离 s = math.sqrt((x1公式:
解法一: import math # 第一个点(x1,y1) x1 = int(input("请输入第一个点的横坐标:")) y1 = int(input("请输入第一个点的纵坐标:")) print("第一个点的坐标是:",(x1,y1)) # 第一个点(x2,y2) x2 = int(input("请输入第二个点的横坐标:")) y2 = int(input("请输入第二个点的纵坐标:")) print("第二个点的坐标是:",(x2,y2)) # 最短距离 s = math.sqrt((x1-x2)**2+(y1-y2)**2) print("两点间的最短距离是:",s) 解法二: import math # 第一个点(x1,y1) x1 = int(input("请输入第一个点的横坐标:")) y1 = int(input("请输入第一个点的纵坐标:")) print("第一个点的坐标是:",(x1,y1)) # 第一个点(x2,y2) x2 = int(input("请输入第二个点的横坐标:")) y2 = int(input("请输入第二个点的纵坐标:")) print("第二个点的坐标是:",(x2,y2)) # 最短距离 s = math.sqrt(pow((x1-x2),2)+pow((y1-y2),2)) print("两点间的最短距离是:",s) s1 = int(s) # 转换成整型 print("两点间的最短距离是:",s1)
感谢大家,点赞,收藏,关注,评论!
-
Python求两点间最短距离
2021-08-06 17:08:13如图为一个10*10的网格图,黑点处为障碍物,给定任意两点——start和end,求最短路径,走一格距离为1。 Code # 算法思想:通过BFS找end,找到就停 # 部分变量含义: # value->网格图列表 # hinders->障碍点... -
图论之两点间最短距离
2016-10-25 10:52:13null -
寻找两点之间的最短距离Python
2021-01-14 20:14:29我有两个数据框。一个包含properties locations,另一个包含railway stations locations。属性数据框样本(原始数据框由约700行组成):properties=pd.DataFrame({'propertyID':['13425','32535','43255','52521'],'... -
指定两点间最短路径
2013-07-26 16:09:59从文件读取图,然后寻找指定两点间最短路径,并把寻找结果存入文件中,路径包括一条主路径和备用路径 -
求两个点之间最短路径
2017-06-01 01:06:42给定一个乡镇网络图,求取两个乡镇的最短路径,并输出路径,以及路径距离的大小。 -
ellipse_matlab_椭球面上两点最短距离_
2021-10-04 11:32:06椭球面上的两点球面距离的解析计算是难以实现的,现提供一种切割方法,可采取贪心策略取得最短路径! -
C# 实现求图的任意两点的最短路径及距离
2019-03-02 15:42:23实验三:C#实现求图的任意两点的最短路径及距离 实验目的 定义Graph类、Node类,从文件中读取图结构;给定两个顶点,给出两个顶点的最短路径(如果没有连通,请给出)。把图进行可视化展示(一个适当大小的图),... -
最短路径(图中两点间最短路径)
2020-12-24 11:13:34importjava.util.Scanner;//最短路径求解public classDistMin {static classGraphMatrix{static final int MaxNum=20;char[] Vertex=new char[MaxNum]; //保存顶点信息(序号或字母)int GType; //图的类型(0:... -
避障最短路径(版本 1.3):计算平面中两点之间的最短路径,避开障碍物。-matlab开发
2021-06-01 18:02:42SHPATH - 避障的最短路径(版本 1.3) 给定一个由 0(对于开放空间)和 1(对于障碍物)组成的“地形”矩阵,该函数计算两个指定点之间的最短路径,同时避开障碍物。 采用两阶段解决方案。 在第一阶段,算法通过... -
java 最短路径算法 如何实现有向 任意两点的最短路径
2021-03-03 10:34:18展开全部Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节e68a8462616964757a686964616f31333361316131点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。... -
求解两点间最短路径的算法
2020-07-19 23:42:40最短路径算法1.Dijkstra算法2.Bellman-Ford算法3.SPFA算法4.Floyd算法几种最短路径算法的对比Dijkstra算法、Bellman-Ford算法和SPFA算法的对比Dijkstra算法和Floyd算法的...多源最短路算法:求任意两点之间的最短路径. -
求图中任意两点的最短路径和全部路径应用
2016-06-28 22:55:10图的应用,实现了求任意两城市间的最短距离以及全部路径,基于MFC实现。 -
两条线段之间的最短距离:函数计算两条线段之间的最短距离。-matlab开发
2021-06-01 09:57:53计算给定起点和终点的两条线段之间的最短距离。 改编在 Dan Sunday 网站上找到的算法 ( http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment )。 用法:输入两条线段的... -
在已知曲面拟合图上如何求解两点间最短距离
2021-04-24 21:48:54我想求得曲面上已知两点间的最小距离。首先根据一系列散点数据,用以下程序拟合出了地形图。A=[55590,86720,1576.3;55730,86770,1588.9;55880,86620,1550.1;56140,86620,1596.8;56220,86370,1592.3;56260,86040,1573... -
(Java)实现查找点与点之间的最短距离
2020-03-14 10:26:52可能存在多个点对都符合最短距离要求,因此需要全部输出; 比如(1,1) (2,2) (3,3) 这里就有两对点都符合(1,1) (2,2) 和 (2,2) (3,3) 二、代码 注意: (1)实现输入格式(x,y)格式输入 (2)使用 Point 类型记录每... -
简单蚁群算法:介绍了蚁群算法在寻找简单网络两点间最短路径的应用。-matlab开发
2021-05-29 06:55:48它是具有权重的节点网络的最短路径的解决方案,为此使用了蚂蚁精英系统。 -
求两点之间最短的距离矩阵.rar
2019-09-12 22:56:25里面有详细的相关编程实现,Floyd算法