毕楷明 20111369 张炳旺 20111380 陈雁楠 20111384 自来水管道的连接优化问题 摘要 为了使自来水管道总长度最小， 现我们考虑通过分两步来解决。 首先，先确定点是否属于不可连接区域。我们分别通过点坐标 转换为极坐标后扩大区域再二维比大小、 离散法分割区域后点坐标带 入比对、以及边界限定后整体线性规划的方法确定点是否处于区域中。 最终考虑线性规划法的精确度最高，得出第 4、23、36、99点在不可 连接区域内。 再参考网上资料考虑最小连接问题，剔除无效点后，对剩余点 间距离以欧式距离赋值， 通过不可连接区域的距离赋值为无穷， 生成 带权邻接矩阵，再使用 kruskal 算法解出最小生成树，结果为 653.0196。 最后，对此最小生成树结果进行优化，考虑加入一点使得此值 更小，于是利用循环语句，将 x = 1~100 ；y = 1~100 共 100