MOST 1 장애물을 극복 할 능력이 있다면 처음부터 끝까지 최단 경로를 계산합니다.

엘로이 젯슨

정수의 2D 매트릭스 형태로 미로가 주어졌습니다. 0은 통과 가능한 공간이고 1은 벽입니다.

시작 위치는 항상 다음과 같습니다.

배열 [0] [0] 
끝은 항상 다음과 같습니다.
배열 [HEIGHT -1] [WIDTH-1]
가능한 이동은 위, 아래, 오른쪽 또는 왼쪽입니다. 미로 내부의 벽은 최대 1 개까지 극복 할 수 있다는 점을 고려하여 처음부터 끝까지 최단 경로를 찾고 싶습니다. 저는 Maze 클래스와 Vertex 클래스를 만드는 것으로 시작했습니다. 첫 번째 생각은 BFS를 사용하는 것이었지만 최근에 이것이 당연히 작동하지 않을 것이라는 것을 깨달았으며 이제 Dijkstra의 알고리즘을 시도하고 있습니다. 아이디어는 통과 가능한 공간보다 훨씬 더 비싼 Wall의 가중치를 부여하고 Dijkstra를 사용하여 처음부터 끝까지 최단 경로를 찾는 것입니다. 그런 다음 각 벽에서 끝까지의 최단 경로를 계산합니다. 그 후 벽의 경로와 끝의 경로, 시작의 경로와 끝의 경로를 비교할 수 있다고 생각하고 어떻게 든 이것을 사용하여 벽을 제거하면 더 짧은 경로를 얻을 수 있는지 결정합니다.

저는 Dijkstra와 정말 힘들고 유용한 것을 얻기 위해이 모든 것을 통합하고 있습니다. 2d 배열 입력을 가져 와서 그래프를 만드는 Maze 클래스를 만드는 것으로 시작했습니다. 미로 클래스 :

   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 포인터 예외가 발생합니다. 대체로 내 질문은 시작에서 끝까지 가장 저렴한 경로를 얻은 다음 벽의 경로를 끝까지 얻을 수있는 방법이라고 생각합니다. 각 벽에 대해.

안드레아스

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 

두 거리의 합이 가장 작은 벽을 선택합니다.
4 개의 후보 중 3 개는 8 개, 1 개는 10
개입니다. 총 5 개의 솔루션이 있습니다.

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 

이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.

침해가 발생한 경우 연락 주시기 바랍니다debugcn@gmail.com 삭제

에서 수정
0

몇 마디 만하겠습니다

0리뷰
로그인참여 후 검토

관련 기사

분류에서Dev

CAKeyframeAnimation 애니메이션을 처음부터 끝까지 반복

분류에서Dev

별표. ARI를 사용하여 이벤트를 수집하고 있습니다. 이벤트를 처음부터 끝까지 단일 고객 상호 작용으로 그룹화하려면 어떻게해야합니까?

분류에서Dev

WLK를 처음부터 끝까지 두 사람으로 만 플레이 할 수 있도록 AzerothCore를 구성 할 수 있습니까?

분류에서Dev

처음부터보기가 상호 작용하고 클릭 가능한 시점까지 Android 앱의 로딩 시간을 계산합니다.

분류에서Dev

복제를 통해 물리적 및 가상 머신을 장애 조치합니다. 가능합니까?

분류에서Dev

`for (key in obj) BREAK`에는 O (1)이 아닌 O (N) 컴 펙션이 있습니다. 이것을 극복 할 방법이 있습니까

분류에서Dev

MySQL 다 대일 관계에서 값을 '합산'하는 방법, 여러 값이있는 경우 최대 값은 1 만 차지합니까?

분류에서Dev

문자가 20보다 크면 무엇을 사용할지 파이썬 코드를 작성했습니다. 사용자로부터 다시 입력을 받아 계산을 수행합니다.

분류에서Dev

RXJS를 사용하여 처음 누를 때부터 시간 창이 끝날 때까지 눌린 키를 관찰 할 수있는 방법은 무엇입니까?

분류에서Dev

장애물 회피 로봇의 여유 공간에서 최단 경로를 찾는 알고리즘이 있습니까?

분류에서Dev

그래서 git-all을 설치하려고 시도했고 내 시스템에서 다양한 그놈 패키지를 제거했지만 그 이유를 실제로 알지 못합니다. 이것을 어떻게 극복 할 수 있습니까?

분류에서Dev

자바 애플리케이션은 죽음을 가장합니다. Jstack은 애플리케이션 복구를 할 수 있습니까?

분류에서Dev

점수가 1 씩 증가 할 때마다 프로그램이 장애물 속도를 1 씩 증가시키는 방법이 있습니까?

분류에서Dev

합계 (열 이름 다음에 1이 아니면 0 인 경우)는 항상 한 행을 반환합니다. 아무것도 반환하지 않도록 어떻게 할 수 있습니까?

분류에서Dev

이 "Cannot Get /"nginx 오류를 어떻게 극복 할 수 있습니까?

분류에서Dev

Windbg는 액세스 위반을 극복하기 위해 변경되는 레지스터를 무시합니다.

분류에서Dev

`propertychange`-이벤트와 결합하지 않음-어떻게 극복 할 수 있습니까?

분류에서Dev

매우 간단한 맵에서 변경 불가능한 컬렉션 뷰를 얻으려고합니다 (얕은 복사본이면 충분할 수 있음).

분류에서Dev

타임 아웃 기능없이 디렉티브 내의 경쟁 조건을 어떻게 극복 할 수 있습니까?

분류에서Dev

웹 페이지 하단에 흰색 막대가 있습니까? 다가오는 여행을 위해 처음부터 첫 번째 사이트를 만듭니다.

분류에서Dev

