자바 재귀 문제로 미로 해결하기

Question

입구에서 출구까지 미로의 경로를 표시 할 수있는 과제가 있으며, 어느 정도까지 작동하도록 만들었지 만 미로가 더 많이 도착하면 막 다른 골목들로 인해 복잡해지며 그런 프로그램은 무한 재귀로 진행됩니다. 당신이 나에게 올바른 방향으로 나를 가리 키도록 도움을 줄 수 있다면 그것은 대단히 감사 할 것입니다.

Mu 현재 이론은 Room 클래스에서 찾을 수 있습니다.

여기 미로를 연결하는 각 방에 대한 참조가 저장되는 곳으로 북쪽, 남쪽, 동쪽, 서쪽, 위, 아래로 6 방향으로 링크 된 목록과 비슷한 종류가 있습니다. 여기

import java.util.ArrayList; 

public class OurRoom 
{ 
    private OurRoom exits[]; 
    private String name; 
    private static ArrayList<OurRoom> list; 

    public OurRoom() 
    { 
     this(null); 
    } 

    public OurRoom(String name) 
    { 
     this.name = name; 
     this.list = new ArrayList<OurRoom>(); 
     exits = new OurRoom[Direction.values().length]; 
     for(OurRoom exit : exits) 
     { 
      exit = null; 
     } 
    }  


    public void connectTo(OurRoom theOtherRoom, Direction direction) 
    { 
     exits[direction.ordinal()] = theOtherRoom; 
     theOtherRoom.exits[direction.getOpposite().ordinal()] = this; 
    } 

    public OurRoom getExit(Direction direction) 
    { 
     return exits[direction.ordinal()]; 
    } 

    public boolean lookExit(Direction direction) 
    { 
     return exits[direction.ordinal()] != null; 
    } 

    public String getName() { 
     return name; 
    } 

    public OurRoom solveRecursively(OurRoom exit) { 
     list.add(this); 
     if(this == exit) { 
      return this; 
     }else { 
      OurRoom temp = null;    
      if(lookExit(Direction.east)) { 
       temp = exits[Direction.east.ordinal()].solveRecursively(exit);    
      } 
      else if(lookExit(Direction.up)) { 
       temp = exits[Direction.up.ordinal()].solveRecursively(exit); 
      } 
      else if(lookExit(Direction.south)) { 
       temp = exits[Direction.south.ordinal()].solveRecursively(exit);    
      }   
      else if(lookExit(Direction.down)) { 
       temp = exits[Direction.down.ordinal()].solveRecursively(exit); 
      } 
      else if(lookExit(Direction.west)) { 
       temp = exits[Direction.west.ordinal()].solveRecursively(exit);  
      } 
      else if(lookExit(Direction.north)) { 
       temp = exits[Direction.north.ordinal()].solveRecursively(exit); 
      } 
      return temp; 
     } 
    } 

    public ArrayList<OurRoom> getList() { 
     return list; 
    } 

} 

는 방향 열거

public enum Direction 
{ 
    north, south, east, west, up, down; 

    public Direction getOpposite() 
    { 
     switch(this) 
     { 
      case north: 
       return south; 
      case south: 
       return north; 
      case east: 
       return west; 
      case west: 
       return east; 
      case up: 
       return down; 
      case down: 
       return up; 
      default: 
       return this; 
     } 
    } 
} 

입니다 그리고 여기에 미로를 구축하는 방법의 예입니다.

import java.util.ArrayList; 
import java.util.Iterator; 

public class OurMaze 
{ 
    private OurRoom entrance, exit; 

    public OurMaze() 
    { 
     this(1); 
    } 

    public OurMaze(int mazeNumber) 
    { 
     entrance = null; 
     exit = null; 
     switch(mazeNumber) 
     { 
     case 0: 
      break; 
     case 1: 
      this.buildMaze1(); 
      break;    
     default: 
     } 
    } 

    public OurRoom getEntrance() 
    { 
     return entrance; 
    } 

    public OurRoom getExit() 
    { 
     return exit; 
    } 

    public Iterator<OurRoom> findPathRecursively() { 
     entrance.solveRecursively(exit); 
     ArrayList<OurRoom> list = entrance.getList();  
     return list.iterator(); 
    } 

    private void buildMaze1() 
    { 
     OurRoom room1, room2; 

     room1 = new OurRoom("Room 1"); 
     room2 = new OurRoom("Room 2"); 
     room1.connectTo(room2, Direction.north); 

     entrance = room1; 
     exit = room2; 
    } 

