算法实例:平面寻路

2024-06-15 17:18
文章标签 算法 实例 平面 寻路

本文主要是介绍算法实例:平面寻路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2018/11/26

01 引言

问题描述:电路焊接过程中,自动化机械手需要将电路板上元器件的引脚连接到已打好的孔中,为了保证焊接过程机械手走的路径最短,即耗费时间最短,设计一个算法。
问题来源:《算法设计手册》p17.


电路板焊接实例

这是一个书籍讲解的范例,把电路版焊接作为一个引子。记录一下面对这种问题的时候,我的解决方案。


02 解决方案

数据建模

问题描述部分是按照现实生活中的描述,本质上是一个寻路问题,并不适用于解决问题的过程。

  • 为了转化为数学问题,需要一个模型。首先建立坐标系,就普通的坐标系就可以。
  • 为了突出问题,我们忽略机械手的初始位置,对上图中的点进行编号,并假设机械手从0号点出发。(这里这个假设本质上有些不够准确,忽略了很多信息,比如说那种一条直线的点,如果我随便找一个点作为起点,肯定就不是最短的了。但为了初步的分析,就先这样假设。)

(实际上的点有很多分布的形式,图中算是一个比较简单的实例,后续再来分析其他的各种情况)

将以上的信息整合,把问题转化如下:

P:存在一个集合S,集合中的元素为坐标系中的点(x,y),对集合中的元素进行排序,使得到的新的有序集合的元素,按顺序距离总和最小。


算法分析过程

随机从一个点出发,可以找到的路径很多,肯定不能用穷举那样的笨方法。要想思考出来好的算法, 就先看看我手里的信息嘛,逐步整合。

  • 坐标系
  • 各个点的位置

从明面上看,这已经是所有的信息了;其实还有一个隐藏的信息,就是各个点之间的直线距离。

首先就从这个距离上下功夫,脑海里想到的第一个算法。


第一个尝试:贪心算法,每次选择距离最短的点
  1. 随机选择一个点作为出发点,并作为当前操作的点
  2. 求出剩余集合中与当前操作的点距离最短的那个点,如果有多个点距离相等,随机取一个;
  3. 将取出的新的点,作为新的当前操作的点,并重复步骤2,直至剩余点为0。

采用贪心算法的结果,每次都是局部最优的,这样选择出来的结果,可能是最优的,也可能不是;相比穷举搜索的算法,已经提高了很多的效率,但仍有提升的空间。
注意看,每次步骤3的时候,从集合中取出一个新的点,都要去计算这个剩余集合中所有点和当前操作点的距离。(这个地方应该把时间复杂度给列上来)这是一个很耗时的操作,就像之前看过的字符串匹配的问题,如果以往的操作可以给你一些后面利用的信息,这种可以给你提供很大的价值。


第二个尝试:改进的贪心算法,利用最边上的点作为起始点

虽然前面提到了利用某数据结构来加速选点的过程,但是一下子来让我去想一个数据结构我可能也想不起来,我记得比较接近的就是kd-tree把,这个是当时做聚类的时候学到的一个。我先从简单的问题出发。
每次都选出一个最短的路径,如果分解了之后,就是新的点X轴和Y轴距离当前操作的点都最近。如果是按照排序的方式,因为这些点都是随机分布的,没有什么特殊的,你没有标准先找到第一个点。但是刚才也说过了,如果这些点分布在一条直线上(例如,与X轴平行),那么这个时候选取的初始点就存在意义了。所以要设计一个数据结构,对这些要求不敏感的,我直接就从最靠边上的点作为起始点就好了。

  1. 对各个点按照X轴上的大小进行排序,
  2. 将X轴上的最靠边(影响后续选择)的点做为起始点,并作为当前操作的点;
  3. 按照已经排好序的点,从集合中取出最近的点;
  4. 将取出的新的点作为新的当前操作的点,重复步骤3,直至集合为空集。

虽然上面的想法很好,但是这个算法失败了。

可以看看这样出来的效果:


第二个算法效果

上面这个算法可以借鉴的地方就是那个将最边上的点最为起始点。(这句话也不完全对,还是有一些不适用的地方。


03 结论

这是一个旅行商的问题,我这里思考的过程基本上没有问题,但没有抓到一些本质,所以结果并不是很理想。另外,我感觉,我对问题的抽象还是不够。

看来我得想第三个了,其实我前面的想法挺不错的,就是利用已经计算过的信息;或者说我是不是还有别的信息量没有挖掘出来。

这里仅仅是自己的一个思考,还是踏踏实实的看书上的说法把。

这篇关于算法实例:平面寻路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1064082

相关文章

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部

Spring组件实例化扩展点之InstantiationAwareBeanPostProcessor使用场景解析

《Spring组件实例化扩展点之InstantiationAwareBeanPostProcessor使用场景解析》InstantiationAwareBeanPostProcessor是Spring... 目录一、什么是InstantiationAwareBeanPostProcessor?二、核心方法解

java String.join()方法实例详解

《javaString.join()方法实例详解》String.join()是Java提供的一个实用方法,用于将多个字符串按照指定的分隔符连接成一个字符串,这一方法是Java8中引入的,极大地简化了... 目录bVARxMJava String.join() 方法详解1. 方法定义2. 基本用法2.1 拼接

Linux lvm实例之如何创建一个专用于MySQL数据存储的LVM卷组

《Linuxlvm实例之如何创建一个专用于MySQL数据存储的LVM卷组》:本文主要介绍使用Linux创建一个专用于MySQL数据存储的LVM卷组的实例,具有很好的参考价值,希望对大家有所帮助,... 目录在Centos 7上创建卷China编程组并配置mysql数据目录1. 检查现有磁盘2. 创建物理卷3. 创

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

Java实例化对象的​7种方式详解

《Java实例化对象的​7种方式详解》在Java中,实例化对象的方式有多种,具体取决于场景需求和设计模式,本文整理了7种常用的方法,文中的示例代码讲解详细,有需要的可以了解下... 目录1. ​new 关键字(直接构造)​2. ​反射(Reflection)​​3. ​克隆(Clone)​​4. ​反序列化

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Python解决雅努斯问题实例方案详解

《Python解决雅努斯问题实例方案详解》:本文主要介绍Python解决雅努斯问题实例方案,雅努斯问题是指AI生成的3D对象在不同视角下出现不一致性的问题,即从不同角度看物体时,物体的形状会出现不... 目录一、雅努斯简介二、雅努斯问题三、示例代码四、解决方案五、完整解决方案一、雅努斯简介雅努斯(Janu

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Python开发文字版随机事件游戏的项目实例

《Python开发文字版随机事件游戏的项目实例》随机事件游戏是一种通过生成不可预测的事件来增强游戏体验的类型,在这篇博文中,我们将使用Python开发一款文字版随机事件游戏,通过这个项目,读者不仅能够... 目录项目概述2.1 游戏概念2.2 游戏特色2.3 目标玩家群体技术选择与环境准备3.1 开发环境3