我如何找到矩陣中最接近A的路徑？

例如：我如何找到矩陣中最接近A的路徑？

m_array = new int[6][6]; m_array[0] = new int[]{2, 0, 0, 0, 0, 0}; m_array[1] = new int[]{0, 2, 0, 0, 0, 2}; m_array[2] = new int[]{2, 0, 0, 1, 0, 0}; m_array[3] = new int[]{0, 0, 0, 0, 0, 0}; m_array[4] = new int[]{0, 2, 0, 0, 2, 0}; m_array[5] = new int[]{0, 0, 2, 0, 0, 0};

我怎麼能找到最接近的2比1？

我想要一個函數，它返回的數組路徑包括數組的點。例如，我會給我的函數「m_array」，它會返回給我1最接近的2，像[2,3] [3,4] [4,4]

來源

2012-06-22 MarsPeople

什麼？我無法理解你想要什麼 – simchona

我的英語很差。我只想找到最接近的2的座標爲1. – MarsPeople

你可能舉一個你要找的答案的例子嗎？ – simchona

這些都是你給我們留下猜測的事情：

只有一個1，但很多2的;
該路徑允許對角線步驟;
您正在尋找連接1與2的所有路徑中最短的路徑。

我目前的想法是，有一個度量可以爲任意兩點之間的路徑長度定義，所以概念「a 2的最短路徑爲1」等價於「最接近2的概念到1「。該指標可以被定義爲「環」圍繞中心1一把手必須穿過去一個2：

0 0 0 
0 1 0 
0 0 2 --> the 2 is in the first ring 

0 0 0 0 0 
0 0 0 0 0 
0 0 1 0 0 
0 0 0 0 0 
0 2 0 0 0 --> the 2 is in the second ring.

如果我所有的假設是正確的，那麼你需要一個功能，讓所有成員第一個環，第二個環等等，另一個函數會搜索一個環2.然後，最後，你需要一個算法來繪製一條2的路徑。我希望你意識到路徑不是唯一的。一個簡單的算法將對角移動，直到與2對齊（水平或垂直），然後非對角地繼續到目標。

來源

2012-06-22 14:30:17

不錯的建議。事實上，我正在努力做到這一點（戒指）。但有一個問題，我會給我的陣列設置障礙。（0 =自由，1 =開始點，2 =任何終點，3 =屏障）當我放置屏障（在我的數組3中）時，我認爲環形射線不能正常工作？ – MarsPeople

它當然不會。在這種情況下，根本就沒有解決辦法。爲了解決這個問題，您需要將網格轉換爲圖形並使用最短路徑算法（例如Dijkstra's）進行求解。 –

我解決了我的問題，像你的「成長戒指」。我用A *算法解決了屏障問題。完成後我會粘貼我的代碼。 – MarsPeople

數組路徑不確定你這意味着你似乎在問兩個不同的事情。我不能真正幫助你的路徑，因爲你沒有詳細說明我們如何移動的標準。您似乎也在問如何找到最接近的2。儘管不是最有效的，但您可以簡單地遍歷矩陣並使用Pythagoras'根據索引計算每個2到1的距離。或者，您可以從矩陣1開始，向外遍歷矩形。這可能會更快，因爲你會停止第二次找到2，而不是必須遍歷整個矩陣檢查2秒的第一個解決方案，儘管第一個解決方案更容易實現，不應該有太大的區別，因爲你的矩陣很小（兩者都是O（n），我相信，但第二種方法最好的情況是你可以在第一次檢查時找到2，而在使用畢達哥拉斯時你總是需要遍歷整個矩陣）。

我希望這是有道理的。

一些澄清後編輯：這裏是我希望滿足您的要求的方法。首先是一個課程來包裝點以方便訪問。

public class Point { 
    private int x, y; 
    public Point(int x, int y) { 
     this.x = x; 
     this.y = y; 
    } 

