MOST1障害物で克服する能力があれば、最短経路を最初から最後まで計算してください

Question

迷路は2次元の行列形式で与えられます。 0は無差別空間、1は壁です。

開始位置は常に

array[0][0]

になり、終了位置は常に

array[HEIGHT -1][WIDTH-1]

です。可能な移動は、上、下、右、または左です。 私は、迷路の中に最大で1つの壁を乗り越えることができると考えて、最初から最後まで最短経路を探したいと思います。私はMazeクラスとVertexクラスを作成することから始めました。私の最初の考えはBFSを使うことでしたが、私は最近これがうまくいかないことに気がつきました。私は今Dijkstraのアルゴリズムを試しています。アイデアは、無駄なスペースよりもはるかに高価なWallのウェイトを与え、Dijkstra'sを使用して最初から最後まで最短のパスを見つけることです。次に、Wallの最短パスを計算します。この後、私は壁のパスと終わりのパスを比較して、始まりのパスを最後にして、何とかこれを使って壁を取り除くと私に短いパスが与えられるかどうかを判断できると考えています。

私はDijkstraに本当に苦労しており、これらをまとめて何か役に立つものにしています。私はMazeクラスを作成することから始めました。これは2次元配列の入力を受け取り、そこからグラフを作成します。迷路クラス：

class Maze{ 
    Vertex[][] vertices; 
    ArrayList<Edge> edges; 
    ArrayList<Vertex> walls; 
    HashSet<Vertex> settledVertices; 
    HashSet<Vertex> unsettledVertices; 
    HashMap<Vertex,Integer> distanceMap; 
    HashMap<Vertex,Vertex> predecessors; 

    Vertex start, end; 
    int width; 
    int height; 

//Maze Contructor 
    public Maze(int arr[][]){ 
    this.height = arr.length; 
    this.width = arr[0].length; 
    this.vertices = new Vertex[height][width]; 
    this.edges = new ArrayList<>(); 
    this.walls = new ArrayList<>(); 

    for(int i = 0 ; i < height; i++){ 
     for(int j = 0; j < width; j++){ 
     this.vertices[i][j] = arr[i][j] == 1 ? new Wall(arr[i][j]) : new Vertex(arr[i][j]); 
     if(this.vertices[i][j].value == 1) 
      this.walls.add(this.vertices[i][j]); 
     } 
    } 

    //Build() sets the Edges and their weights, as well as determine each Vertexs neighbors 
    build(); 

    this.start = this.vertices[0][0]; 
    this.end = this.vertices[height-1][width-1]; 

    } 

    //Attempting Dijkstra 
    public void executeDij(Vertex source){ 
    this.settledVertices = new HashSet<>(); 
    this.unsettledVertices = new HashSet<>(); 
    this.distanceMap = new HashMap<>(); 
    this.predecessors = new HashMap<>(); 

    this.distanceMap.put(source,0); 
    this.unsettledVertices.add(source); 

    while(unsettledVertices.size() > 0){ 
     Vertex v = getMinimum(unsettledVertices); 
     unsettledVertices.remove(v); 
     findMinDistance(v); 
    } 
    } 


    public int getDistance(Vertex arrow, Vertex target){ 
     for(Edge e : edges) 
     if(e.source.equals(arrow) && e.destination.equals(target)) 
     return e.weight; 

    throw new RuntimeException("Get distance error"); 
    } 




    public void findMinDistance(Vertex vertex){ 
     for (Vertex target : vertex.neighbors) { 
     if(getShortestDistance(target) > getShortestDistance(vertex) + getDistance(vertex, target)) 
      distanceMap.put(target, getShortestDistance(vertex) + getDistance(vertex,target)); 
     } 

    } 




    public int getShortestDistance(Vertex destination){ 
    Integer d = distanceMap.get(destination); 

    if(d == null) 
     return Integer.MAX_VALUE; 
    return d; 
    } 



    public Vertex getMinimum(HashSet<Vertex> set){ 
    Vertex min = null; 

    for(Vertex v : set){ 
     if(min == null){ 
     min = v; 
     }else{ 
     if(getShortestDistance(v) < getShortestDistance(min)){ 
     min = v; 
     }  
     } 
    } 
    return min; 
    } 



    public boolean isSettled(Vertex v){ 
    return settledVertices.contains(v); 
    } 



