가중치가없는 표에서 A에서 B 방향으로 최단 경로를 찾으려면 어떤 알고리즘을 사용해야합니까?

Question

시나리오는 플레이어가 소스 위치 A에서 B 위치로 이동해야하지만 최대량 만 이동할 수있는 턴 기반 상황입니다.

예를 들어, B는 A에서 24 단위 거리 (BFS를 사용하여 계산 됨)이며 12 점을 굴 렸습니다. B 방향으로 12 운동 단위 거리 밖에 떨어져 있지 않은 경로를 어떻게 찾을 수 있습니까?

참고 :

이

• 가 이동할 수 없습니다 대각선
• 큰 장애물
이 있습니다

편집 :이 단서/클루 유사한 게임이지만, 텍스트 전용 그렇다 플레이어는 '앞으로'움직일 방향을 선택합니다. 여기

내가 뭘하려 :

예 그리드 :

○○○○○○○○○○ 
○○○○○○○○◘◘ 
○○○◘◘◘○○◘◘ 
○○○◘◘◘○○B◘ 
○A○◘◘◘○○◘◘ 

알고리즘 (◘ 장애물이다, ○는 없습니다) :

if paces == 0, return 
try moving col closer to dest.col: 
    if col == dest.col, move row closer to dest.row 
    else if adjacent is blocked, move row away from start 

이를 제외하고, 종이에 괜찮 작동 내가 구석에 뛰어 들면 :

○A→◘◘○○◘◘◘ 
○○↓◘◘○○B◘◘ 
○○↓◘◘○○◘◘◘ 
○○↓◘◘○○↑◘◘ 
○○↓→→→→→◘◘ 

솔루션 :

public ArrayList<Location> shortestPath(final Location start, final Location dest) { 
    HashSet<Location> visits = new HashSet<>(); 
    HashMap<Location, Location> links = new HashMap<>(); 

    PriorityQueue<Location> queue = new PriorityQueue<>(Board.GRID_COLS * Board.GRID_ROWS, 
      new Comparator<Location>() { 

       @Override 
       public int compare(Location a, Location b) { 
        return Integer.compare(getHeuristic(a, dest), getHeuristic(b, dest)); 
       } 
      }); 

    queue.add(start); 

    while (!queue.isEmpty()) { 
     Location current = queue.remove(); 
     if (current.equals(dest)) { 
      ArrayList<Location> path = reconstruct(current, new LinkedList<Location>(), links); 
      path.add(dest); 
      return path; 
     } 

     visits.add(current); 
     for (Location neighbour : getNeighbours(current)) { 
      if (!visits.contains(neighbour)) { 
       queue.add(neighbour); 
       visits.add(neighbour); 
       links.put(neighbour, current); 
      } 
     } 

    } 
    return null; // failed 
} 

// Manhattan distance 
private int getHeuristic(Location src, Location dest) { 
    return Math.abs(dest.row - src.row) + Math.abs(dest.col - src.col); 
} 

private ArrayList<Location> reconstruct(Location current, LinkedList<Location> list, HashMap<Location, Location> links) { 
    if (links.containsKey(current)) { 
     list.addFirst(links.get(current)); 
     return reconstruct(links.get(current), list, links); 
    } else { 
     return new ArrayList<>(list); 
    } 
} 

private ArrayList<Location> getNeighbours(Location current) { 
    ArrayList<Location> neighbours = new ArrayList<>(); 

    if (current.row < GRID_ROWS - 1) { 
     Location n = LOCATIONS[current.row + 1][current.col]; 
     if (isAccessible(n, current)) neighbours.add(n); 
    } 
    if (current.row > 0) { 
     Location n = LOCATIONS[current.row - 1][current.col]; 
     if (isAccessible(n, current)) neighbours.add(n); 
    } 
    if (current.col < GRID_COLS - 1) { 
     Location n = LOCATIONS[current.row][current.col + 1]; 
     if (isAccessible(n, current)) neighbours.add(n); 
    } 
    if (current.col > 0) { 
     Location n = LOCATIONS[current.row][current.col - 1]; 
     if (isAccessible(n, current)) neighbours.add(n); 

    } 
    return neighbours; 
} 

Answer 1

는 A*을위한 완벽한 작업 같은 소리. 그래프에

, 그것은 기본적으로 그냥 같은 (알고리즘) 폭 우선 검색하지만, (f(x)으로 정렬) 우선 순위 - 큐 을 사용하는 등 오히려 큐 이상이어야합니다.

Answer 2

게임 보드의 왼쪽 상단 모서리는 좌표 (0, 0) 여야합니다. 하나의 경로 만 알고 싶은 경우를 대비하여 반환 된 경로를 선택할 수 있습니다. 경로가 시작점을 포함하기 때문에 최적의 단계는 경로 -1의 길이입니다. 다행히 그것이 당신을 도울 것입니다.

using System; 
using System.Collections.Generic; 
using System.Drawing; 

