Massive Algorithms: May 2016

Kd-Trees - Princeton Programming Assignment 5

http://coursera.cs.princeton.edu/algs4/assignments/kdtree.html
http://coursera.cs.princeton.edu/algs4/checklists/kdtree.html
Write a data type to represent a set of points in the unit square (all points have x- and y-coordinates between 0 and 1) using a 2d-tree to support efficient range search (find all of the points contained in a query rectangle) and nearest neighbor search (find a closest point to a query point). 2d-trees have numerous applications, ranging from classifying astronomical objects to computer animation to speeding up neural networks to mining data to image retrieval.

Range search and k-nearest neighbor

Geometric primitives. To get started, use the following geometric primitives for points and axis-aligned rectangles in the plane.

Use the immutable data type Point2D (part of algs4.jar) for points in the plane. Here is the subset of its API that you may use:

public class Point2D implements Comparable<Point2D> {
   public Point2D(double x, double y)              // construct the point (x, y)
   public  double x()                              // x-coordinate 
   public  double y()                              // y-coordinate 
   public  double distanceTo(Point2D that)         // Euclidean distance between two points 
   public  double distanceSquaredTo(Point2D that)  // square of Euclidean distance between two points 
   public     int compareTo(Point2D that)          // for use in an ordered symbol table 
   public boolean equals(Object that)              // does this point equal that object? 
   public    void draw()                           // draw to standard draw 
   public  String toString()                       // string representation 
}

Use the immutable data type RectHV (part of algs4.jar) for axis-aligned rectangles. Here is the subset of its API that you may use:

public class RectHV {
   public    RectHV(double xmin, double ymin,      // construct the rectangle [xmin, xmax] x [ymin, ymax] 
                    double xmax, double ymax)      // throw a java.lang.IllegalArgumentException if (xmin > xmax) or (ymin > ymax)
   public  double xmin()                           // minimum x-coordinate of rectangle 
   public  double ymin()                           // minimum y-coordinate of rectangle 
   public  double xmax()                           // maximum x-coordinate of rectangle 
   public  double ymax()                           // maximum y-coordinate of rectangle 
   public boolean contains(Point2D p)              // does this rectangle contain the point p (either inside or on boundary)? 
   public boolean intersects(RectHV that)          // does this rectangle intersect that rectangle (at one or more points)? 
   public  double distanceTo(Point2D p)            // Euclidean distance from point p to closest point in rectangle 
   public  double distanceSquaredTo(Point2D p)     // square of Euclidean distance from point p to closest point in rectangle 
   public boolean equals(Object that)              // does this rectangle equal that object? 
   public    void draw()                           // draw to standard draw 
   public  String toString()                       // string representation 
}

Do not modify these data types.
Brute-force implementation. Write a mutable data type PointSET.java that represents a set of points in the unit square. Implement the following API by using a red-black BST (using either SET from algs4.jar orjava.util.TreeSet).

public class PointSET {
   public         PointSET()                               // construct an empty set of points 
   public           boolean isEmpty()                      // is the set empty? 
   public               int size()                         // number of points in the set 
   public              void insert(Point2D p)              // add the point to the set (if it is not already in the set)
   public           boolean contains(Point2D p)            // does the set contain point p? 
   public              void draw()                         // draw all points to standard draw 
   public Iterable<Point2D> range(RectHV rect)             // all points that are inside the rectangle 
   public           Point2D nearest(Point2D p)             // a nearest neighbor in the set to point p; null if the set is empty 

   public static void main(String[] args)                  // unit testing of the methods (optional) 
}

Corner cases. Throw a java.lang.NullPointerException if any argument is null. Performance requirements. Your implementation should support insert() and contains() in time proportional to the logarithm of the number of points in the set in the worst case; it should support nearest() and range() in time proportional to the number of points in the set.
2d-tree implementation. Write a mutable data type KdTree.java that uses a 2d-tree to implement the same API (but replace PointSET with KdTree). A 2d-tree is a generalization of a BST to two-dimensional keys. The idea is to build a BST with points in the nodes, using the x- and y-coordinates of the points as keys in strictly alternating sequence.

Search and insert. The algorithms for search and insert are similar to those for BSTs, but at the root we use the x-coordinate (if the point to be inserted has a smaller x-coordinate than the point at the root, go left; otherwise go right); then at the next level, we use the y-coordinate (if the point to be inserted has a smaller y-coordinate than the point in the node, go left; otherwise go right); then at the next level the x-coordinate, and so forth.

insert (0.7, 0.2)
insert (0.5, 0.4)
insert (0.2, 0.3)
insert (0.4, 0.7)
insert (0.9, 0.6)

Draw. A 2d-tree divides the unit square in a simple way: all the points to the left of the root go in the left subtree; all those to the right go in the right subtree; and so forth, recursively. Your draw() method should draw all of the points to standard draw in black and the subdivisions in red (for vertical splits) and blue (for horizontal splits). This method need not be efficient—it is primarily for debugging.

The prime advantage of a 2d-tree over a BST is that it supports efficient implementation of range search and nearest neighbor search. Each node corresponds to an axis-aligned rectangle in the unit square, which encloses all of the points in its subtree. The root corresponds to the unit square; the left and right children of the root corresponds to the two rectangles split by the x-coordinate of the point at the root; and so forth.

Range search. To find all points contained in a given query rectangle, start at the root and recursively search for points in both subtrees using the following pruning rule: if the query rectangle does not intersect the rectangle corresponding to a node, there is no need to explore that node (or its subtrees). A subtree is searched only if it might contain a point contained in the query rectangle.
Nearest neighbor search. To find a closest point to a given query point, start at the root and recursively search in both subtrees using the following pruning rule: if the closest point discovered so far is closer than the distance between the query point and the rectangle corresponding to a node, there is no need to explore that node (or its subtrees). That is, a node is searched only if it might contain a point that is closer than the best one found so far. The effectiveness of the pruning rule depends on quickly finding a nearby point. To do this, organize your recursive method so that when there are two possible subtrees to go down, you always choose the subtree that is on the same side of the splitting line as the query point as the first subtree to explore—the closest point found while exploring the first subtree may enable pruning of the second subtree.

http://www.cs.princeton.edu/courses/archive/spr13/cos226/lectures/99GeometricSearch.pdf
1d range search
Range search: find all keys between k1 and k2.
Range count: number of keys between k1 and k2.
Unordered list. Fast insert, slow range search.
Ordered array. Slow insert, binary search for k1 and k2 to do range search.
N = number of keys
R = number of keys that match
public int size(Key lo, Key hi)
{
if (contains(hi)) return rank(hi) - rank(lo) + 1;
else return rank(hi) - rank(lo);
}

2-d orthogonal range search
Find/count points in a given h-v rectangle