Heroku로 배포 할 때이 " 'django_content_type'does not exist"오류를 어떻게 극복 할 수 있습니까?

분류에서Dev

Rails 앱에 대한 마이그레이션을 생성 할 수없는 것 같습니다.이 오류를 어떻게 극복합니까?

분류에서Dev

SAS의 데이터 단계에서 다음 반복을 계속하려면 어떻게해야합니까?

분류에서Dev

SAS의 데이터 단계에서 다음 반복을 계속하려면 어떻게해야합니까?

분류에서Dev

MIPS 시뮬레이터를 사용하여 N (내 경우에는 10)에서 1까지의 숫자 합계를 계산하고 있습니다.

분류에서Dev

Moodle 백업의 포럼 게시물을 처음부터 설치된 다른 서버로 복원하려면 어떻게해야합니까?

분류에서Dev

OSMNX 최단 경로-도달 할 수없는 경우 노드를 건너 뛰고 다음 가장 가까운 경로를 취하는 방법

분류에서Dev

가능한 가장 빠른 방법으로 문자열에서 하위 문자열을 검색합니다. 끝부터의 형식은 고정되지만 처음부터는 고정되지 않으며 길이도 고정되지 않습니다.

분류에서Dev

처음부터 끝에서 동위 원소 필터링을 변경할 수 없습니다.

Related 관련 기사

  1. 1

    CAKeyframeAnimation 애니메이션을 처음부터 끝까지 반복

  2. 2

    별표. ARI를 사용하여 이벤트를 수집하고 있습니다. 이벤트를 처음부터 끝까지 단일 고객 상호 작용으로 그룹화하려면 어떻게해야합니까?

  3. 3

    WLK를 처음부터 끝까지 두 사람으로 만 플레이 할 수 있도록 AzerothCore를 구성 할 수 있습니까?

  4. 4

    처음부터보기가 상호 작용하고 클릭 가능한 시점까지 Android 앱의 로딩 시간을 계산합니다.

  5. 5

    복제를 통해 물리적 및 가상 머신을 장애 조치합니다. 가능합니까?

  6. 6

    `for (key in obj) BREAK`에는 O (1)이 아닌 O (N) 컴 펙션이 있습니다. 이것을 극복 할 방법이 있습니까

  7. 7

    MySQL 다 대일 관계에서 값을 '합산'하는 방법, 여러 값이있는 경우 최대 값은 1 만 차지합니까?

  8. 8

    문자가 20보다 크면 무엇을 사용할지 파이썬 코드를 작성했습니다. 사용자로부터 다시 입력을 받아 계산을 수행합니다.

  9. 9

    RXJS를 사용하여 처음 누를 때부터 시간 창이 끝날 때까지 눌린 키를 관찰 할 수있는 방법은 무엇입니까?

  10. 10

    장애물 회피 로봇의 여유 공간에서 최단 경로를 찾는 알고리즘이 있습니까?

  11. 11

    그래서 git-all을 설치하려고 시도했고 내 시스템에서 다양한 그놈 패키지를 제거했지만 그 이유를 실제로 알지 못합니다. 이것을 어떻게 극복 할 수 있습니까?

  12. 12

    자바 애플리케이션은 죽음을 가장합니다. Jstack은 애플리케이션 복구를 할 수 있습니까?

  13. 13

    점수가 1 씩 증가 할 때마다 프로그램이 장애물 속도를 1 씩 증가시키는 방법이 있습니까?

  14. 14

    합계 (열 이름 다음에 1이 아니면 0 인 경우)는 항상 한 행을 반환합니다. 아무것도 반환하지 않도록 어떻게 할 수 있습니까?

  15. 15

    이 "Cannot Get /"nginx 오류를 어떻게 극복 할 수 있습니까?

  16. 16

    Windbg는 액세스 위반을 극복하기 위해 변경되는 레지스터를 무시합니다.

  17. 17

    `propertychange`-이벤트와 결합하지 않음-어떻게 극복 할 수 있습니까?

  18. 18

    매우 간단한 맵에서 변경 불가능한 컬렉션 뷰를 얻으려고합니다 (얕은 복사본이면 충분할 수 있음).

  19. 19

    타임 아웃 기능없이 디렉티브 내의 경쟁 조건을 어떻게 극복 할 수 있습니까?

  20. 20

    웹 페이지 하단에 흰색 막대가 있습니까? 다가오는 여행을 위해 처음부터 첫 번째 사이트를 만듭니다.

  21. 21

    Heroku로 배포 할 때이 " 'django_content_type'does not exist"오류를 어떻게 극복 할 수 있습니까?

  22. 22

    Rails 앱에 대한 마이그레이션을 생성 할 수없는 것 같습니다.이 오류를 어떻게 극복합니까?

  23. 23

    SAS의 데이터 단계에서 다음 반복을 계속하려면 어떻게해야합니까?

  24. 24

    SAS의 데이터 단계에서 다음 반복을 계속하려면 어떻게해야합니까?

  25. 25

    MIPS 시뮬레이터를 사용하여 N (내 경우에는 10)에서 1까지의 숫자 합계를 계산하고 있습니다.

  26. 26

    Moodle 백업의 포럼 게시물을 처음부터 설치된 다른 서버로 복원하려면 어떻게해야합니까?

  27. 27

    OSMNX 최단 경로-도달 할 수없는 경우 노드를 건너 뛰고 다음 가장 가까운 경로를 취하는 방법

  28. 28

    가능한 가장 빠른 방법으로 문자열에서 하위 문자열을 검색합니다. 끝부터의 형식은 고정되지만 처음부터는 고정되지 않으며 길이도 고정되지 않습니다.

  29. 29

    처음부터 끝에서 동위 원소 필터링을 변경할 수 없습니다.

뜨겁다태그

보관