分治法求最近点对问题
分治法求最近点对问题,要求:1.对于平面上给定的N个点,给出所有点对的最短距离,即,输入是平面上的N个点,输出是N点中具有最短距离的两点。2.要求随机生成N个点的平面坐标,应用蛮力法编程计算出所有点对的最短距离。3.要求随机生成N个点的平面坐标,应用分治法编程计算出所有点对的最短距离。4.分别对N=100,1000,10000,100000,统计算法运行时间,比较理论效率与实测效率的差异,同时对蛮力法和分治法的算法效率进行分析和比较。5.如果能将算法执行过程利用图形界面输出,可获加分。
用户评论