    public int getX() { return x; } 
    public int getY() { return y; } 
    public int setX(int x) { this.x = x; } 
    public int setY(int y) { this.y = y; } 

}

現在的方法本身：

public ArrayList<Point> getPath(int[][] matrix) { 
    Point closestTwo = getClosestTwo(matrix); // Implement this as you wish 
    Point onePosition = getOnePosition(matrix); 

    ArrayList<Point> pointList = new ArrayList<Point>(); 

    Point currentlyOn = onePosition; 

    while (currentlyOn.getX() != closestTwo.getX() && currentlyOn.getY() != closestTwo.getY()) { 
     currentlyOn = oneStep(currentlyOn, closestTwo); 
     pointList.add(currentlyOn); 
    } 

    return pointList; 
}

這裏，你可以用更貼近一步式方法的一個例子。它會返回一個點，它將最大限度地提升你，而只做一步（對角線優先）。

public Point oneStep(Point from, Point goal) { 
    int x = from.getX() - goal.getX(); 
    int y = from.getY() - goal.getY(); 
    Point nextStep = new Point (from.getX(), from.getY()); 

    if (x > 0) { 
     nextStep.setX(nextStep.getX() + 1) 
    } else if (x < 0) { 
     nextStep.setX(nextStep.getX() - 1) 
    } 

    if (y > 0) { 
     nextStep.setY(nextStep.getY() + 1) 
    } else if (y < 0) { 
     nextStep.setY(nextStep.getY() - 1) 
    } 

    return nextStep; 
}

我相信這應該可以正常工作。如果你使用這個，你應該得到一個Point的ArrayList。 getClosestTwo方法的一個例子可能是這樣的（使用Pythagoras'）。記住導入java.lang.Math;

public Point getClosestTwo(int[][] matrix) { // Assumes matrix is initialized, non-empty etc. 
    int x, y; 
    double smallestDistance = matrix.size() * matrix[0].size(); // bigger than possible 
    Point onePosition = getOnePosition(matrix); 

    for (int i = 0; i < matrix.size(); i++) { 
     for (int j = 0; j < matrix[0].size(); j++) { 
      double tmp = (double)(Math.abs(i - y) + Math.abs(j - x)) 
      double distance = Math.sqrt(tmp); 
      if (distance < smallestDistance) { 
       y = i; 
       x = j; 
       smallestDistance = distance; 
      } 
     } 
    } 

    return new Point(x, y); 
}

getOnePosition（INT [] []矩陣）可以被簡單地實現像這樣：

// Return null if no 1 in matrix 
public Point getOnePosition(int[][] matrix) { 
    for (int i = 0; i < matrix.size(); i++) { 
     for (int j = 0; j < matrix[0].size(); j++) { 
      if (matrix[i][j] == 1) { 
       return new Point(j, i); 
      } 
     } 
    } 
    return null; 
}

希望這有助於。請記住檢查是否存在空值，編寫安全代碼等。您可以將它們放在一起。我希望這段代碼沒有任何錯別字或錯誤，您將無法修復。

來源

2012-06-22 13:20:59

是不是清楚我的問題？（我的英文很差）：/ 我不能使用畢達哥拉斯，因爲我在矩陣數組中。對於「m_array」，我想要一個函數，它返回的數組路徑包括數組的點。例如，我給我的函數「m_array」，它返回給我最接近2的1，數組路徑像[2,3] [3,4] [4,4] – MarsPeople

好吧，看看你的問題後5分鐘試圖理解你的意思，這裏是我認爲你的意思：你有一個矩陣只有一個'1'。你想找到最接近的'2'。然後，您想要獲得從前面找到的最近的'1'到最接近的'2'的最短路徑。你仍然可以使用畢達哥拉斯找到最接近2.我的答案，但是，並不包括如何從2路到1 ，我可以看到你考慮到對角線移動是允許的。在這種情況下，考慮制定一種算法，直到你的目標爲止，然後直接進入對角線。我會編輯我的答案。 –