namespace Game 
{ 
    class Program 
    { 
     /// <summary> 
     /// Find a matrix with all possible optimum paths from point A to point B in the game board 
     /// </summary> 
     /// <param name="board">Game board</param> 
     /// <param name="moves">Allowed moves</param> 
     /// <param name="matrix">Resulting matrix</param> 
     /// <param name="A">Point A</param> 
     /// <param name="B">Point B</param> 
     private static void FindMatrix(List<List<char>> board, List<Point> moves, out List<List<int>> matrix, out Point A, out Point B) 
     { 
      matrix = new List<List<int>>(); 
      A = new Point(-1, -1); 
      B = new Point(-1, -1); 
      //Init values of the matrix 
      for (int row = 0; row < board.Count; row++) 
      { 
       matrix.Add(new List<int>()); 
       for (int col = 0; col < board[row].Count; col++) 
       { 
        matrix[matrix.Count - 1].Add(board[row][col] == '◘' ? -1 : 0); 
        switch (board[row][col]) 
        { 
         case 'A': 
          { 
           A.X = col; 
           A.Y = row; 
           matrix[row][col] = -1; 
           break; 
          } 
         case 'B': 
          { 
           B.X = col; 
           B.Y = row; 
           break; 
          } 
        } 
       } 
      } 
      if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist in the board 
      { 
       var pairs = new List<Point>[2] { new List<Point>(), new List<Point>() }; 
       int index = 0; 
       int level = 0; 
       pairs[index].Add(A); 
       while ((pairs[index].Count > 0) && (pairs[index][pairs[index].Count - 1] != B)) 
       { 
        pairs[Math.Abs(1 - index)].Clear(); 
        level++; 
        foreach (var pair in pairs[index]) 
         foreach (var move in moves) //Test all possible moves 
          if ((pair.Y + move.Y >= 0) && (pair.Y + move.Y < board.Count) && (pair.X + move.X >= 0) && (pair.X + move.X < board[pair.Y + move.Y].Count) && (matrix[pair.Y + move.Y][pair.X + move.X] == 0)) //Inside the board? Not visited before? 
          { 
           pairs[Math.Abs(1 - index)].Add(new Point(pair.X + move.X, pair.Y + move.Y)); 
           matrix[pair.Y + move.Y][pair.X + move.X] = level; 
          } 
        index = Math.Abs(1 - index); 
       } 
       matrix[A.Y][A.X] = 0; 
      } 
     } 

     /// <summary> 
     /// Finds all possible optimum paths from point A to point B in the game board matix 
     /// </summary> 
     /// <param name="matrix">Game board matrix</param> 
     /// <param name="moves">Allowed moves</param> 
     /// <param name="A">Point A</param> 
     /// <param name="B">Point B</param> 
     /// <param name="result">Resulting optimum paths</param> 
     /// <param name="list">Temporary single optimum path</param> 
     private static void WalkMatrix(List<List<int>> matrix, List<Point> moves, Point A, Point B, ref List<List<Point>> result, ref List<Point> list) 
     { 
      if ((list.Count > 0) && (list[list.Count - 1] == B)) //Stop condition 
      { 
       result.Add(new List<Point>(list)); 
      } 
      else 
      { 
       foreach (var move in moves) 
        if ((A.Y + move.Y >= 0) && (A.Y + move.Y < matrix.Count) && (A.X + move.X >= 0) && (A.X + move.X < matrix[A.Y + move.Y].Count) && (matrix[A.Y + move.Y][A.X + move.X] == matrix[A.Y][A.X] + 1)) //Inside the board? Next step? 
        { 
         list.Add(new Point(A.X + move.X, A.Y + move.Y)); //Store temporary cell 
         WalkMatrix(matrix, moves, list[list.Count - 1], B, ref result, ref list); 
         list.RemoveAt(list.Count - 1); //Clean temporary cell 
        } 
      } 
     } 

     /// <summary> 
     /// Finds all possible optimum paths from point A to point B in the game board 
     /// </summary> 
     /// <param name="board">Game board</param> 
     /// <returns>All possible optimum paths</returns> 
     public static List<List<Point>> FindPaths(List<List<char>> board) 
     { 
      var result = new List<List<Point>>(); 
      var moves = new List<Point> { new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1) }; //Right, Down, Left, Up (clockwise) 
      List<List<int>> matrix; //Matrix temporary representation of the game to store all possible optimum paths 
      Point A; 
      Point B; 
      FindMatrix(board, moves, out matrix, out A, out B); 
      if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist in the board 
      { 
       List<Point> list = new List<Point>(); 
       list.Add(A); 
       WalkMatrix(matrix, moves, A, B, ref result, ref list); 
      } 
      return result; 
     } 

     static void Main(string[] args) 
     { 
      List<List<char>> board = new List<List<char>> //An example of game board 
      { 
       new List<char>("○○○○○○○○○○"), 
       new List<char>("○○○○○○○○◘◘"), 
       new List<char>("○○○◘◘◘○○◘◘"), 
       new List<char>("○○○◘◘◘○○B◘"), 
       new List<char>("○A○◘◘◘○○◘◘") 
      }; 
      List<List<Point>> paths = FindPaths(board); 
     } 
    } 
}