A knight moves on a chessboard two squares up, down, left, or right followed by one square in one of the two directions perpendicular to the first part of the move (i.e., the move is L-shaped). Suppose the knight is on an unbounded board at square (0,0) and we wish to move it to square (x,y) in the smallest number of moves. (For example, to move from (0,0) to (1,1) requires two moves. The knight can move to board locations with negative coordinates.)
1.Explain how to decide whether the required number of moves is even or odd without constructing a solution.2.Design an admissible heuristic function for estimating the minimum number of moves required; it should be as accurate as you can make it. Prove rigorously that your heuristic is admissible.
3.Implement A* and use it to solve the problem using your heuristic. Create two scatter plots showing (a) the number of nodes expanded as a function of solution length, and (b) computation time as a function of solution length for a set of randomly generated problem instances.
思路分析：这是一道AI作业题，主要考察A*算法的实现。下面给出的A*实现用到的启发函数是generated node到目的地的Manhattan 距离的三分之一，，因为爵士走日字形，最多跳跃距离不会超过3格，这是一个可接受的启发函数。实现主要是BFS，需要借助队列实现。
实现Code
import java.util.Comparator;import java.util.PriorityQueue;/** * Find the minimum number of moves of knight from * (0,0) to (x,y) * @author Liu Yang & Wei Hong * @mail lyang@cs.umass.edu & hwberg@gmail.com */public class ChessboardSearchAstar {static int[][] actionCosts = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1},{1, 2}, {1, -2}, {-1, 2}, {-1, -2}};private Node startNode;private Node goalNode;int MAX_X = 1999;int MAX_Y = 1999;int MIN_X = -2000;int MIN_Y = -2000;int visitedFlagOffset = 2000; // x + visitedFlagOffset = index of x in visitedFlagstatic int generatedNodeCount;static int expandedNodeCount;private enum flagType{INIT, VISITED;}private static flagType[][] visitedFlag;public int getVisitedFlagOffset() {return visitedFlagOffset;}public void setVisitedFlagOffset(int visitedFlagOffset) {this.visitedFlagOffset = visitedFlagOffset;}public Node getStartNode() {return startNode;}public void setStartNode(Node startNode) {this.startNode = startNode;}public Node getGoalNode() {return goalNode;}public void setGoalNode(Node goalNode) {this.goalNode = goalNode;}//return -1 when there is no solution or illegal inputpublic int astarSearch(){if(startNode.getX() == goalNode.getX() && startNode.getY() == goalNode.getY()){return 0;}//since the startNode is fixed, only need to check goalNodeif(!(goalNode.getX() >= MIN_X && goalNode.getX() <= MAX_X) || !(goalNode.getY() >= MIN_Y && goalNode.getY() <= MAX_Y)){System.err.println("illegal input!");return -1;}Comparator<Node> comparator = new Comparator<Node>() {@Overridepublic int compare(Node n1, Node n2) {// TODO Auto-generated method stubif(n1.getFValue(goalNode) > n2.getFValue(goalNode)){return 1;} else if(n1.getFValue(goalNode) == n2.getFValue(goalNode)){return 0;}return -1;}};PriorityQueue<Node> pQueue = new PriorityQueue<Node>(2, comparator);//init visitedFlagvisitedFlag = new flagType[MAX_X – MIN_X + 1][MAX_Y – MIN_Y + 1];for(int i = 0; i < visitedFlag.length; i++){for(int j = 0; j < visitedFlag[i].length; j++){visitedFlag[i][j] = flagType.INIT;}}generatedNodeCount = 1;expandedNodeCount = 0;Node currentNode = new Node(startNode);startNode.setG(0);startNode.setStepCount(0);startNode.setParentNode(null);pQueue.add(startNode);visitedFlag[startNode.getX() + visitedFlagOffset][startNode.getY() + visitedFlagOffset] = flagType.VISITED;while(pQueue.size() != 0 ){pQueue.poll();expandedNodeCount++;visitedFlag[currentNode.getX() + visitedFlagOffset][currentNode.getY() + visitedFlagOffset] = flagType.VISITED;for(int i = 0; i < actionCosts.length; i++){Node childNode = new Node(currentNode.getX() + actionCosts[i][0], currentNode.getY() + actionCosts[i][1]);if((childNode.getX() >= MIN_X) && (childNode.getX() <= MAX_X) && (childNode.getY() >= MIN_Y) && (childNode.getY() <= MAX_Y) &&visitedFlag[childNode.getX() + visitedFlagOffset][childNode.getY() + visitedFlagOffset] == flagType.INIT ){generatedNodeCount++;childNode.setParentNode(currentNode);childNode.setG(currentNode.getG() + 1);childNode.setStepCount(currentNode.getStepCount() + 1);pQueue.add(childNode);visitedFlag[childNode.getX() + visitedFlagOffset][childNode.getY() + visitedFlagOffset] = flagType.VISITED;}}currentNode = pQueue.peek();if(currentNode.getX() == goalNode.getX() && currentNode.getY() == goalNode.getY()){return currentNode.stepCount;}}System.out.println("There is no solution for the input!");return -1;}/** * @param for testing */public static void main(String[] args) {// TODO Auto-generated method stubChessboardSearchAstar chessSearch = new ChessboardSearchAstar();chessSearch.setStartNode(new Node(0,0));chessSearch.setGoalNode(new Node(1,1));//tracking the computation timelong startTime = System.currentTimeMillis();System.out.println("the minimum number of moves of knight is " + chessSearch.astarSearch());long endTime = System.currentTimeMillis();System.out.println("The computation time is " + (endTime – startTime) + "ms");System.out.println("expandedNodeCount: " + expandedNodeCount + " " + "generatedNodeCount: " + generatedNodeCount);}static class Node {Node parentNode;int x, y; //coordinatesint g; //current costint stepCount;//count of steppublic Node(int i, int j) {// TODO Auto-generated constructor stubthis.x = i;this.y = j;}public Node(Node startNode) {// TODO Auto-generated constructor stubthis.x = startNode.x;this.y = startNode.y;}public Node() {// TODO Auto-generated constructor stub}public int getStepCount() {return stepCount;}public void setStepCount(int stepCount) {this.stepCount = stepCount;}public Node getParentNode() {return parentNode;}public void setParentNode(Node parentNode) {this.parentNode = parentNode;}public int getX() {return x;}public void setX(int x) {this.x = x;}public int getY() {return y;}public void setY(int y) {this.y = y;}public int getG() {return g;}public void setG(int g) {this.g = g;}public int getFValue(Node goalNode){return g + getHValue(goalNode);}public int getHValue(Node goalNode){return (Math.abs(x – goalNode.x) + Math.abs(y – goalNode.y)) / 3;}}}
大多数人想要改造这个世界，但却罕有人想改造自己。