謝謝你的回覆。實際上，我沒有正確使用這個算法。我用「成長環」解決了我的問題。完成後，我會將我的代碼粘貼到此處。再次感謝您的幫助。 – MarsPeople

該函數將我的矩陣數組拼接爲環半徑。

public static int[][] SpliceMatrix(int orginX, int orginY, int ringRadius, int[][] map){ 

    int[][] tempMap = new int[ringRadius * 2 + 1][ringRadius * 2 + 1]; 

    int tempY = -ringRadius; 
    for(int i = 0; i < (ringRadius * 2 + 1); i++){ 
     int tempX = -ringRadius; 

     for(int j = 0; j < (ringRadius * 2 + 1); j++){ 
      try{ 
       tempMap[i][j] = map[orginY + tempY][orginX + tempX]; 
      }catch(ArrayIndexOutOfBoundsException e){ 
       tempMap[i][j] = 1; 
      } 

      tempX++; 
     } 

     tempY++; 
    } 

    return tempMap; 
}

我用A * algoritm在這個函數：

private static Point findNext2(int orginX, int orginY, int[][] map){ 

    //Find "2"s 
    ArrayList<Point> ends = new ArrayList<Point>(); 

    for(int i = 0; i < map.length; i++){ 
     for(int j = 0; j < map[0].length; j++){ 
      if(map[i][j] == 2){ 
       ends.add(new Point(j, i)); 

       map[i][j] = 0;//Clear for A* 
      } 
     } 
    } 

    //Find the closest 
    if(ends.size() > 0){ 
     Point p = null; 
     int distance = 100; 

     for(int i = 0; i < ends.size(); i++){ 
      int tempDistance = APlus.go(orginX, orginY, ends.get(i).x, ends.get(i).y, map).size(); 
      System.out.println(tempDistance); 
      if(tempDistance != 0 && tempDistance < distance){ 
       distance = tempDistance; 
       p = new Point(ends.get(i).x, ends.get(i).y); 
      } 

     } 

     if(p == null){ 
      System.out.println("2 is not accesible"); 

      return null; 
     } 

     return p; 

    }else{ 
     System.out.println("There is no 2 in ring"); 

     return null; 
    } 

}

然後我用

public static void main(String args[]){ 

    int[][] m_array = new int[6][6]; 
    m_array[0] = new int[]{1, 1, 0, 0, 2, 0}; 
    m_array[1] = new int[]{0, 0, 0, 0, 0, 1}; 
    m_array[2] = new int[]{1, 1, 1, 0, 1, 0}; 
    m_array[3] = new int[]{1, 0, 1, 0, 1, 0}; 
    m_array[4] = new int[]{0, 0, 0, 0, 1, 0}; 
    m_array[5] = new int[]{0, 0, 0, 0, 0, 0}; 

    int[][] c = SpliceMatrix(2, 2, 2, m_array);//int x, int y, ringRadius, matrix 

    Point p = findNext2(3, 3, c);//orginX, orginY, matrix 
    System.out.println(p + " is the closest 2"); 
}

我希望這是描述性的。我無法正確使用HTML。

來源

2012-06-25 06:50:09 MarsPeople

我更喜歡使用quickgraph查找更近的點或路徑; 所以，請看這個鏈接： http://www.codeproject.com/Articles/5603/QuickGraph-A-100-C-graph-library-with-Graphviz-Sup

來源

2012-06-25 07:13:39

這是我的一段代碼。似乎比任何我在這裏看到這麼決定後的方式簡單：