2d orthogonal range search: grid implementation
Grid implementation.
ɾDivide space into M-by-M grid of squares.
ɾCreate list of points contained in each square.
ɾUse 2d array to directly index relevant square.
ɾInsert: add (x, y) to list for corresponding square.
ɾRange search: examine only squares that intersect 2d range query.

Space-time tradeoff.
ɾSpace: M 2 + N.
ɾTime: 1 + N / M 2 per square examined, on average.
Choose grid square size to tune performance.
ɾToo small: wastes space.
ɾToo large: too many points per square.
ɾRule of thumb: √N-by-√N grid.
Running time. [if points are evenly distributed]
ɾInitialize data structure: N.
ɾInsert point: 1.
ɾRange search: 1 per point in range

Grid implementation. Fast, simple solution for evenly-distributed points.
Problem. Clustering a well-known phenomenon in geometric data.
ɾLists are too long, even though average length is short.
ɾNeed data structure that adapts gracefully to data.

2d tree. Recursively divide space into two halfplanes.
Quadtree. Recursively divide space into four quadrants.
BSP tree. Recursively divide space into two regions.

2d tree implementation
Data structure. BST, but alternate using x- and y-coordinates as key.
ɾSearch gives rectangle containing point.
ɾInsert further subdivides the plane.

Range search in a 2d tree demo
Find all points in a query axis-aligned rectangle.
ɾCheck if point in node lies in given rectangle.
ɾRecursively search left/bottom (if any could fall in rectangle).
ɾRecursively search right/top (if any could fall in rectangle)

https://segmentfault.com/a/1190000005345079
课程开始先讲解了2-3 search trees，一种引入了新规则树型结构。这是一个“理解容易，实现复杂”的Symbol table方案，它可以对任何输入数据保证树形结构的平衡以达到保证各项操作logN的复杂度，而规则却足够简单到可以在课堂中很快描述清楚，可以算是课程中第一个令我惊艳的算法。
紧接着下一节就是我们的主角：左倾红黑二叉树(LLRB)。
它只做到了一件事：将2-3 tree带回了二叉树世界，却仅对朴素的二叉树做极其微小的改动——每个节点增加1 bit，用以表示“颜色”，加之无比简洁的引导，便在现实世界中实现了原先只是构想的2-3 tree几乎全部的优点。
红黑树本身就是70年代Sedgewick教授参与提出的，而LLRB是由他一手提出的极其简洁的红黑树实现版本，尤其是它的insertion，在课堂上作为重点讲解，仅在原朴素二叉树实现代码基础上，增加了3个小工具函数（左旋、右旋、翻转）和递归插入过程中的4行代码（如图），便完成了所有工作。

这次的作业同样包含了一个暴力算法的版本（使用默认的红黑树结构），除了在执行效率上可以做比较外，还提供了一个重要的软件工程思路：面临一个较为复杂，而优化空间很大的问题时，先实现一个最简单的暴力算法版本检测结果（往往可以非常简便地实现），再考虑进阶的算法与数据结构实现性能优化，并在实现期间，暴力算法可以作为检验算法正确性最直接的参考。
实现过程中值得提到的点：

节点的奇偶性是一个不小的麻烦，编写需要十分谨慎，我的做法是在Node类中添加了一个boolean用以表示奇偶，相信一定有更好的方法（不存储RectHV），还会回来探索；
Nearest Neighbor的查找过程需要思考清楚，剪枝的界限十分清晰，尤其是剪裁其中一个子树的条件：如果本子树中找到的最近点与给定点距离已小于给定点到另一子树矩形区域的距离（点到点距离比点到矩形距离还近时），才能跳过另一子树的遍历过程。

https://github.com/Revil/algs-kdtree
public class KdTree {

private static class Node {
private Point2D p;
private RectHV rect;
private Node left;
private Node right;

public Node(Point2D p, RectHV rect) {
RectHV r = rect;
if (r == null)
r = new RectHV(0, 0, 1, 1);
this.rect = r;
this.p = p;
}
}

private Node root;
private int size;

// construct an empty set of points
public KdTree() {
root = null;
size = 0;
}

// is the set empty?
public boolean isEmpty() { return root == null; }

// number of points in the set
public int size() { return size; }

// larger or equal keys go right
private Node insertH(Node x, Point2D p, RectHV rect) {
if (x == null) {
size++;
return new Node(p, rect);
}
if (x.p.equals(p)) return x;

RectHV r;
int cmp = Point2D.Y_ORDER.compare(x.p, p);
if (cmp > 0) {
if (x.left == null)
r = new RectHV(rect.xmin(), rect.ymin(), rect.xmax(), x.p.y());
else
r = x.left.rect;
x.left = insertV(x.left, p, r);
} else {
if (x.right == null)
r = new RectHV(rect.xmin(), x.p.y(), rect.xmax(), rect.ymax());
else
r = x.right.rect;
x.right = insertV(x.right, p, r);
}

return x;
}

// larger or equal keys go right
private Node insertV(Node x, Point2D p, RectHV rect) {
if (x == null) {
size++;
return new Node(p, rect);
}
if (x.p.equals(p)) return x;

RectHV r;
int cmp = Point2D.X_ORDER.compare(x.p, p);
if (cmp > 0) {
if (x.left == null)
r = new RectHV(rect.xmin(), rect.ymin(), x.p.x(), rect.ymax());
else
r = x.left.rect;
x.left = insertH(x.left, p, r);
} else {
if (x.right == null)
r = new RectHV(x.p.x(), rect.ymin(), rect.xmax(), rect.ymax());
else
r = x.right.rect;
x.right = insertH(x.right, p, r);
}

return x;
}

// add the point p to the set (if it is not already in the set)
public void insert(Point2D p) {
if (isEmpty())
root = insertV(root, p, null);
else
root = insertV(root, p, root.rect);
}

// larger or equal keys go right
private boolean contains(Node x, Point2D p, boolean vert) {
if (x == null) return false;
if (x.p.equals(p)) return true;
int cmp;
if (vert) cmp = Point2D.X_ORDER.compare(x.p, p);
else cmp = Point2D.Y_ORDER.compare(x.p, p);
if (cmp > 0) return contains(x.left, p, !vert);
else return contains(x.right, p, !vert);
}

// does the set contain the point p?
public boolean contains(Point2D p) {
return contains(root, p, true);
}

private void draw(Node x, boolean vert) {
if (x.left != null) draw(x.left, !vert);
if (x.right != null) draw(x.right, !vert);

// draw the point first
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(.01);
StdDraw.point(x.p.x(), x.p.y());

// draw the line
double xmin, ymin, xmax, ymax;
if (vert) {
StdDraw.setPenColor(StdDraw.RED);
xmin = x.p.x();
xmax = x.p.x();
ymin = x.rect.ymin();
ymax = x.rect.ymax();
} else {
StdDraw.setPenColor(StdDraw.BLUE);
ymin = x.p.y();
ymax = x.p.y();
xmin = x.rect.xmin();
xmax = x.rect.xmax();
}
StdDraw.setPenRadius();
StdDraw.line(xmin, ymin, xmax, ymax);
}

// draw all of the points to standard draw
public void draw() {
// draw the rectangle
StdDraw.rectangle(0.5, 0.5, 0.5, 0.5);
if (isEmpty()) return;
draw(root, true);
}

private void range(Node x, RectHV rect, Queue<Point2D> q) {
if (x == null)
return;
if (rect.contains(x.p))
q.enqueue(x.p);
if (x.left != null && rect.intersects(x.left.rect))
range(x.left, rect, q);
if (x.right != null && rect.intersects(x.right.rect))
range(x.right, rect, q);
}

// all points in the set that are inside the rectangle
public Iterable<Point2D> range(RectHV rect) {
Queue<Point2D> q = new Queue<Point2D>();
range(root, rect, q);
return q;
}

private Point2D nearest(Node x, Point2D p, Point2D mp, boolean vert) {
Point2D min = mp;

if (x == null) return min;
if (p.distanceSquaredTo(x.p) < p.distanceSquaredTo(min))
min = x.p;

// choose the side that contains the query point first
if (vert) {
if (x.p.x() < p.x()) {
min = nearest(x.right, p, min, !vert);
if (x.left != null
&& (min.distanceSquaredTo(p)
> x.left.rect.distanceSquaredTo(p)))
min = nearest(x.left, p, min, !vert);
} else {
min = nearest(x.left, p, min, !vert);
if (x.right != null
&& (min.distanceSquaredTo(p)
> x.right.rect.distanceSquaredTo(p)))
min = nearest(x.right, p, min, !vert);
}
} else {
if (x.p.y() < p.y()) {
min = nearest(x.right, p, min, !vert);
if (x.left != null
&& (min.distanceSquaredTo(p)
> x.left.rect.distanceSquaredTo(p)))
min = nearest(x.left, p, min, !vert);
} else {
min = nearest(x.left, p, min, !vert);
if (x.right != null
&& (min.distanceSquaredTo(p)
> x.right.rect.distanceSquaredTo(p)))
min = nearest(x.right, p, min, !vert);
}
}
return min;
}

// a nearest neighbor in the set to p: null if set is empty
public Point2D nearest(Point2D p) {
if (isEmpty()) return null;
return nearest(root, p, root.p, true);
}
}

