不会吧！都2022年了，你还没有弄懂最接近点对问题？？？
相信我，就看这一篇就够啦！！！
1．问题描述
给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中该点对间的距离最小。
2．实验目的
1)掌握递归与分治法的基本思想及基本原理。
2)掌握使用分治法求解问题的一般特征及步骤。
3)掌握分治法的设计方法及复杂性分析方法。
掌握分治法解平面最接近点对算法设计思想、算法设计过程及程序编码实现。
采用分治法解最接近点对问题。请回答以下问题：
1)一维情形下如何用线性时间完成合并步骤？
2)二维情形下递归求解递归出口如何设置？
3)二维情形下证明该问题具有稀疏性质：什么是鸽舍原理？二维情形下为什么跨分割线点对能构成最接近点对候选者的最多只有6对？
4)在二维情形下如何能用线性时间完成左右最近点对与中间跨分割线点对的比较？
5)对算法做时间复杂性分析。
6)本题选做：二维情形设采用分治法解最接近点对问题，编程实现。
2022-04-07 09:08:00
164KB
【学习要点】
6.1 一般方法
6.2 背包问题
6.3 带时限的作业排序
6.4 最佳合并模式
6.5 最小代价生成树
6.6 单源最短路径
6.7 磁带最优存储
6.8 贪心法的基本要素
2022-02-10 11:04:05
3.15MB
【学习要点】
2.1 算法复杂度
2.2 渐近表示法
2.3 递推关系
2022-02-08 09:06:31
1.22MB
【学习要点】
5.1 分治法的基本思想
5.2 求最大最小元
5.3 二分搜索
5.4 排序问题
5.5 选择问题
5.6 斯特拉森矩阵乘法
2022-02-07 09:05:53
1.65MB