精华内容
下载资源
问答
  • C++ 两点之间最短距离
    千次阅读
    2020-10-05 14:27:39
    两点之间最短距离

    这是我的一个测试,也是我学习html的/起点,他们说一个合格的程序员必须学会html,我比他们起步晚了一些,可是我认为还来的及,以后我就用html来记录我的学习记录了。

    问题的提出:
    在二维平面的n个点上,找出其中的一对点,使得在n个点组成的所有的点中,该点对的距离最小。


    一维:最接近点对问题

    方法一:(暴力法)
      直接使用双层遍历来计算每一对点的距离,另外新建一个变量记录两点之间距离最小的值,但是如此一来时间复杂度就变为O(n2),

    方法二:(分治法)
    分治法的思路:

    1. 划分成子规模点集S1和S2;
    2. 找到S1和S2的最小距离d;
    3. 合并S1和S2:利用d在S1的(m-d,m]和S2(m,m+d]中找到最大点和最小点,即p3和q3.选出最小距离,完成合并。

    ![示意图](https://img-blog.csdnimg.cn/20201004201704741.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTExOTY0,size_16,color_FFFFFF,t_70#pic_center)

    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;
    }
    
    二维最接近点的问题:

    思路与一维的最接近点对相似。

    1. 选取中垂线l:x=m来作为分割直线。
    2. 递归的在S1和S2找出其最小距离d1和d2,并设d=min{d1,d2},S中最接近点对或是d,或者是某个{p,q}
    3. 合并起来

    // 随便写思路的如果有误,请指正(注意返回的是两点之间的距离,不是坐标)
    #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宫格或者多宫格的两点距离最短的算法。各种大厂的面试题中的最基本算法知识,实现两点之间的最短距离实现方法。
  • 要实现的是输入一张 图,起点,终点,输出起点和终点之间的最短路径。 广度优先搜索 适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度:...
  • 本次程序利用邻接表实现无向图,并且通过广度优先遍历找到两点之间的最短路径。 2.广度优先遍历 广度优先遍历(BFS)和深度优先遍历(DFS)是图结构中最常用的遍历方式。其中广度优先遍历配合上队列能够找到两点之间的...
  • 顶点表示城市,边表示各个城市之间的交通关系,所带权值为个城市间的耗费。 这个交通咨询系统可以回答旅客提出的各种问题,例如:如何选择一条路径使得 从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");
    	}
    	
    }
    
    展开全文
  • 任意两点间的最短距离,使用动态规划算法实现
  • 记录下 java jts 求个空间几何图形间最短距离,及最短距离间的个坐标. 如:求一个到一条直线的垂直坐标
  • 我们经常在考试当中看到求线段之和最小的问题,首先来看下这几个数学模型:模型1:两点之间线段最短要在l找点P,使得PA+PB最短,这模型最简单,两点之间线段最短。模型2:将军饮马问题在l上找一点P,使得PA+PB最短,...

    我们经常在考试当中看到求线段之和最小的问题,首先来看下这几个数学模型:

    模型1:两点之间线段最短

    7e7e07d00ed8fc8284e2788e9ba7145d.png

    要在l找点P,使得PA+PB最短,这模型最简单,两点之间线段最短。

    模型2:将军饮马问题

    7e7e07d00ed8fc8284e2788e9ba7145d.png

    在l上找一点P,使得PA+PB最短,作对称。其中BA’就是最短的值

    模型3:两动点找三角形周长最小

    3bea0391c190e8002c36041c0b81b75c.png

    在OA,OB上找点M、N,使得△PMN周长最小,把P关于OA,OB分别作对称,然后连接两个对称点,交点记为所求,然后周长最小值为P’P’’

    模型4:两动点加垂线段最短

    2f1c7c77a4216b54e541146c8de8dd07.png

    在OA上找一点M,使得M到OB的距离与M到P的距离之和最短。作P关于OA的对称点,然后在对称点P’上作OB的垂线,交点即为所求,P’N就是最短值。

    模型5:四边形周长

    如图,点P,Q为∠MON内的两点,分别在OM,ON上作点A,B。使四边形PAQB的

    周长最小。

    eaf03e034469cd2c5961f20f063758a2.png

    总结一句话,要在哪找点,我们就关于谁作对称!是不是很好理解?

    题型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万

    235681da3e81803957d1f1afd5066379.png
    3a870b94c11d8286fe0b9a670d39694f.png

    题型2:角类

    如图∠AOB = 45°,P是∠AOB内一点,PO = 10,Q、P分别是OA、OB上的动点,求△PQR周长的最小值.

    5ef88c0689a5aff6e163bc851adcccae.png

    题型3:三角形类

    如图,等腰Rt△ABC的直角边长为2,E是斜边AB的中点,P是AC边上的一动点,则PB+PE的最小值为

    b2b2b1988a2018ace7c51dd96033698f.png

    如图,在△ABC中,AC=BC=2,∠ACB=90°,D是BC边的中点,E是AB边上一动点,则EC+ED的最小值为_______。

    45b2e24a2aef15a8aebfe4cc6023e465.png

    在直角△DBC'中

    DB=1,BC=2,根据勾股定理可得,DC'=√5

    如图,在等边△ABC中,AB = 6,AD⊥BC,E是AC上的一点,M是AD上的一点,且AE = 2,求EM+EC的最小值。

    c548172577c8ce54f1563789b72eb44d.png

    题型4:矩形类

    如图,若四边形ABCD是矩形, AB = 10cm,BC = 20cm,E为边BC上的一个动点,P为BD上的一个动点,求PC+PD的最小值。

    9b9af6e7361c4a67937735be6654331a.png

    作点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的最小值。

    7b1da552b97c92d2b8a80d9897a20237.png

    题型6:直角梯形类

    已知直角梯形ABCD中,AD∥BC,AB⊥BC,AD=2,BC=DC=5,点P在BC上移动,则当PA+PD取最小值时,△APD中边AP上的高为( )

    d07287728a5893f9d3c5a777a16b962e.png
    57b995503537fb62de65efd1b89ab9ad.png

    题型7:圆类

    已知⊙O的直径CD为4,∠AOD的度数为60°,点B是︵AD的中点,在直径CD上找一点P,使BP+AP的值最小,并求BP+AP的最小值.

    8efcd9ccff0c9a26b233e62bb26096ea.png

    如图,MN是半径为1的⊙O的直径,点A在⊙O上,∠AMN=30°,B为AN弧的中点,P是直径MN上一动点,则PA+PB的最小值为( )

    A.2√2 B.√2

    C.1 D.2

    4c7984c29ea3ecae70326d356647026a.png

    题型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的值最小

    f327c0e5051a12c8a287932a58251d49.png

    题型9:二次函数类

    如图,在直角坐标系中,点A的坐标为(-2,0),连结OA,将线段OA绕原点O顺时针旋转120。,得到线段OB.

    (1)求点B的坐标;

    (2)求经过A、O、B三点的抛物线的解析式;

    (3)在(2)中抛物线的对称轴上是否存在点C,使△BOC的周长最小?若存在,求出点C的坐标;若不存在,请说明理由.(注意:本题中的结果均保留根号)

    1f5063c93dce0b2c84cb894b30a76c99.png

    题型10:建桥选址类

    如图,村庄A、B位于一条小河的两侧,若河岸a、b彼此平行,现在要建设一座与河岸垂直的桥CD,问桥址应如何选择,才能使A村到B村的路程最近?

    dcfa7e209166a64e1aba31c719cea11b.png

    题型11:立体图形

    一只蚂蚁欲从圆柱形桶外的A点爬到桶内的B点处寻找食物,已知点A到桶口的距离AC为12cm,点B到桶口的距离BD为8cm,CD的长为15cm,那么蚂蚁爬行的最短路程是多少?

    ba5518ce0576a2ddf27b687c8727326a.png

    垂线段最短型

    如图,在锐角△ABC中,AB=4√2,∠BAC=45°,∠BAC的平分线交BC于点D,M、N分别是AD和AB上的动点,则BM+MN的最小值是____.

    584299d1615e5db41f9705a5f98732f0.png
    展开全文
  • 含有各种障碍物的,水平面两点最短距离算法。就相当于计算你从一个地方走到另一个地方,最短的路径。 注意:不是图论!不是节点!不是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)
    

    感谢大家,点赞,收藏,关注,评论!

    展开全文
  • 如图为一个10*10的网格图,黑点处为障碍物,给定任意两点——start和end,求最短路径,走一格距离为1。 Code # 算法思想:通过BFS找end,找到就停 # 部分变量含义: # value->网格图列表 # hinders->障碍点...
  • null
  • 我有个数据框。一个包含properties locations,另一个包含railway stations locations。属性数据框样本(原始数据框由约700行组成):properties=pd.DataFrame({'propertyID':['13425','32535','43255','52521'],'...
  • 指定两点最短路径

    2013-07-26 16:09:59
    从文件读取图,然后寻找指定两点最短路径,并把寻找结果存入文件中,路径包括一条主路径和备用路径
  • 给定一个乡镇网络图,求取个乡镇的最短路径,并输出路径,以及路径距离的大小。
  • 椭球面上的两点球面距离的解析计算是难以实现的,现提供一种切割方法,可采取贪心策略取得最短路径!
  • 实验三:C#实现求图的任意两点最短路径及距离 实验目的 定义Graph类、Node类,从文件中读取图结构;给定两个顶点,给出两个顶点的最短路径(如果没有连通,请给出)。把图进行可视化展示(一个适当大小的图),...
  • 最短路径(图中两点最短路径)

    千次阅读 2020-12-24 11:13:34
    importjava.util.Scanner;//最短路径求解public classDistMin {static classGraphMatrix{static final int MaxNum=20;char[] Vertex=new char[MaxNum]; //保存顶点信息(序号或字母)int GType; //图的类型(0:...
  • SHPATH - 避障的最短路径(版本 1.3) 给定一个由 0(对于开放空间)和 1(对于障碍物)组成的“地形”矩阵,该函数计算个指定点之间的最短路径,同时避开障碍物。 采用阶段解决方案。 在第一阶段,算法通过...
  • 展开全部Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节e68a8462616964757a686964616f31333361316131最短路径。主要特点是以起始为中心向外层层扩展,直到扩展到终点为止。...
  • 求解两点最短路径的算法

    千次阅读 2020-07-19 23:42:40
    最短路径算法1.Dijkstra算法2.Bellman-Ford算法3.SPFA算法4.Floyd算法几种最短路径算法的对比Dijkstra算法、Bellman-Ford算法和SPFA算法的对比Dijkstra算法和Floyd算法的...多源最短路算法:求任意两点之间的最短路径.
  • 图的应用,实现了求任意城市间的最短距离以及全部路径,基于MFC实现。
  • 计算给定起点和终点的条线段之间的最短距离。 改编在 Dan Sunday 网站上找到的算法 ( http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment )。 用法:输入条线段的...
  • 我想求得曲面上已知两点间的最小距离。首先根据一系列散点数据,用以下程序拟合出了地形图。A=[55590,86720,1576.3;55730,86770,1588.9;55880,86620,1550.1;56140,86620,1596.8;56220,86370,1592.3;56260,86040,1573...
  • 可能存在多个对都符合最短距离要求,因此需要全部输出; 比如(1,1) (2,2) (3,3) 这里就有都符合(1,1) (2,2) 和 (2,2) (3,3) 二、代码 注意: (1)实现输入格式(x,y)格式输入 (2)使用 Point 类型记录每...
  • 它是具有权重的节点网络的最短路径的解决方案,为此使用了蚂蚁精英系统。
  • 里面有详细的相关编程实现,Floyd算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,502
精华内容 31,400
关键字:

两点距离最短