Brute Force:
public class PointSET {

private SET<Point2D> set;

// construct an empty set of points
public PointSET() { set = new SET<Point2D>(); }

// is the set empty?
public boolean isEmpty() { return set.isEmpty(); }

// number of points in the set
public int size() { return set.size(); }

// add the point p to the set (if it is not already in the set)
// proportional to logarithm of N in the worst case
public void insert(Point2D p) { set.add(p); }

// does the set contain the point p?
// proportional to logarithm of N in the worst case
public boolean contains(Point2D p) { return set.contains(p); }

// draw all of the points to standard draw
public void draw() {
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(.01);

for (Point2D p : set)
StdDraw.point(p.x(), p.y());

StdDraw.show(0);
}

// all points in the set that are inside the rectangle
// proportional to N in the worst case
public Iterable<Point2D> range(RectHV rect) {
Stack<Point2D> s = new Stack<Point2D>();

for (Point2D p : set)
if (rect.contains(p))
s.push(p);

return s;
}

// a nearest neighbor in the set to p: null if set is empty
// proportional to N
public Point2D nearest(Point2D p) {
if (isEmpty()) return null;

double dis, minDis = Double.MAX_VALUE;
Point2D q = null;

for (Point2D ip : set) {
dis = p.distanceSquaredTo(ip);
if (dis < minDis) {
minDis = dis;
q = ip;
}
}

return q;
}
}
https://github.com/Revil/algs-kdtree/blob/master/RectHV.java
public double distanceTo(Point2D p) {
return Math.sqrt(this.distanceSquaredTo(p));
}

// distance squared from p to closest point on this axis-aligned rectangle
public double distanceSquaredTo(Point2D p) {
double dx = 0.0, dy = 0.0;
if (p.x() < xmin) dx = p.x() - xmin;
else if (p.x() > xmax) dx = p.x() - xmax;
if (p.y() < ymin) dy = p.y() - ymin;
else if (p.y() > ymax) dy = p.y() - ymax;
return dx*dx + dy*dy;
}

// does this axis-aligned rectangle contain p?
public boolean contains(Point2D p) {
return (p.x() >= xmin) && (p.x() <= xmax)
&& (p.y() >= ymin) && (p.y() <= ymax);
}

https://github.com/iman89/princeton/blob/master/KDTrees/src/KdTree.java

8 Puzzle - Princeton Programming Assignment 4

http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html
Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.
The problem. The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order, using as few moves as possible. You are permitted to slide blocks horizontally or vertically into the blank square. The following shows a sequence of legal moves from an initial board (left) to the goal board (right).


1  3        1     3        1  2  3        1  2  3        1  2  3
 4  2  5   =>   4  2  5   =>   4     5   =>   4  5      =>   4  5  6
 7  8  6        7  8  6        7  8  6        7  8  6        7  8 

 initial        1 left          2 up          5 left          goal

Best-first search. Now, we describe a solution to the problem that illustrates a general artificial intelligence methodology known as the A* search algorithm. We define a search node of the game to be a board, the number of moves made to reach the board, and the previous search node. First, insert the initial search node (the initial board, 0 moves, and a null previous search node) into a priority queue. Then, delete from the priority queue the search node with the minimum priority, and insert onto the priority queue all neighboring search nodes (those that can be reached in one move from the dequeued search node). Repeat this procedure until the search node dequeued corresponds to a goal board. The success of this approach hinges on the choice of priority function for a search node. We consider two priority functions:

Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the search node. Intuitively, a search node with a small number of blocks in the wrong position is close to the goal, and we prefer a search node that have been reached using a small number of moves.
Manhattan priority function. The sum of the Manhattan distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the search node.

For example, the Hamming and Manhattan priorities of the initial search node below are 5 and 10, respectively.


8  1  3        1  2  3     1  2  3  4  5  6  7  8    1  2  3  4  5  6  7  8
 4     2        4  5  6     ----------------------    ----------------------
 7  6  5        7  8        1  1  0  0  1  1  0  1    1  2  0  0  2  2  0  3

 initial          goal         Hamming = 5 + 0          Manhattan = 10 + 0

