폭스 우선 검색 알고리즘 JAVA 8- 퍼즐

Question

8 퍼즐 게임에 대한 폭 - 우선 알고리즘을 구현하려하고 있습니다. 나는 그것이 새로운 사례가 아니며 웹상에서 해결책을 찾는다는 것을 알고 있지만, 나는 사고 방식으로 그것을 만들고 싶다.

이 코드는 이미

123 
456 
780 

인 노드 결과를 발견하지만 그것을 할 수있는 35 단계를 수행!

의견을 보내 주시면 감사하겠습니다. Wikipedia 따르면 =)는

//This method receives a Collection of `Nodo` objects, each one will be checked and compare with the finalGoal 

    public void percorreNodos(Collection<Nodo> nodosBase) 
      { 
       //In this class a have an array that has all the IDs os nodes that already has been checked 
       //The ID of a Node, is the representation: 123456780, 354126870 , etc.. 
       System.out.println("idsPercorrido.size() = " + idsPercorridos.size()); 
       //Check if the collection nodosBase contains the finalGoal 
       Iterator<Nodo> iterator = nodosBase.iterator(); 
       while(iterator.hasNext()) 
       { 
        Nodo nodoBase = (Nodo) iterator.next(); 
        //If this current node has already been checked, we dont have to check it again 
        idsPercorridos.add(nodoBase.getId()); 
          //Just print the node (sysout) 
        nodoBase.print(); 
        contPassos++; 
        System.out.println("\n" + contPassos + " STEPS(number of nodes checked)..."); 
        //Check if this node is the final goal 
        if(nodoBase.isObjetivoFinal()) 
        { 
            //set the variable indicating that the result has been found 
         encontrouObjetivo = true; 
         System.out.println("Resultado alcancado EM " + contPassos + " PASSOS..."); 
         nodoBase.print(); 
         break; 
        } 
       } 

       // Now that we know that no one Node of nosoBase collection is the final goal, we are going to generate the next children to be checked, and call this function recursively 
       //Just confirm that we didnt find the goal 
       if(encontrouObjetivo == false) 
       { 
          //Creates the next frontier 
        Collection<Nodo> novaFronteira = new HashSet<Nodo>(); 

        for(Nodo nodoPai : nodosBase) 
        { 
            //Generate each Node its childrens and add to a collection called "novaFronteira" 
         Collection<Nodo> filhos = nodoPai.gerarFilhos(); 
         for(Nodo filho : filhos) 
         { 
//idsPercorridos is a collection<String> which contains all the nodes ids that we checked, we dont want to check a node more than one time ! 
          if(idsPercorridos.contains(filho.getId()) == false) 
          { 
           novaFronteira.add(filho); 

          } 
         } 
        } 
        this.percorreNodos(novaFronteira); 
       } 

      } 

Answer 1

novaFronteira에 중복 요소를 추가하지 않아도됩니다.

for(Nodo nodoPai : nodosBase) 
{ 
    Collection<Nodo> filhos = nodoPai.gerarFilhos(); 
    for(Nodo filho : filhos) 
    { 
     if(idsPercorridos.contains(filho.getId()) == false) 
     { 
      novaFronteira.add(filho); 
     } 
    } 
} 

novaFronteira 많은 중복 된 노드를 추가에서이 코드를 방지 거기에 아무것도

.

if 문 내부에 idsPercorridos에 추가하면 데이터 및 데이터 구조가 정확히 무엇인지에 따라이 단계의 추가 실행 시간이 달라 지지만 이러한 오류가 발생하지 않으며 단계가 줄어 듭니다. 전화가 실제로 원래보다 오래 걸릴 수 있습니다. 문제가 시간을 실행하는 경우이 효율적 contains 통화를 허용로하지 않는, ArrayList 또는 LinkedList에 반대

---

, 당신은, idsPercorridos가 TreeSet 또는 HashSet 있는지 확인해야한다.

---

문제가 해결되지 않으면 대상과의 거리 각 노드에 휴리스틱 기능을 추가하는 것을 포함하는 대신 the A* algorithm를 사용하여 시도해 볼 수도 있습니다 -이 가까운 대상 노드를 탐색 할 수있게 해준다 첫째, 종종 거기에 도달하는 데 더 적은 단계로 이어집니다.

좋은 휴리스틱 함수는 각 타일과 대상 위치 사이에 Manhattan distances의 합계가 될 수 있습니다.

현재 코드가 상당히 변경 될 수 있습니다.

Answer 2

이 퍼즐 9!/2 = 181440 가능한 조합을 풀수있다. 각 노드에서 이러한 각 조합을 확인하면 (그렇지 않으면 계산이 더 쉬워집니다) 약 (9!/2) * 9 = 1,632,960 단계가됩니다. 따라서 컴퓨터가 해당 단계를 수행 할 수 있기 때문에 알고리즘이 350,000 단계 인 경우 문제가 발생하지 않습니다. 은 실제로입니다.