AI：在曼哈頓啓發式圖搜索和A *實現

Question

This is my project在佛羅倫薩大學的AI課程。我必須解決一個經典的遊戲：滑動拼圖8和15單元格。 這是我實現一般圖搜索算法：

public abstract class GraphSearch implements SearchAlgorithm { 

protected Queue<Node> fringe; 
protected HashSet<Node> closedList; 

public GraphSearch() { 
    fringe = createFringe(); 
    closedList = new HashSet<Node>(100); 
} 

protected abstract Queue<Node> createFringe(); 

public int getNodeExpanded() { 
    return closedList.size(); 
} 

@Override 
public Solution search(Puzzle puzzle) { 
    fringe.add(new Node(puzzle.getInitialState(), null, null)); 
    while (!fringe.isEmpty()) { 
     Node selectedNode = fringe.poll(); 
     if (puzzle.getGoalTest().isGoalState(selectedNode.getState())) { 
      return new Solution(selectedNode, getNodeExpanded()); 
     } 
     closedList.add(selectedNode); 
     LinkedList<Node> expansion = selectedNode.expandNode(); 
     for (Node n : expansion) { 
      if (!closedList.contains(n) && !fringe.contains(n)) 
       fringe.add(n); 
     } 
    } 
    return new Solution(null, getNodeExpanded()); 
} 

} 

這是我的A *代碼：

public class AStar extends GraphSearch implements InformedSearch { 

private Heuristic heuristic; 

public AStar(Heuristic heuristic) { 
    setHeuristic(heuristic); 
} 

public Heuristic getHeuristic() { 
    return heuristic; 
} 

@Override 
public void setHeuristic(Heuristic heuristic) { 
    this.heuristic = heuristic; 
} 

@Override 
protected Queue<Node> createFringe() { 
    return new PriorityQueue<Node>(1000, new Comparator<Node>() { 

     @Override 
     public int compare(Node o1, Node o2) { 
      o1.setH(heuristic.h(o1)); 
      o2.setH(heuristic.h(o2)); 
      o1.setF(o1.getG() + o1.getH()); 
      o2.setF(o2.getG() + o2.getH()); 
      if (o1.getF() < o2.getF()) 
       return -1; 
      if (o1.getF() > o2.getF()) 
       return 1; 
      return 0; 
     } 
    }); 
} 

} 

這是我的曼哈頓啓發式代碼：

@Override 
public int h(Node n) { 
    int distance = 0; 
    ArrayList<Integer> board = n.getState().getBoard(); 
    int[][] multiBoard = new int[N][N]; 
    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < N; j++) { 
      multiBoard[i][j] = board.get(i * N + j); 
     } 
    } 
    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < N; j++) { 
      int value = multiBoard[i][j]; 
      if (multiBoard[i][j] != 0) { 
       int targetX = (value - 1)/N; 
       int targetY = (value - 1) % N; 
       distance += Math.abs(i - targetX) + Math.abs(j - targetY); 
      } 
     } 
    } 
    return distance; 
} 

現在，代碼的作品，並找到解決方案拼圖（拼圖狀態是一個N * N值的數組和目標狀態是[1,2,3,4,5,6,7,8,9，0]（對於N = 3）與空白cell = 0），但將結果與其他程序進行比較ams（相同的算法和相同的啓發式）我的程序擴展了不同數量的節點。我認爲在一般的圖形搜索中存在一個問題......任何想法？ ：D 謝謝！

Answer 1

您的啓發式計算是錯誤的。假設9位於董事會的索引4處。您將其rowRight值計算爲3而不是2.這將導致算法的超自適應性能。你的排右側計算應該是：

int rowRight = (valueFound - 1)/N;