We make a key observation: To solve the puzzle from a given search node on the priority queue, the total number of moves we need to make (including those already made) is at least its priority, using either the Hamming or Manhattan priority function. (For Hamming priority, this is true because each block that is out of place must move at least once to reach its goal position. For Manhattan priority, this is true because each block must move its Manhattan distance from its goal position. Note that we do not count the blank square when computing the Hamming or Manhattan priorities.) Consequently, when the goal board is dequeued, we have discovered not only a sequence of moves from the initial board to the goal board, but one that makes the fewest number of moves. (Challenge for the mathematically inclined: prove this fact.)
A critical optimization. Best-first search has one annoying feature: search nodes corresponding to the same board are enqueued on the priority queue many times. To reduce unnecessary exploration of useless search nodes, when considering the neighbors of a search node, don't enqueue a neighbor if its board is the same as the board of the previous search node.


8  1  3       8  1  3       8  1       8  1  3     8  1  3
 4     2       4  2          4  2  3    4     2     4  2  5
 7  6  5       7  6  5       7  6  5    7  6  5     7  6

 previous    search node    neighbor   neighbor    neighbor
                                      (disallow)

Game tree. One way to view the computation is as a game tree, where each search node is a node in the game tree and the children of a node correspond to its neighboring search nodes. The root of the game tree is the initial search node; the internal nodes have already been processed; the leaf nodes are maintained in a priority queue; at each step, the A* algorithm removes the node with the smallest priority from the priority queue and processes it (by adding its children to both the game tree and the priority queue).
8puzzle game tree

Detecting unsolvable puzzles. Not all initial boards can lead to the goal board by a sequence of legal moves, including the two below:


1  2  3         1  2  3  4
 4  5  6         5  6  7  8
 8  7            9 10 11 12
                13 15 14 
unsolvable
                unsolvable

To detect such situations, use the fact that boards are divided into two equivalence classes with respect to reachability: (i) those that lead to the goal board and (ii) those that lead to the goal board if we modify the initial board by swapping any pair of blocks (the blank square is not a block). (Difficult challenge for the mathematically inclined: prove this fact.) To apply the fact, run the A* algorithm on two puzzle instances—one with the initial board and one with the initial board modified by swapping a pair of blocks—in lockstep (alternating back and forth between exploring search nodes in each of the two game trees). Exactly one of the two will lead to the goal board.
Board and Solver data types. Organize your program by creating an immutable data type Board with the following API:

public class Board {
    public Board(int[][] blocks)           // construct a board from an N-by-N array of blocks
                                           // (where blocks[i][j] = block in row i, column j)
    public int dimension()                 // board dimension N
    public int hamming()                   // number of blocks out of place
    public int manhattan()                 // sum of Manhattan distances between blocks and goal
    public boolean isGoal()                // is this board the goal board?
    public Board twin()                    // a board that is obtained by exchanging any pair of blocks
    public boolean equals(Object y)        // does this board equal y?
    public Iterable<Board> neighbors()     // all neighboring boards
    public String toString()               // string representation of this board (in the output format specified below)

    public static void main(String[] args) // unit tests (not graded)
}

Corner cases. You may assume that the constructor receives an N-by-N array containing the N² integers between 0 and N² − 1, where 0 represents the blank square.
Performance requirements. Your implementation should support all Board methods in time proportional to N² (or better) in the worst case.
Also, create an immutable data type Solver with the following API:

public class Solver {
    public Solver(Board initial)           // find a solution to the initial board (using the A* algorithm)
    public boolean isSolvable()            // is the initial board solvable?
    public int moves()                     // min number of moves to solve initial board; -1 if unsolvable
    public Iterable<Board> solution()      // sequence of boards in a shortest solution; null if unsolvable
    public static void main(String[] args) // solve a slider puzzle (given below)
}

To implement the A* algorithm, you must use MinPQ from algs4.jar for the priority queue(s).

Corner cases. The constructor should throw a java.lang.NullPointerException if passed a null argument.

http://coursera.cs.princeton.edu/algs4/checklists/8puzzle.html

I'm a bit confused about the purpose of the twin() method. You will use it to determine whether a puzzle is solvable: exactly one of a board and its twin are solvable. A twin is obtained by swapping any pair of blocks (the blank square is not a block). For example, here is a board and several possible twins. Your solver will use only one twin.

    1  3       3  1       1  3       1  3       1  3       6  3
 4  2  5    4  2  5    2  4  5    4  5  2    4  2  5    4  2  5
 7  8  6    7  8  6    7  8  6    7  8  6    8  7  6    7  8  1

  board      twin       twin       twin       twin       twin

How do I reconstruct the solution once I've dequeued the goal search node? Since each search node records the previous search node to get there, you can chase the pointers all the way back to the initial search node (and consider them in reverse order).
Can I terminate the search as soon as a goal search node is enqueued (instead of dequeued)? No, even though it does lead to a correct solution for the slider puzzle problem using the Hamming and Manhattan priority functions, it's not technically the A* algorithm (and will not find the correct solution for other problems and other priority functions).
I noticed that the priorities of the search nodes dequeued from the priority queue never decrease. Is this a property of the A* algorithm? Yes. In the language of the A* algorithm, the Hamming and Manhattan distances (before adding in the number of moves so far) are known as heuristics. If a heuristic is both admissible (never overestimates the number of moves to the goal search node) and consistent (satisfies a certain triangle inequality), then this noticed property is guaranteed. The Hamming and Manhattan heuristics are both admissible and consistent. You may use this noticed property as a debugging clue: if the priority of the search node dequeued from the priority queue decreases, then you know you did something wrong.
Even with the critical optimization, the priority queue may contain two or more search nodes corresponding to the same board. Should I try to eliminate these? In principle, you could do so with a set data type such as SET in algs4.jar or java.util.TreeSet or java.util.HashSet (provided that the Board data type were either Comparable or had a hashCode() method). However, almost all of the benefit from avoiding duplicate boards is already extracted from the critical optimization and the cost of identifying other duplicate boards will be more than the remaining benefit from doing so.
Can I put the logic for detecting whether a puzzle is infeasible in Board instead of Solver? There is a elegant algorithm for determining whether a board is solvable that relies on a parity argument (and occasionally we change our API to require this solution). However, the current API requires you to detect infeasiblity in Solver by using two synchronized A* searches (e.g., using two priority queues).

https://segmentfault.com/a/1190000005345079

随着学习的深入，这次作业的复杂度有了一个明显的上升，但这门课最美妙的地方之一也就在这里：面临的问题越来越复杂，而导师给出的指导思路依然保持最大程度的简洁优雅，每一步骤的设定都直指问题核心，并在实现功能基础上提供非常丰富的优化选择，以及每个优化会带来的影响分析

