实验2_分治法求最近点对问题.zip_分治法求最近点对问题

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/626b76d21e41a87e8aa192ff/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/626b76d21e41a87e8aa192ff/bg1.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x1 h3 y2 ff1 fs0 fc0 sc0 ls0 ws0">实验二 分治法求最近点对问题</div><div class="t m0 x2 h3 y3 ff1 fs0 fc0 sc0 ls0 ws0">一、实验目的：</div><div class="t m0 x2 h4 y4 ff1 fs1 fc0 sc1 ls0 ws0">（<span class="ff2">1</span>）<span class="_ _0"></span>掌握分治法思想。</div><div class="t m0 x2 h4 y5 ff1 fs1 fc0 sc1 ls0 ws0">（<span class="ff2">2</span>）<span class="_ _0"></span>学会最近点对问题求解方法。</div><div class="t m0 x2 h3 y6 ff1 fs0 fc0 sc0 ls0 ws0">二、内容：</div><div class="t m0 x2 h4 y7 ff2 fs1 fc0 sc1 ls0 ws0">1. <span class="ff1">对于平面上给定的<span class="_ _1"> </span></span>N<span class="_"> </span><span class="ff1">个点，给出所有点对的最短距离，即，输入是平面上的<span class="_ _2"> </span></span>N<span class="_"> </span><span class="ff1">个点，输</span></div><div class="t m0 x2 h4 y8 ff1 fs1 fc0 sc1 ls0 ws0">出是<span class="_ _2"> </span><span class="ff2">N<span class="_"> </span></span>点中具有最短距离的两点。</div><div class="t m0 x2 h4 y9 ff2 fs1 fc0 sc1 ls0 ws0">2. <span class="ff1">要求随机生成<span class="_ _1"> </span></span>N<span class="_"> </span><span class="ff1">个点的平面坐标，应用蛮力法编程计算出所有点对的最短距离。</span></div><div class="t m0 x2 h4 ya ff2 fs1 fc0 sc1 ls0 ws0">3. <span class="ff1">要求随机生成<span class="_ _1"> </span></span>N<span class="_"> </span><span class="ff1">个点的平面坐标，应用分治法编程计算出所有点对的最短距离。</span></div><div class="t m0 x2 h4 yb ff2 fs1 fc0 sc1 ls0 ws0">4. <span class="ff1">分别对<span class="_ _1"> </span></span>N=100,1000,10000,100000<span class="ff1">，统计算法运行时间，比较理论效率与实测效率的差异，</span></div><div class="t m0 x2 h4 yc ff1 fs1 fc0 sc1 ls0 ws0">同时对蛮力法和分治法的算法效率进行分析和比较。</div><div class="t m0 x2 h4 yd ff2 fs1 fc0 sc1 ls0 ws0">5. <span class="ff1">如果能将算法执行过程利用图形界面输出，可获加分。</span></div><div class="t m0 x2 h3 ye ff1 fs0 fc0 sc0 ls0 ws0">三、算法思想提示</div><div class="t m0 x2 h4 yf ff2 fs1 fc0 sc1 ls0 ws0">1. <span class="ff1">预处理：根据输入点集<span class="_ _1"> </span></span>S<span class="_ _1"> </span><span class="ff1">中的<span class="_ _2"> </span></span>x<span class="_"> </span><span class="ff1">轴和<span class="_ _2"> </span></span>y<span class="_"> </span><span class="ff1">轴坐标进行排序，得到<span class="_ _2"> </span></span>X<span class="_"> </span><span class="ff1">和<span class="_ _2"> </span></span>Y<span class="_ _3"></span>,<span class="ff1">很显然此时<span class="_ _2"> </span></span>X<span class="_"> </span><span class="ff1">和<span class="_ _1"> </span></span>Y<span class="_ _2"> </span><span class="ff1">中</span></div><div class="t m0 x2 h4 y10 ff1 fs1 fc0 sc1 ls0 ws0">的点就是<span class="_ _2"> </span><span class="ff2">S<span class="_"> </span></span>中的点。</div><div class="t m0 x2 h4 y11 ff2 fs1 fc0 sc1 ls0 ws0">2. <span class="ff1">点数较少时的情形</span></div><div class="t m0 x2 h4 y12 ff2 fs1 fc0 sc1 ls0 ws0">3. <span class="ff1">点数</span>|S|>3<span class="_"> </span><span class="ff1">时，将平面点集<span class="_ _2"> </span></span>S<span class="_"> </span><span class="ff1">分割成为大小大致相等的两个子集<span class="_ _2"> </span></span>S</div><div class="t m0 x3 h5 y13 ff2 fs2 fc0 sc1 ls0 ws0">L</div><div class="t m0 x4 h4 y12 ff1 fs1 fc0 sc1 ls0 ws0">和<span class="_ _2"> </span><span class="ff2">S</span></div><div class="t m0 x5 h5 y13 ff2 fs2 fc0 sc1 ls0 ws0">R</div><div class="t m0 x6 h4 y12 ff1 fs1 fc0 sc1 ls0 ws0">，选取一个垂直</div><div class="t m0 x2 h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">线<span class="_ _2"> </span><span class="ff2">L<span class="_"> </span></span>作为分割直线，考虑<span class="_ _2"> </span><span class="ff2">X</span></div><div class="t m0 x7 h5 y15 ff2 fs2 fc0 sc1 ls0 ws0">L</div><div class="t m0 x8 h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">和<span class="_ _2"> </span><span class="ff2">X</span></div><div class="t m0 x9 h5 y15 ff2 fs2 fc0 sc1 ls0 ws0">R</div><div class="t m0 xa h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">，<span class="ff2">Y</span></div><div class="t m0 xb h5 y15 ff2 fs2 fc0 sc1 ls0 ws0">L</div><div class="t m0 xc h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">和<span class="_ _2"> </span><span class="ff2">Y</span></div><div class="t m0 xd h5 y15 ff2 fs2 fc0 sc1 ls0 ws0">R</div><div class="t m0 xe h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">，这里还需要排序吗？</div></div></div><div class="pi" data-data='{"ctm":[1.611850,0.000000,0.000000,1.611850,0.000000,0.000000]}'></div></div> </body> </html>