Coursera-Algorithms,Part I-Robert Sedgewick-Programming Assignment 5
程序员文章站
2022-07-09 13:48:39
...
Programming Assignment 5: Kd-Trees
0.完结祝贺
1.一个语言相关的问题
有一个关于语言的问题，记录一下理解，表述不一定准确，有空再深究：
Java的参数传递问题。
一个前提：自定义类型都是引用传递
作业里有一处递归，不断往一个栈里添加满足条件的点。各层递归之间用参数传递这个栈。递归完成以后，最外层的栈里就装好所有点了。
合理性：每一层递归都生成一个新 指针，通过引用传递，它们指向的是同一个栈——最外层初始化好的那一个。所以各层操作的是同一个栈。内层递归完成后，内层指针消失，但栈是在最外层定义的，其内容不受影响。
思维惯性使然下，打算套用这一形式写“最近邻点”功能，就出现问题了。
以为会发生这种事：变量作为参数在层间引用传递，每层找到更近的点就赋一个新值，递归完以后这个变量肯定是最近的点了，完美。
而实际发生的事：每层创建一个新指针，这个指针确实指向了外层找到的当前最近点。而在这这一层找到更近的点以后，赋值使得新指针指向新点（而不像前面的情况：一直指向最外层定义的栈），与外层断开联系。这层递归完成以后，指针消失，找到的更近的结果也丢失了。
“赋值”被加粗了，赋值是导致指针指向新内容、层间联系断开的原因，可是找到更近的点以后除了赋值没有别的办法——这与Point2D类型不可变（immutable）、Stack类型可变有关。如果Point2D也有一个方法改变自身坐标，就可以类似“在矩形内”的方法实现“最近点”了。可见类是否mutable是造成两者实现方法不同的深层原因。
2.StdDraw绘图
本课程提供标准绘图类StdDraw，使用前应进行一定初始化，设置画布大小画笔大小等。
StdDraw.setXscale(0, 1);
StdDraw.setYscale(0, 1);
StdDraw.setPenRadius(.01);否则画出来是空白。
（共线问题不画图硬着头皮还是写出来了，这次作业还是需要一些调试的，故上网搜索解决了画图空白问题。。）
3.最后的优化
最后几分有一个关于搜索顺序的优化，调试了有一阵子。
该优化针对类似下图的情况：左边半边没有被排除，搜索完右边以后左边的两个点谁先谁后？
本着“近的先搜索”的原则，能直观地判断应该先搜索2点。但是查询点既没有包含于2对应的矩形（rect）中、也没有包含于1对应的矩形中。人眼之所以能判断先搜索2点，是因为查询点与2都处于相对下方的位置。更准确地描述应为：将1、2对应矩形的分界线延长，将整个画布分为两部分，查询点与2处在同一部分。
到这里解法应该已经比较明朗了。我的方法：每个节点额外设置一个RectHV·对象rectDivideIntoTwo，表示该节点P与它的兄弟节点Q将整个画布划分成两份时，节点P对应的部分。下图的情况中，由于查询点包含于点2对应的rectDivideIntoTwo，故点2应先于1搜索。具体实现可能还有别的方式。
4.一个巧合：还需要优化吗？
提交时又碰到一个问题，只差1分不能通过，情况如图：查询点落在了分界线上
问题出在：第一步应该往左还是往右？我的解法与参考解相反。
测试信息：
Test 6a: insert points from file; check nearest() with random query points
and check traversal of kd-tree
* input5.txt
- failed on trial 14 of 1000
- performs incorrect traversal of kd-tree during call to nearest()
- sequence of points inserted:
A 0.7 0.2
B 0.5 0.4
C 0.2 0.3
D 0.4 0.7
E 0.9 0.6
- query point = (0.7, 0.01)
- student nearest() = (0.7, 0.2)
- reference nearest() = (0.7, 0.2)
- student distanceSquaredTo() = 0.0361
- reference distanceSquaredTo() = 0.0361
- student sequence of kd-tree nodes involved in calls to distanceSquaredTo():
A B C E
- reference sequence of kd-tree nodes involved in calls to distanceSquaredTo():
A E B C
* input10.txt
==> FAILED可以见到，给出的参考顺序是先搜索的右边的点(0.9 , 0.6)——一个比左边更远的点。从这里基本可以判定，这属于测试bug，而不是缺少某种优化了。
针对这种情况没有较简单的优化办法，先后顺序存粹取决于代码里哪种情况被放在了if中、哪种情况被放在了else中（contain方法是包括边界情况的，所以边界情况被归作哪一类与if-else中if的条件有关）。由于该单元测试的查询点是随机给出的，我猜测重复提交可能就能通过了，但是我没有做尝试——我调换了if和else的语句块，随后通过了测试。
5.代码
PointSET.java
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.SET;
import edu.princeton.cs.algs4.StdDraw;
public class PointSET {
private SET<Point2D> points;
public PointSET() // construct an empty set of points
{ points = new SET<Point2D>(); }
public boolean isEmpty() // is the set empty?
{ return points.isEmpty(); }
public int size() // number of points in the set
{ return points.size(); }
public void insert(Point2D p) // add the point to the set (if it is not already in the set)
{
if (p == null) throw new java.lang.IllegalArgumentException();
points.add(p);
}
public boolean contains(Point2D p) // does the set contain point p?
{
if (p == null) throw new java.lang.IllegalArgumentException();
return points.contains(p);
}
public void draw() // draw all points to standard draw
{
for (Point2D p : points)
p.draw();
}
public Iterable<Point2D> range(RectHV rect) // all points that are inside the rectangle (or on the boundary)
{
if (rect == null) throw new java.lang.IllegalArgumentException();
SET<Point2D> pointsInside = new SET<Point2D>();
for (Point2D p:points)
{
if (rect.contains(p))
pointsInside.add(p);
}
return pointsInside;
}
public Point2D nearest(Point2D p) // a nearest neighbor in the set to point p; null if the set is empty
{
if (p == null) throw new java.lang.IllegalArgumentException();
Double minDistance = null;
Double thisDistance = null;
Point2D nearest = null;
for (Point2D point:points)
{
thisDistance = point.distanceTo(p);
if (minDistance == null || thisDistance < minDistance)
{
minDistance = point.distanceTo(p);
nearest = point;
}
}
return nearest;
}
public static void main(String[] args) // unit testing of the methods (optional)
{
System.out.println("Client Starts:");
PointSET points = new PointSET();
Point2D p1 = new Point2D(1.1, 1.1); points.insert(p1);
Point2D p2 = new Point2D(2.2, 2.2); points.insert(p2);
Point2D p3 = new Point2D(3.3, 3.4); points.insert(p3);
Point2D p4 = new Point2D(4.5, 4.3); points.insert(p4);
Point2D p5 = new Point2D(5.9, 5.2); points.insert(p5);
Point2D p6 = new Point2D(6.7, 6.3); points.insert(p6);
Point2D p7 = new Point2D(7.2, 7.8); points.insert(p7);
Point2D p8 = new Point2D(8.5, 8.5); points.insert(p8);
Point2D p9 = new Point2D(9.7, 9.9); points.insert(p9);
StdDraw.setXscale(0, 10);
StdDraw.setYscale(0, 10);
StdDraw.setPenRadius(.01);
// points.draw();
RectHV rhv = new RectHV(2.5,2.5,6.5,9.7);
Iterable<Point2D> pointsInside = points.range(rhv);
for (Point2D p : pointsInside)
p.draw();
rhv.draw();
Point2D p = new Point2D(1.1,2.1);
p.drawTo(points.nearest(p));
}
}KdTree.java
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.StdDraw;
import java.util.Stack;
public class KdTree {
private Node root;
private class Node
{
private Point2D point;
private Node left,right;
private boolean ifUsingXCoord; // True: compare by x coordinates. False: y coordinates.
private RectHV rect; // Corresponding rectangular:
// One that contains the point and all its descendants
private RectHV rectDivideIntoTwo; // This point and its sibling divide the whole canvas into two
// parts. And this rectangular represents the part corresponding
// to this point. This is for some detailed optimization.
private int count;
public Node(Point2D point, Node parent)
{
if (parent == null)
// Constructing the root: 1. corresponding rectangle is the whole canvas
// 2. comparing by x coordinates
{
rect = new RectHV(0, 0, 1, 1);
rectDivideIntoTwo = new RectHV(0, 0, 1, 1);
// rect.draw(); // Debugging drawing
ifUsingXCoord = true;
}
else
// Construction other nodes: 1. corresponding rectangle is obtained by change one parameter
// of its parent's
// 2. alternately compare by x or y. Contrast to its parent
{
double xmin, xmax, ymin, ymax;
double xminDIT, xmaxDIT, yminDIT, ymaxDIT; // DIT: Divide Into Two
xmin = parent.rect.xmin();
xmax = parent.rect.xmax();
ymin = parent.rect.ymin();
ymax = parent.rect.ymax();
xminDIT = 0;
xmaxDIT = 1;
yminDIT = 0;
ymaxDIT = 1;
int comp = compare(point, parent.point, parent.ifUsingXCoord);
if (parent.ifUsingXCoord)
{
if (comp > 0)
xminDIT = xmin = parent.point.x();
else
xmaxDIT = xmax = parent.point.x();
}
else
{
if (comp > 0)
yminDIT = ymin = parent.point.y();
else
ymaxDIT = ymax = parent.point.y();
}
rect = new RectHV(xmin, ymin, xmax, ymax);
// rect.draw();
rectDivideIntoTwo = new RectHV(xminDIT, yminDIT, xmaxDIT, ymaxDIT);
ifUsingXCoord = !parent.ifUsingXCoord;
}
this.point = point;
count = 1;
}
}
public KdTree() // construct an empty set of points
{}
public boolean isEmpty() // is the set empty?
{ return root == null; }
public int size() // number of points in the set
{ return size(root); }
private int size(Node x)
{
if (x == null) return 0;
return x.count;
}
public void insert(Point2D p) // add the point to the set (if it is not already in the set)
{
if (p == null) throw new java.lang.IllegalArgumentException();
root = insert(root, null, p);
}
private Node insert(Node x, Node parentOfx, Point2D p)
{
if (x == null) return new Node(p, parentOfx);
int comp = compare(p, x.point, x.ifUsingXCoord);
if (comp > 0) x.right = insert(x.right, x, p);
else if (comp < 0) x.left = insert(x.left, x, p);
else x.point = p;
x.count = size(x.left) + 1 + size(x.right);
return x;
}
public boolean contains(Point2D p) // does the set contain point p?
{
if (p == null) throw new java.lang.IllegalArgumentException();
Node x = root;
int comp;
while (x != null)
{
comp = compare(p, x.point, x.ifUsingXCoord);
if (comp > 0) x = x.right;
else if (comp < 0) x = x.left;
else return true;
}
return false;
}
private Node pointToNode(Point2D p) // Debugging tool
{
Node x = root;
int comp;
while (x != null)
{
comp = compare(p, x.point, x.ifUsingXCoord);
if (comp > 0) x = x.right;
else if (comp < 0) x = x.left;
else return x;
}
return null;
}
private int compare(Point2D p1, Point2D p2, boolean ifUsingXCoord)
{
int temp;
if (ifUsingXCoord) temp = Double.compare(p1.x(), p2.x()); // Compare by x coordinates
else temp = Double.compare(p1.y(), p2.y()); // Compare by y coordinates
if (temp == 0) return p1.compareTo(p2); // Important!
return temp; // If the preferred coordinates are identical,
// compare by the other.
}
public void draw() // draw all points to standard draw
{
for (Point2D p: points())
p.draw();
}
private Iterable<Point2D> points()
{
Stack<Point2D> points = new Stack<Point2D>();
inorder(root, points);
return points;
}
private void inorder(Node x, Stack<Point2D> points)
// Add all the points in the tree rooted at x
{
if (x == null) return ;
inorder(x.left, points);
points.add(x.point);
inorder(x.right, points);
}
public Iterable<Point2D> range(RectHV rect) // all points that are inside the rectangle (or on the boundary)
{
if (rect == null) throw new java.lang.IllegalArgumentException();
Stack<Point2D> pointsInside = new Stack<Point2D>();
if (root == null) return pointsInside;
findInside(root, rect, pointsInside);
return pointsInside;
}
private void findInside(Node x, RectHV rect, Stack<Point2D> pointsInside)
// Push all the points inside the rectangular and in the tree rooted at x
{
if (x.left != null && rect.intersects(x.left.rect))
findInside(x.left, rect, pointsInside);
if (rect.contains(x.point))
pointsInside.add(x.point);
if (x.right != null && rect.intersects(x.right.rect))
findInside(x.right, rect, pointsInside);
}
public Point2D nearest(Point2D p) // a nearest neighbor in the set to point p; null if the set is empty
{
if (p == null) throw new java.lang.IllegalArgumentException();
if (root == null) return null;
Point2D currentNearest = root.point;
currentNearest = findNearest(root, p, currentNearest);
return currentNearest;
}
private Point2D findNearest(Node x, Point2D p, Point2D currentNearest)
// Find the a nearer point in the subtree rooted at x. Return the new one.
{
// System.out.println(x.point); // Debugging Info
if (x.right != null && x.right.rectDivideIntoTwo.contains(p))
// Query point is in the same part with x.right, therefore search x.right first.
{
if (x.point.distanceTo(p) < currentNearest.distanceTo(p)) // Parent first.
// Avoid recursion whenever possible
currentNearest = x.point;
if (x.right != null && x.right.rect.distanceTo(p) < currentNearest.distanceTo(p))
currentNearest = findNearest(x.right, p, currentNearest);
if (x.left != null && x.left.rect.distanceTo(p) < currentNearest.distanceTo(p))
currentNearest = findNearest(x.left, p, currentNearest);
}
else
// Query point is in the same part with x.left, therefore search x.left first.
{
if (x.point.distanceTo(p) < currentNearest.distanceTo(p))
currentNearest = x.point;
if (x.left != null && x.left.rect.distanceTo(p) < currentNearest.distanceTo(p))
currentNearest = findNearest(x.left, p, currentNearest);
if (x.right != null && x.right.rect.distanceTo(p) < currentNearest.distanceTo(p))
currentNearest = findNearest(x.right, p, currentNearest);
}
return currentNearest;
}
public static void main(String[] args) // unit testing of the methods (optional)
{
System.out.println("Client starts:");
KdTree kt = new KdTree();
System.out.println(kt.isEmpty());
Point2D p1 = new Point2D(0.7, 0.2); kt.insert(p1);
Point2D p2 = new Point2D(0.5, 0.4); kt.insert(p2);
Point2D p3 = new Point2D(0.2, 0.3); kt.insert(p3);
Point2D p4 = new Point2D(0.4, 0.7); kt.insert(p4);
Point2D p5 = new Point2D(0.9, 0.6); kt.insert(p5);
System.out.println(kt.size());
System.out.println(kt.isEmpty());
StdDraw.setXscale(0, 1);
StdDraw.setYscale(0, 1);
StdDraw.setPenRadius(.01);
// kt.draw();
RectHV rect = new RectHV(0.1,0.2,0.8,0.7);
rect.draw();
Iterable<Point2D> pointsInside = kt.range(rect);
for (Point2D p : pointsInside)
{ p.draw(); }
Point2D pTest = new Point2D(0.3, 0.4);
kt.nearest(pTest).drawTo(pTest);
Iterable<Point2D> points = kt.points();
for (Point2D p : points)
{ System.out.print(kt.pointToNode(p).count+" "); }
}
}