整个问题相对比较复杂，但经过给定API的划分和给定的限制后，问题变成了实现一个个目标明确的小方法而已，其中最复杂的不过是A*的实现，而周到合理的封装和PQ的使用也使得这个过程无比自然，在此之前我从未意识到我可以将A*在如此短小清晰的代码中实现：（源码如此，仅省略了声明过程）

while (!pq.min().board.isGoal()) { 
    cur = pq.delMin();
    for (Board nb : cur.board.neighbors()) {
        if (cur.prev != null && nb.equals(cur.prev.board)) continue;
        pq.insert(new Node(nb, cur.moves+1, cur));
    }
}

PQ使用了Manhattan Priority作为Comparator，Node为封装Board的单链表节点，结束后获取最短路径只需取PQ中最小Node，利用prev指针遍历。
解决8 Puzzle这一NP难问题的核心代码便完成了。
当然，在其余部分还是有不少值得提到的点：

用char[]存储一个Board的状态比用int[][]好太多，但使用前需要详细测试将char做数字使用与直接用int的区别；
Board的equals()方法只需比较char[]构成的String即可，早期因图省事直接比较了toString()的返回值（one-liner），造成了很大的性能损失，最后寻找问题来源也费了不少功夫（教训：看似再简单的部分也要在脑袋里多转一转再下手，devil in the details，…，you name it）；
Solvability: 这篇文章描述的解决方案应为checklist所述方案，但需要脆弱地依赖toString()反推Board内容，在本期课程的API设定中已被明确禁止，要求使用两个同步A*的方案解决（最好使用一个PQ），但未来session可能会在两方案对应API设定间切换，所以我都实现了一遍，上面出现的A*代码来自文章所述方案；
实现Priority的cache时需要稍多做思考，直觉想到的第一方案是储存在Node中与A*过程配合，而这将使A*代码迅速肿胀，且没有很好地利用更多规律：如checklist所指出，对相邻Board每次重新计算Priority其实也有很多重复工作，我的做法是将cache过程作为Board类一个私有构造函数，构造相邻Priority只需做对应增量操作即可，以最简洁的手段达到了目的。

https://github.com/keyvanakbary/princeton-algorithms/tree/master/week-4-8-puzzle

public class Board {

private static final int SPACE = 0;

private int[][] blocks;

public Board(int[][] blocks) {

this.blocks = copy(blocks);

}

private int[][] copy(int[][] blocks) {

int[][] copy = new int[blocks.length][blocks.length];

for (int row = 0; row < blocks.length; row++)

for (int col = 0; col < blocks.length; col++)

copy[row][col] = blocks[row][col];

return copy;

}

public int dimension() {

return blocks.length;

}

public int hamming() {

int count = 0;

for (int row = 0; row < blocks.length; row++)

for (int col = 0; col < blocks.length; col++)

if (blockIsNotInPlace(row, col)) count++;

return count;

}

private boolean blockIsNotInPlace(int row, int col) {

int block = block(row, col);

return !isSpace(block) && block != goalFor(row, col);

}

private int goalFor(int row, int col) {

return row*dimension() + col + 1;

}

private boolean isSpace(int block) {

return block == SPACE;

}

public int manhattan() {

int sum = 0;

for (int row = 0; row < blocks.length; row++)

for (int col = 0; col < blocks.length; col++)

sum += calculateDistances(row, col);

return sum;

}

private int calculateDistances(int row, int col) {

int block = block(row, col);

return (isSpace(block)) ? 0 : Math.abs(row - row(block)) + Math.abs(col - col(block));

}

private int block(int row, int col) {

return blocks[row][col];

}

private int row (int block) {

return (block - 1) / dimension();

}

private int col (int block) {

return (block - 1) % dimension();

}

public boolean isGoal() {

for (int row = 0; row < blocks.length; row++)

for (int col = 0; col < blocks.length; col++)

if (blockIsInPlace(row, col)) return false;

return true;

}

private boolean blockIsInPlace(int row, int col) {

int block = block(row, col);

return !isSpace(block) && block != goalFor(row, col);

}

public Board twin() {

for (int row = 0; row < blocks.length; row++)

for (int col = 0; col < blocks.length - 1; col++)

if (!isSpace(block(row, col)) && !isSpace(block(row, col + 1)))

return new Board(swap(row, col, row, col + 1));

throw new RuntimeException();

}

private int[][] swap(int row1, int col1, int row2, int col2) {

int[][] copy = copy(blocks);

int tmp = copy[row1][col1];

copy[row1][col1] = copy[row2][col2];

copy[row2][col2] = tmp;

return copy;

}

public boolean equals(Object y) {

if (y==this) return true;

if (y==null || !(y instanceof Board) || ((Board)y).blocks.length != blocks.length) return false;

for (int row = 0; row < blocks.length; row++)

for (int col = 0; col < blocks.length; col++)

if (((Board) y).blocks[row][col] != block(row, col)) return false;

return true;

}

public Iterable<Board> neighbors() {

LinkedList<Board> neighbors = new LinkedList<Board>();

int[] location = spaceLocation();

int spaceRow = location[0];

int spaceCol = location[1];

if (spaceRow > 0) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow - 1, spaceCol)));

if (spaceRow < dimension() - 1) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow + 1, spaceCol)));

if (spaceCol > 0) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow, spaceCol - 1)));

if (spaceCol < dimension() - 1) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow, spaceCol + 1)));

return neighbors;

}

private int[] spaceLocation() {

for (int row = 0; row < blocks.length; row++)

for (int col = 0; col < blocks.length; col++)

if (isSpace(block(row, col))) {

int[] location = new int[2];

location[0] = row;

location[1] = col;

return location;

}

throw new RuntimeException();

}

public String toString() {

StringBuilder str = new StringBuilder();

str.append(dimension() + "\n");

for (int row = 0; row < blocks.length; row++) {

for (int col = 0; col < blocks.length; col++)

str.append(String.format("%2d ", block(row, col)));

str.append("\n");

}

return str.toString();

}

