RAM BFS 알고리즘 사용량 감소

Question

사용자가 입력 한 입방체 위치를 해결하기 위해 폭 넓은 첫 번째 검색 알고리즘을 사용하는 2x2x2 루빅 큐브 솔버를 작성했습니다. 이 프로그램은 큐브를 해결합니다. 그러나 난 어려운 위치에 입력하면 검색에 깊이 발견 될 해결할 문제가 발생, 나는 힙 공간이 부족합니다. 내 컴퓨터에는 4GB의 RAM 만 있으며 프로그램을 실행할 때 3GB를줍니다. 나는 수색에 필요한 숫양의 양을 줄이기 위해 내가 무엇을 할 수 있는지 궁금했다. BFS의 몇 가지 측면을 변경함으로써 가능할 수 있습니다. BFS하지만 난 지금 여기에 무슨 일이 일어나고 있는지 이해할 필요가 자사의 모든 정보가 모든 코드 파일에 대한 링크는 것을 두려워

static private void solve(Cube c) { 

    Set<Cube> cubesFound = new HashSet<Cube>(); 
    cubesFound.add(c); 

    Stack<Cube> s = new Stack<Cube>(); 
    s.push(c); 

    Set<Stack<Cube>> initialPaths = new HashSet<Stack<Cube>>(); 
    initialPaths.add(s); 

    solve(initialPaths, cubesFound); 
} 

static private void solve(Set<Stack<Cube>> livePaths, Set<Cube> cubesFoundSoFar) { 
    System.out.println("livePaths size:" + livePaths.size()); 
    int numDupes = 0; 

    Set<Stack<Cube>> newLivePaths = new HashSet<Stack<Cube>>(); 

    for(Stack<Cube> currentPath : livePaths) { 

     Set<Cube> nextStates = currentPath.peek().getNextStates(); 

     for (Cube next : nextStates) { 
      if (currentPath.size() > 1 && next.isSolved()) { 
       currentPath.push(next); 
       System.out.println("Path length:" + currentPath.size()); 
       System.out.println("Path:" + currentPath); 
       System.exit(0); 

      } else if (!cubesFoundSoFar.contains(next)) { 
       Stack<Cube> newCurrentPath = new Stack<Cube>(); 
       newCurrentPath.addAll(currentPath); 
       newCurrentPath.push(next); 
       newLivePaths.add(newCurrentPath); 
       cubesFoundSoFar.add(next); 
      } else { 
       numDupes += 1; 
      } 
     } 
    } 
    String storeStates = "positions.txt"; 
    try { 
     PrintWriter outputStream = new PrintWriter(storeStates); 
     outputStream.println(cubesFoundSoFar); 
     outputStream.println(storeStates); 
     outputStream.close(); 

    } catch (FileNotFoundException e) { 
     // TODO Auto-generated catch block 
     e.printStackTrace(); 
    } 

    System.out.println("Duplicates found " + numDupes + "."); 
    solve(newLivePaths, cubesFoundSoFar); 
} 

. https://github.com/HaginCodes/2x2-Cube-Solver/blob/master/src/com/haginonyango/pocketsolver/Cube.java

Answer 1

정의에 따르면, "최우수 우선 검색"은 전체 검색 경계에서 공간을 통해 가능한 경로를 유지합니다.

기하 급수적으로 커질 수 있습니다. 3x3x3 루빅 큐브를 사용하면 12가 있다고 생각합니까? 각각의 지점에서 가능한 이동이므로 10 개의 이동 순서는 틀림없이 10^9 이상인 12^10 조합을 필요로합니다. 이 많은 주에서는 총 저장 용량을 최소화하기 위해 주 크기를 최소화해야합니다. (어, 실제로 인쇄 모든 상태 "outputStream.println (cubesFoundSoFar);"? 밤은 출력의 광대 한 양의 것을?) 2x2x2와

, 당신은 각 지점에서 8 가능 움직임이있다. 난 임의의 문제에 대한 해결책 길이는 여기에 모릅니다. 길이가 10 인 경우 8^10이되며 여전히 큰 값입니다.

이제 많은 이동 시퀀스가 ​​동일한 큐브 구성을 갖습니다. 이를 인식하려면 생성 된 이동이 이미 방문한 위치를 다시 생성하지 않는지 확인해야합니다. 당신은 그 일을하고있는 것처럼 보이고 (좋은!) 히트 수를 추적합니다. 많은 경로가 동일한 구성으로 이어져야하기 때문에 조회수가 꽤 높을 것으로 예상됩니다.

표시하지 않는 것은 검색을 안내하기 위해 각 이동 순서에 점수를 부여하는 방법입니다. 다음 노드는 어떤 노드를 확장합니까? 이것은 가 가장 좋은이 나오는 곳입니다. 가이드가 없으면 (예 : 열거 된 모든 이동 시퀀스의 값이 동일 함) 모든 이동 시퀀스가 ​​동일하므로 엄청난 공간에서 진정으로 방황합니다. 솔버를 솔루션으로 안내하는 것은 무엇입니까? 우선 순위 큐와 같은 것이 노드 우선 순위와 우선 순위를 갖고 있어야하며 여기에 제시된 코드에는 표시되지 않습니다.

점수를 이동 순서의 품질로 측정하는 데 훌륭한 경험적 방법이 무엇인지 모르겠지만 도착 순서에 따라 이동 순서를 채점하여 시작할 수 있습니다. 시도 할 다음 "최상의 이동"은 가장 짧은 경로를 가진 것입니다. 그것은 아마도 대단히 도움이 될 것입니다.

(얼굴의 색상 수를 세는 것이 효과적 일 수 있지만 잘못된 색상을 제거하려면 3 -> 2 움직임을 취할 수있는 3 가지 색상 힌트가 사실입니까? 그런 다음 점수는 # moves + # facecolors-1 일 수 있으며 솔루션 이동 횟수를 계산할 수 있으며 가장 짧은 이동 순서를 원한다는 것을 알 수 있습니다.이 값은 소위 허용 가능한 불확실성 점수 일 수 있습니다.

또한 중복 이동 순서를 감지하도록 체계를 조정해야합니다. 이미 마주 치게 된 상태를 발견하면, 그 상태는 아마도 그 상태에 도달하는 데 걸리는 점수 (이동 횟수)를 그 상태에 첨부했을 것입니다. 히트를 치면 같은 상태에 도달하는 또 다른 방법을 찾았습니다 ... 그러나 새로운 경로에 대한 점수는 보다 작을 수 있습니다.은 상태에 기록 된 것보다 큽니다. 이 경우 작은 새 점수로 발견 된 중복 상태의 점수를 수정해야합니다. 이 방법으로 스코어 20을 가진 경로/상태는 사실 스코어가 10 인 것을 발견 할 수 있는데, 이것은 스코어가 갑자기 향상된다는 것을 의미합니다.