public static boolean isWithinRadius(int[] position, int[] centerPosition, int radius) { 

     int xCenterPoint = centerPosition[0]; 
     int yCenterPoint = centerPosition[1]; 
     int zCenterPoint = centerPosition[2]; 


     int xPoint = position[0]; 
     int yPoint = position[1]; 
     int zPoint = position[2]; 

     boolean xMatch = (xPoint - radius <= xCenterPoint) && (xPoint >= xCenterPoint - radius); 
     boolean yMatch = (yPoint - radius <= yCenterPoint) && (yPoint >= yCenterPoint - radius); 
     boolean zMatch = (zPoint - radius <= zCenterPoint) && (zPoint >= zCenterPoint - radius); 


     return xMatch && yMatch && zMatch; 

    } // public boolean isWithinRadius (int[], int)

如果位置是centerPosition的半徑範圍內這將返回true。

centerPosition是環的中心。（如果您不需要Z值，只需在要求的地方放0）。
半徑1 ==環1，半徑2 ==環1 &環2等。您可以掃描半徑。試着建立在這個基礎上。如果您有興趣，我已經編寫了一個高級矩陣類，您可以掃描（基於散列）並查找其中的對象。我正要編寫返回在半徑內找到的對象的ArrayList的代碼。

如果你希望只在特定的環（而不是半徑範圍內的所有對象）使用此代碼中找到對象：

public static boolean isWithinRadiusRing(int[] position, int[] centerPosition, int radius) { 


     int xCenterPoint = centerPosition[0]; 
     int yCenterPoint = centerPosition[1]; 
     int zCenterPoint = centerPosition[2]; 


     int xPoint = position[0]; 
     int yPoint = position[1]; 
     int zPoint = position[2]; 

     boolean xRingMatch = (xPoint - radius == xCenterPoint) || (xPoint == xCenterPoint - radius); 
     boolean yRingMatch = (yPoint - radius == yCenterPoint) || (yPoint == yCenterPoint - radius); 
     boolean zRingMatch = (zPoint - radius == zCenterPoint) || (zPoint == zCenterPoint - radius); 

     boolean xRadiusMatch = (xPoint - radius <= xCenterPoint) && (xPoint >= xCenterPoint - radius); 
     boolean yRadiusMatch = (yPoint - radius <= yCenterPoint) && (yPoint >= yCenterPoint - radius); 
     boolean zRadiusMatch = (zPoint - radius <= zCenterPoint) && (zPoint >= zCenterPoint - radius); 

     boolean xMatch = xRingMatch && yRadiusMatch && zRadiusMatch; 
     boolean yMatch = yRingMatch && xRadiusMatch && zRadiusMatch; 
     boolean zMatch = zRingMatch && xRadiusMatch && yRadiusMatch; 

     /* 
      System.out.println("xRingMatch="+xRingMatch+" yRingMatch="+yRingMatch+" zRingMatch="+zRingMatch); 
      System.out.println("xRadiusMatch="+xRadiusMatch+" yRadiusMatch="+yRadiusMatch+" zRadiusMatch="+zRadiusMatch); 
      System.out.println("xMatch="+xMatch+" yMatch="+yMatch+" zMatch=" +zMatch); 
      System.out.println("return=" + (xMatch || yMatch || zMatch)); 
     */ 

     return xMatch || yMatch || zMatch; 

    } // public boolean isWithinRadiusRing(int[], int[] , int)

這將返回true如果給定位置是給定的半徑內從centerPosition環（半徑1 == RING1，半徑2 ==環2等）

爲了找出半徑距離的兩個位置之間：

 public static int getDistanceRadius(int[] startPosition, int[] endPosition) { 

      // The xyz value that streches the most the distance between two positions 
      // is the radius value. 
      int xDistance = Math.abs(startPosition[0] - endPosition[0]); 
      int yDistance = Math.abs(startPosition[1] - endPosition[1]); 
      int zDistance = Math.abs(startPosition[2] - endPosition[2]); 

      int radius = (xDistance > yDistance ? xDistance : yDistance);   
      radius = (radius > zDistance ? radius : zDistance); 

      return radius; 

     } // public static int getDistanceRadius(int[], int[])

來源

2015-04-27 19:40:24 SKYFALL26

我如何找到矩陣中最接近A的路徑？

回答

相關問題