public class Solver {

private class Move implements Comparable<Move> {

private Move previous;

private Board board;

private int numMoves = 0;

public Move(Board board) {

this.board = board;

}

public Move(Board board, Move previous) {

this.board = board;

this.previous = previous;

this.numMoves = previous.numMoves + 1;

}

public int compareTo(Move move) {

return (this.board.manhattan() - move.board.manhattan()) + (this.numMoves - move.numMoves);

}

private Move lastMove;

public Solver(Board initial) {

MinPQ<Move> moves = new MinPQ<Move>();

moves.insert(new Move(initial));

MinPQ<Move> twinMoves = new MinPQ<Move>();

twinMoves.insert(new Move(initial.twin()));

while(true) {

lastMove = expand(moves);

if (lastMove != null || expand(twinMoves) != null) return;

}

private Move expand(MinPQ<Move> moves) {

if(moves.isEmpty()) return null;

Move bestMove = moves.delMin();

if (bestMove.board.isGoal()) return bestMove;

for (Board neighbor : bestMove.board.neighbors()) {

if (bestMove.previous == null || !neighbor.equals(bestMove.previous.board)) {

moves.insert(new Move(neighbor, bestMove));

}

return null;

}

public boolean isSolvable() {

return (lastMove != null);

}

public int moves() {

return isSolvable() ? lastMove.numMoves : -1;

}

public Iterable<Board> solution() {

if (!isSolvable()) return null;

Stack<Board> moves = new Stack<Board>();

while(lastMove != null) {

moves.push(lastMove.board);

lastMove = lastMove.previous;

}

return moves;

}

http://blog.csdn.net/liuweiran900217/article/details/19818289

Is there an efficient way to solve the 8-puzzle and its generalizations?Finding a shortest solution to an N-by-N slider puzzle isNP-hard,so it's unlikely that an efficient solution exists.

如果这是一个NP-hard问题，我们只有两种思路：一种是找出概率解，也就是说在多项式时间内做出一个解，这个解有很大的概率是正确的；另一种就是用搜索树等方法来搜索到精确解，但是搜索解本身可能是一个时间复杂度或者空间复杂度为指数复杂度的算法。

Princeton的《Algorithm》给出了一个使用A*搜索的方式来进行解决。其思路和Coursera中另一个公开课《Generic Game Playing》的搜索树算法很像，大致思路是：对于每一个中间解，计算一个这个解是“正确的”大概期望，按照每一个中间解的期望对搜索树进行排序，优先搜索期望大的解。在本题中，所谓的“期望”就是Hamming priority和Manhattan priority。对搜索树排序的方法就是Week4中的优先队列。

上述算法一定能够搜索到正确的解，因为搜索树最极限的情况也就是把所有的可能移动方法都搜索一遍嘛，所以在最糟糕情况下，算法的时间复杂度和空间复杂度都将会是指数级的。

但是，能否搜索到解还有一个情况，就是能否判断8 Puzzle的这个实例是否确实存在解。但是，是否存在解这个确定问题也是一个NP-hard问题，至今没有一个多项式时间算法能在多项式空间复杂度内回答一个8 Puzzle实例是否存在解。针对此问题，《Algorithm》给出了一种判断方法。8 Puzzle问题可分为两类：给定实例存在解，或给定实例的“Twin”实例存在解。因此，整个算法要求构造一个给定实例的Twin实例，然后同时在两个实例中运行搜索算法：如果给定实例找到了解，那么就输出解；如果Twin实例找到了解，那么说明给定实例不存在解，输出null。

http://www.1point3acres.com/bbs/thread-84775-1-1.html

Princeton Programming Assignment 3: Pattern Recognition

http://coursera.cs.princeton.edu/algs4/assignments/collinear.html
https://www.cs.princeton.edu/courses/archive/fall12/cos226/checklist/collinear.html
Computer vision involves analyzing patterns in visual images and reconstructing the real-world objects that produced them. The process is often broken up into two phases: feature detection and pattern recognition. Feature detection involves selecting important features of the image; pattern recognition involves discovering patterns in the features. We will investigate a particularly clean pattern recognition problem involving points and line segments. This kind of pattern recognition arises in many other applications such as statistical data analysis.
The problem. Given a set of N distinct points in the plane, find every (maximal) line segment that connects a subset of 4 or more of the points.

Points and lines

Brute force. Write a program BruteCollinearPoints.java that examines 4 points at a time and checks whether they all lie on the same line segment, returning all such line segments. To check whether the 4 points p, q, r, and s are collinear, check whether the three slopes between p and q, between p and r, and between p and s are all equal.

public class BruteCollinearPoints {
   public BruteCollinearPoints(Point[] points)    // finds all line segments containing 4 points
   public           int numberOfSegments()        // the number of line segments
   public LineSegment[] segments()                // the line segments
}

The method segments() should include each line segment containing 4 points exactly once. If 4 points appear on a line segment in the order p→q→r→s, then you should include either the line segment p→s or s→p (but not both) and you should not include subsegments such as p→r or q→r. For simplicity, we will not supply any input to BruteCollinearPoints that has 5 or more collinear points.
Corner cases. Throw a java.lang.NullPointerException either the argument to the constructor is null or if any point in the array is null. Throw a java.lang.IllegalArgumentException if the argument to the constructor contains a repeated point.
Performance requirement. The order of growth of the running time of your program should be N⁴ in the worst case and it should use space proportional to N plus the number of line segments returned.
A faster, sorting-based solution. Remarkably, it is possible to solve the problem much faster than the brute-force solution described above. Given a point p, the following method determines whether p participates in a set of 4 or more collinear points.

Think of p as the origin.
For each other point q, determine the slope it makes with p.
Sort the points according to the slopes they makes with p.
Check if any 3 (or more) adjacent points in the sorted order have equal slopes with respect to p. If so, these points, together with p, are collinear.

Applying this method for each of the N points in turn yields an efficient algorithm to the problem. The algorithm solves the problem because points that have equal slopes with respect to p are collinear, and sorting brings such points together. The algorithm is fast because the bottleneck operation is sorting.
Points and slopes

Write a program FastCollinearPoints.java that implements this algorithm.

public class FastCollinearPoints {
   public FastCollinearPoints(Point[] points)     // finds all line segments containing 4 or more points
   public           int numberOfSegments()        // the number of line segments
   public LineSegment[] segments()                // the line segments
}

The method segments() should include each maximal line segment containing 4 (or more) points exactly once. For example, if 5 points appear on a line segment in the order p→q→r→s→t, then do not include the subsegments p→s or q→t.
Corner cases. Throw a java.lang.NullPointerException either the argument to the constructor is null or if any point in the array is null. Throw a java.lang.IllegalArgumentException if the argument to the constructor contains a repeated point.
Performance requirement. The order of growth of the running time of your program should be N² log N in the worst case and it should use space proportional to N plus the number of line segments returned.FastCollinearPoints should work properly even if the input has 5 or more collinear points.

https://github.com/zhichaoh/Coursera-Algorithms/blob/f03dd5839a360af56c1cd3aa8a6361d0d1ec764c/src/Fast.java

public static void main(String[] args) throws IOException {

String fileName = args[0];

List<Point> points = readList(fileName);

Collections.sort(points);

StdDraw.setXscale(0, 32768);

StdDraw.setYscale(0, 32768);

for(int i=0;i<points.size();i++) points.get(i).draw();

Map<String, Boolean> printedMap = new HashMap<String, Boolean>();

for(int i=0;i<points.size();i++) {

List<Point> tmpPoints = new ArrayList<Point>();

for(int j=i+1;j<points.size();j++) tmpPoints.add(points.get(j));

Collections.sort(tmpPoints, points.get(i).SLOPE_ORDER);

for(int j=0;j<tmpPoints.size();){

double slote = points.get(i).slopeTo(tmpPoints.get(j));

List<Point> nList = new ArrayList<Point>();

nList.add(points.get(i)); nList.add(tmpPoints.get(j));

j++;

while(j<tmpPoints.size() && points.get(i).slopeTo(tmpPoints.get(j))==slote) {

nList.add(tmpPoints.get(j));

j ++;

}

if(nList.size()>=4) {

boolean printedFlag = false;

for(int k=0;k<nList.size()-1;k++) {

String seg = nList.get(k).toString()+","+nList.get(k+1).toString();

if(!printedMap.containsKey(seg)) {

printedMap.put(seg, true);

printedFlag = true;

}

if(printedFlag){

Collections.sort(nList);

for(int k=0;k<nList.size()-1;k++) System.out.print(nList.get(k)+" -> ");

System.out.print(nList.get(nList.size()-1)+"\n");

points.get(i).drawTo(nList.get(nList.size()-1));

}

https://github.com/vgoodvin/princeton-algs4/tree/master/Collinear%20Points

public static void main(String[] args) {

// Rescale the coordinate system.

StdDraw.setXscale(0, 32768);

StdDraw.setYscale(0, 32768);

// Read points from the input file.

In in = new In(args[0]);

int pointsCount = in.readInt();

Point[] points = new Point[pointsCount];

for (int i = 0; i < pointsCount; i++) {

int x = in.readInt();

int y = in.readInt();

points[i] = new Point(x, y);

points[i].draw();

}

// Go each point p.

for (int p = 0; p < pointsCount; p++) {

// Sort the points according to the slopes they makes with p.

sort(points, points[p].SLOPE_ORDER);

// Check if any 3 (or more) adjacent points in the sorted order have equal slopes with respect to p

ArrayList<Point> collinearPoints = new ArrayList<Point>(pointsCount);

for (int q = 0; q < pointsCount - 1; q++) {

if (p == q) {

continue;

}

if (collinearPoints.isEmpty()) {

collinearPoints.add(points[q]);

} else if (points[p].slopeTo(points[q - 1]) == points[p].slopeTo(points[q])) {

collinearPoints.add(points[q]);

} else if (collinearPoints.size() > 2) {

// Draw collinear points.

collinearPoints.add(points[p]);

Collections.sort(collinearPoints);

// Display collinear points.

for (int i = 0; i < 3; i++) {

StdOut.print(collinearPoints.get(i));

StdOut.print(" -> ");

}

StdOut.println(Collections.max(collinearPoints));

Collections.min(collinearPoints).drawTo(Collections.max(collinearPoints));

break;

} else {

collinearPoints.clear();

collinearPoints.add(points[q]);

}

/***********************************************************************

* Bottom-Up merge sorting functions

***********************************************************************/

// stably merge a[lo..m] with a[m+1..hi] using aux[lo..hi]

private static void merge(Point[] a, Point[] aux, int lo, int m, int hi, Comparator<Point> comparator) {

// copy to aux[]

for (int k = lo; k <= hi; k++) {

aux[k] = a[k];

}

// merge back to a[]

int i = lo, j = m+1;

for (int k = lo; k <= hi; k++) {

if (i > m) a[k] = aux[j++];

else if (j > hi) a[k] = aux[i++];

else if (less(comparator, aux[j], aux[i])) a[k] = aux[j++];

else a[k] = aux[i++];

}

// bottom-up mergesort

public static void sort(Point[] a, Comparator<Point> comparator) {

int N = a.length;

Point[] aux = new Point[N];

for (int n = 1; n < N; n = n+n) {

for (int i = 0; i < N-n; i += n+n) {

int lo = i;

int m = i+n-1;

int hi = Math.min(i+n+n-1, N-1);

merge(a, aux, lo, m, hi, comparator);

}

// is v < w ?

private static boolean less(Comparator<Point> comparator, Point v, Point w) {

return comparator.compare(v, w) < 0;

}

Brute Force
public static void main(String[] args) {
// Rescale the coordinate system.
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
// Read points from the input file.
In in = new In(args[0]);
int pointsCount = in.readInt();
Point[] points = new Point[pointsCount];
for (int i = 0; i < pointsCount; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
points[i].draw();
}
// Go each 4 points and check whether they all lie on the same line segment.
for (int p = 0; p < pointsCount; p++) {
for (int q = p + 1; q < pointsCount; q++) {
double slopeToQ = points[p].slopeTo(points[q]);
for (int r = q + 1; r < pointsCount; r++) {
double slopeToR = points[p].slopeTo(points[r]);
if (slopeToQ == slopeToR) {
for (int s = r + 1; s < pointsCount; s++) {
double slopeToS = points[p].slopeTo(points[s]);
if (slopeToQ == slopeToS) {
// Create the list of collinear points and sort them.
List<Point> collinearPoints = new ArrayList<Point>(4);
collinearPoints.add(points[p]);
collinearPoints.add(points[q]);
collinearPoints.add(points[r]);
collinearPoints.add(points[s]);
Collections.sort(collinearPoints);
// Display collinear points.
for (int i = 0; i < 3; i++) {
StdOut.print(collinearPoints.get(i));
StdOut.print(" -> ");
}
StdOut.println(Collections.max(collinearPoints));
Collections.min(collinearPoints).drawTo(Collections.max(collinearPoints));
}
}
}
}
}
}
}

public class Point implements Comparable<Point> {

// compare points by slope
public final Comparator<Point> SLOPE_ORDER = new Comparator<Point>() {
public int compare(Point o1, Point o2) {
double slope1 = slopeTo(o1);
double slope2 = slopeTo(o2);
if (slope1 == slope2) {
return 0;
}
if (slope1 < slope2) {
return -1;
}
return 1;
}
};

private final int x; // x coordinate
private final int y; // y coordinate

// create the point (x, y)
public Point(int x, int y) {
/* DO NOT MODIFY */
this.x = x;
this.y = y;
}

// plot this point to standard drawing
public void draw() {
/* DO NOT MODIFY */
StdDraw.point(x, y);
}

// draw line between this point and that point to standard drawing
public void drawTo(Point that) {
/* DO NOT MODIFY */
StdDraw.line(this.x, this.y, that.x, that.y);
}

// slope between this point and that point
public double slopeTo(Point that) {
if (that == null) {
throw new NullPointerException();
}
if (that.x == x) {
if (that.y == y) {
return Double.NEGATIVE_INFINITY;
}
return Double.POSITIVE_INFINITY;
}
if (that.y == y) {
return 0.0;
}
return (double) (that.y - this.y) / (that.x - this.x);
}

// is this point lexicographically smaller than that one?
// comparing y-coordinates and breaking ties by x-coordinates
public int compareTo(Point that) {
if (y == that.y && x == that.x) {
return 0;
}
if (y < that.y || (y == that.y && x < that.x)) {
return -1;
}
return 1;
}

// return string representation of this point
public String toString() {
/* DO NOT MODIFY */
return "(" + x + ", " + y + ")";
}
}
http://blog.csdn.net/liuweiran900217/article/details/19285111

slopeTo类相当于来计算两点间连线的斜率了。初中数学我们就知道，有如下几种情况。

（1）两个点的y坐标相同，即连线与x轴平行。这种情况的斜率为0。但是我们要注意一个问题，在Java中实际上有两种0，即+0和-0，并且Java内置的比较函数认为+0>-0。这是怎么来的呢？在题目的CheckList中已经给出了相关的介绍，我们放在这里供大家参考：

What does it mean for slopeTo() to return positive zero?Java (and the IEEE 754 floating-point standard) define two representations of zero: negative zero and positive zero.

double a = 1.0;
double x = (a - a) /  a;   // positive zero ( 0.0)
double y = (a - a) / -a;   // negative zero (-0.0)

Note that while (x == y) is guaranteed to be true,Arrays.sort() treatsnegative zero as strictly less than positive zero.Thus, to make the specification precise, we require you to return positive zero for horizontal line segments.Unless your program casts to the wrapper type Double (either explicitly or via autoboxing),you probably will not notice any difference in behavior;but, if your program does cast to the wrapper type and fails only on (some) horizontal line segments, this may bethe cause.

（2）两个点的x坐标相同，即连线与y轴平行。根据题目要求，我们要把这种斜率定义为正无穷大。在Java中，Double类给出了双精度浮点数正无穷大的表示，为Double.POSITIVE_INFINITY，因此用这个值代表正无穷大即可。

（3）两个点相同。这是一个极为特殊的情况，在CheckList中也有过说明，内容如下：

Can the same point appear more than once as input to Brute or Fast?You may assume the input to Bruteand Fast are N distinct points.Nevertheless, the methods implemented as part of the Point data typemust correctly handle the case when the points are not distinct:for the slopeTo() method, this requirement is explicitly stated in the API;for the comparison methods, this requirement is implict in the contracts for Comparable andComparator.

对于这种情况，我的处理方法是将其结果设置为负无穷大，即Double.NEGATIVE_INFINITY。

（4）其他一般情况。这种情况下，我们直接计算斜率即可，计算公式很简单，为：(y_1 - y_0) / (x_1 - x_0)。不过注意到点的坐标表示是int，斜率为double，因此我们还需要一个强制转换来保证计算的精度。

compareTo()

这个类的实现也很容易，直接按照题目要求来实现即可。当y_0 < y_1或者当y_0 = y_1且x_0 < x_1时，返回-1。

SLOPE_ORDER

这个类的实现也很容易，分别计算两个点对于第三个点的斜率（调用slopeTo()），然后返回两个结果的比较值即可。因为在slopeTo()中我们已经处理过了3种特殊的情况，因此直接返回比较值就是正确的结果。

 private static void FastMethod(Point[] pointArray){
  int N = pointArray.length;
  for (int i=0; i<N; i++){
   Point origPoint = pointArray[i];
   Point[] otherPoint = new Point[N-1];
   for (int j=0; j<pointArray.length; j++){
    if (j < i) otherPoint[j] = pointArray[j];
    if (j > i) otherPoint[j-1] = pointArray[j];
   }
   Arrays.sort(otherPoint, origPoint.SLOPE_ORDER);
   
   int count = 0;
   int index = 0;
   double tempSlope = origPoint.slopeTo(otherPoint[0]);
   for (int j=0; j<otherPoint.length;j++){
    if (Double.compare(origPoint.slopeTo(otherPoint[j]),  tempSlope) == 0){
     count++;
     continue;
    }else{
     if (count >=3){
      if (otherPoint[index].compareTo(origPoint) >=0){
       StdOut.print(origPoint + " -> ");
       for (int k=index; k<j-1; k++){
        StdOut.print(otherPoint[k] + " -> ");
       }
       StdOut.println(otherPoint[j-1]);
       origPoint.drawTo(otherPoint[j-1]);
      }
     }
     count = 1;
     index = j;
     tempSlope = origPoint.slopeTo(otherPoint[j]);
    }
   }
   if (count >= 3){
    if (otherPoint[index].compareTo(origPoint) >= 0){
     StdOut.print(origPoint + " -> ");
     for (int k=index; k<otherPoint.length - 1; k++){
      StdOut.print(otherPoint[k] + " -> ");
     }
     StdOut.println(otherPoint[otherPoint.length-1]);
     origPoint.drawTo(otherPoint[otherPoint.length-1]);
    }
   }
  }
  StdDraw.show(0);
 }

https://segmentfault.com/a/1190000005345079

作业说明中对核心算法的描述非常清晰，应当特别小心的技术点（浮点误差、正负零等等）也都在checklist中予以强调，因而实现难度不算很大，其中使用了Java的Comparable与Comparator，排序过程调用Arrays.sort()，详细思考问题理清关系后，实现非常自然，前提是编程基本功必须扎实。
值得提到的点：

checklist鼓励初学者开始编写快速算法时先不要担心5个或以上的点共线的情况，而实际上对基本功扎实的同学，从开始便考虑这个问题更为合适；
checklist提到compare()和FastCollinearPoints类可以完全避免浮点数用整形运算实现，我想到的唯一符合要求（Point.java注释中规定不得依赖toString()）的方法是，对Point类的compareTo()方法返回值增加意义（不单纯返回正负1），以获取两点的坐标之差（因题目给定坐标取值范围0-32767，可在返回值低两位字节存储x坐标差，高两位字节存储y坐标差），再利用坐标差判断斜率是否相等。虽依然完全符合题目要求，但已有一点奇技淫巧之嫌，并且不一定能够通过autograder（评分时会替换Point类去测试FastCollinearPoints），不多讨论。（更新：此方法已确定违反FastCollinearPoints的API。）

Kd-Trees - Princeton Programming Assignment 5

8 Puzzle - Princeton Programming Assignment 4

Princeton Programming Assignment 3: Pattern Recognition

compareTo()

SLOPE_ORDER

Labels

Popular Posts

insert (0.7, 0.2)	insert (0.5, 0.4)	insert (0.2, 0.3)	insert (0.4, 0.7)	insert (0.9, 0.6)