    public static void main(String[] args) { 
     OurMaze maze = new OurMaze(1);  
    } 
} 

Answer 1

다른 사람들은이 문제를 해결하기위한 적절한 접근법을 설명했지만, 정확히 을 지적 해 두는 것이 가치 있다고 생각합니다. 귀하의 프로그램은 더 복잡한 미로로 확장되지 않습니다.

duffymo가 암시 하듯이 문제는 알고리즘이 백 트랙킹을 제대로 수행하지 못한다는 것입니다. 즉, 막 다른 골목으로 끝나는 지점을 가져 와서 이전 사각형으로 돌아갈 때 기억하지 않습니다. 모든. 고정 된 순서로 종료를 시도하기 때문에 항상 실패한 종료를 다시 시도하십시오.

solveRecursively 함수가 정의 된 방법을 살펴보면 어느 방에서나 한 방향 만 시도 될 것입니다. 방에 동쪽 출구가있는 경우 if-else 블록이 이 아닌으로 간주되므로 다른 출구가 있는지 여부는 중요하지 않습니다. 이 밝혀

그래서, 당신의 해결 로직은 올바른 해결책이 순서대로 각 방에서 "최초의"출구없는 경우 의 모든 경우 (두 개의 객실 사이에 무한 루프에 들어갈 예) 실패하면 거기 정의했다.

(각 방/방향에 대해 간단한 부울 플래그를 저장하는 것이 좋습니다. 재귀 호출을 호출하기 전에 설정 한 다음 다시 방으로 돌아 오면 방향이 ' 다른 블록 중 하나를 시도하기 위해 if 블록이 빠지도록 할 수 있습니다. Nikita가 제시 한 바와 같이 일반적인 BFS 논리를 사용하도록 리팩토링하면 전체적으로 더 좋을 것입니다.)

Answer 2

나는 당신이 어디에 있었는지 추적하기 위해 어떤 종류의 나무가 필요합니다.

재귀가 실패하면 대개 메소드를 작성한 사람이 중지 조건을 올바르게 표현하지 못했음을 의미합니다. 무엇 당신이야?

나는 이것이 컴퓨터에서 처음 만난 게임이라고 생각합니다. 내 학부 학위를 취득한 학교의 IBM 메인 프레임이었습니다. I/O는 종이 텔레타이에있었습니다. 이 미로 게임을하면서 버려진 돈으로 많은 소금 눈물이 울 렸습니다. 큰 재미.

Answer 3

셀을 방문했는지 여부를 나타내는 값으로 2 차원 배열을 유지하면됩니다. 동일한 셀을 두 번 통과하지 않으려 고합니다.

이외에도 폭이 좁은 우선 검색 (최단 경로를 원하지 않는다면 깊이 우선 검색도 좋습니다)입니다.

일부 링크 http://en.wikipedia.org/wiki/Flood_fill
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search

샘플 검색 루틴
.

void dfs(int i, int j) { 
     if cell(i, j) is outside of maze or blocked { 
      return 
     } 
     if visited[i][j] { 
      return 
     } 
     visited[i][j] = true; 
     dfs(i + 1, j); 
     dfs(i - 1, j); 
     dfs(i, j + 1); 
     dfs(i, j - 1); 
    } 

경로 자체가 visited과 같은 경우에 찾을 수 있습니다, 각 셀에 대해 당신은 당신이 그것에 온있는 셀을 유지한다. 그래서 인쇄는 이와 같이 보일 것입니다 (단지 의사 코드).

var end = exit_point; 
while (end != start_point) { 
    print end; 
    end = came_from[end]; 
} 

편집
코드는 위의 두 가지 차원 미로입니다 난 그냥 당신이 입체 버전을 것으로 나타났습니다. 그러나 위의 예에서 세 번째 좌표를 쉽게 입력 할 수 있습니다.
어려움이 있는지 알려주세요.

Answer 4

미로를 풀 때 각 노드가 공간이고 각 가장자리가 여섯 방향 중 하나에서 이동을 나타내는 6 진 그래프로 나타냅니다. 그런 다음 가장 짧은 경로를 찾는 데 잘 알려진 알고리즘을 적용 할 수 있습니다.

This page은 이와 같이 구조화 된 그래프를 통해 경로를 찾는 다양한 솔루션을 설명합니다. 가장자리를 따라 이동하는 비용은 다른 가장자리를 따라 이동하는 비용과 같으므로 그래프는 실제지도를 설명하는 것보다 쉽습니다.

특히 Dijkstra's algorithm을 확인하십시오.