    public LinkedList<Vertex> getPath(Vertex target){ 
    LinkedList<Vertex> path = new LinkedList<>(); 
    Vertex singleStep = target; 

    if(predecessors.get(singleStep) == null) 
     return null; 

    path.add(singleStep); 

    while(predecessors.get(singleStep) != null){ 
     singleStep = predecessors.get(singleStep); 
     path.add(singleStep); 
    } 

    Collections.reverse(path); 
    return path; 

    } 

マイ頂点クラス：

class Vertex{ 
    int value; 
    boolean visited; 
    int distance; 
    Vertex previous; 
    ArrayList<Vertex> neighbors = new ArrayList<>(); 

    public Vertex(int value){ 
     this.value = value; 
    } 

    public boolean isWall(){ 
     return this.value == 1; 
    } 

    public void setVisited(){ 
     this.visited = true; 
    } 

    public int getValue(){ 
     return this.value; 
    } 

} 

私は基本的に、この時点で自分自身を失ってしまったと私は、私ももうやっているかわからないんだけど。 getPathメソッドを使用しようとすると、Null Pointer Exceptionが発生します。私の質問は、始まりから終わりまで、そして終わりまでの壁の道から、最も安価な道をどうやって得ることができるかということです。各壁面について

Answer 1

Dijkstraのアルゴリズムを使用して任意の点への最短経路を構築するのは良いですが、開始と終了の両方から実行します。

のは、あなたがウォールのためのスペースのための_とXを使用して、この迷路を持っているとしましょう：

s _ _ X _ _ 
X _ X X _ X 
_ _ X _ _ _ 
_ X _ _ X _ 
_ X X _ X _ 
_ _ X _ _ e 

まず、スタートからの最短距離を埋める：

s s1 s2 X _ _ 
X s2 X X _ X 
s4 s3 X _ _ _ 
s5 X _ _ X _ 
s6 X X _ X _ 
s7 s8 X _ _ _ 

をそれが最後にあなたを持っている場合あなたは壁を飛び越さずに済んでいます。
そうでない場合は、エンドからの最短距離を埋める：

今

s s1 s2 X e6 e7 
X s2 X X e5 X 
s4 s3 X e5 e4 e3 
s5 X e5 e4 X e2 
s6 X X e3 X e1 
s7 s8 X e2 e1 e 

を、開始値と終了値の隣にある壁を見つける：

s s1 s2 -- e6 e7 
X s2 X X e5 X 
s4 s3 -- e5 e4 e3 
s5 -- e5 e4 X e2 
s6 X X e3 X e1 
s7 s8 -- e2 e1 e 

の最小合計で壁を選択してください2つの距離。
は4つの候補の 、3は合計8を持って、そして1は5つのソリューションのトータルここにあります合計10
があります

s →s1→s2→--→e6 e7 │ s →s1 s2 -- e6 e7 │ s →s1 s2 -- e6 e7 │ s →s1 s2 -- e6 e7 │ s →s1 s2 -- e6 e7 
      ↓↓ │ ↓↓    │ ↓↓    │ ↓↓    │ ↓↓    
X s2 X X e5 X │ X s2 X X e5 X │ X s2 X X e5 X │ X s2 X X e5 X │ X s2 X X e5 X 
      ↓↓ │ ↓↓    │ ↓↓    │ ↓↓    │ ↓↓    
s4 s3 -- e5 e4→e3 │ s4 s3→--→e5→e4→e3 │ s4 s3→--→e5 e4 e3 │ s4 s3→-- e5 e4 e3 │ s4 s3 -- e5 e4 e3 
       ↓↓ │    ↓↓ │   ↓↓  │  ↓↓   │ ↓↓   
s5 -- e5 e4 X e2 │ s5 -- e5 e4 X e2 │ s5 -- e5 e4 X e2 │ s5 -- e5→e4 X e2 │ s5 --→e5→e4 X e2 
       ↓↓ │    ↓↓ │   ↓↓  │   ↓↓  │   ↓↓  
s6 X X e3 X e1 │ s6 X X e3 X e1 │ s6 X X e3 X e1 │ s6 X X e3 X e1 │ s6 X X e3 X e1 
       ↓↓ │    ↓↓ │   ↓↓  │   ↓↓  │   ↓↓  
s7 s8 -- e2 e1 e │ s7 s8 -- e2 e1 e │ s7 s8 -- e2→e1→e │ s7 s8 -- e2→e1→e │ s7 s8 -- e2→e1→e