처음 검색 - 자바

나는 자바에서 폭 넓은 첫 번째 검색을 구현하는 학교 excersice 있습니다. 문제가 내 검색이 작동하지 않으며 나는 나에게 조언을하고 나에게 궁극적 인 문제가 될 수있는 곳에서 약간적인 지침을 제공하기 위해 묻는 문제 :(그래서 필자를 찾을 수 없습니다 것입니다하지만 거의 모든 것을 구현했습니다.처음 검색 - 자바

public ArrayList<SearchNode> search(Problem p) { 
     // The frontier is a queue of expanded SearchNodes not processed yet 
     frontier = new NodeQueue(); 
     /// The explored set is a set of nodes that have been processed 
     explored = new HashSet<SearchNode>(); 
     // The start state is given 
     GridPos startState = (GridPos) p.getInitialState(); 
     // Initialize the frontier with the start state 
     frontier.addNodeToFront(new SearchNode(startState)); 

     // Path will be empty until we find the goal. 
     path = new ArrayList<SearchNode>(); 

     // The start NODE 

     SearchNode node = new SearchNode(startState); 

     // Check if startState = GoalState?? 
     if(p.isGoalState(startState)){ 
      path.add(new SearchNode(startState)); 
      return path; 
     } 


     do { 

      node = frontier.removeFirst(); 
      explored.add(node); 

      ArrayList reachable = new ArrayList<GridPos>(); 
      reachable = p.getReachableStatesFrom(node.getState()); 

      SearchNode child; 

      for(int i = 0; i< reachable.size(); i++){ 

       child = new SearchNode((GridPos)reachable.get(i)); 

       if(!(explored.contains(child) || frontier.contains(child))){ 
        if(p.isGoalState(child.getState())){ 
         path = child.getPathFromRoot() ; 
         return path; 
        } 
        frontier.addNodeToFront(child); 
       } 

      } 
     }while(!frontier.isEmpty()); 


     return path; 
    }

당신

출처

2012-09-23 mrjasmin

어떻게 작동하지 않습니까? 정확 해. – Borgleader

"잘못된"노드와 경로를 탐색하는 것 같습니다. – mrjasmin

당신이 우리에게 보여주지 않는 많은 방법이 있습니다. 두 개의 다른 배열/목록에서 노드를 추출하고 도달 가능한 노드를 단 하나의 노드에 삽입하는 것 같습니다. 당신의 상태도 이상합니다. 고전적으로 구현 된'explored'리스트 만 확인하면됩니다. 기본 개념은 목록의 처음부터 첫 번째 노드를 추출하고 모든 이웃을 같은 목록의 끝에 추가하는 것입니다. 목록이 비어 있거나 대상 노드를 해당 목록에 추가 한 경우 중지하십시오. – IVlad

frontier.addNodeToFront(child);

, 당신의 대기열의 전면에 요소를 추가하는 것은 깊이 우선 탐색으로 실행하는 코드를 정확한 원인이됩니다되는 코드 (getReachableStatesFrom() 등)의 나머지 부분을 가정 감사드립니다.

출처

2012-09-23 19:34:09

네, 맞습니다. 나 한테 멍청한 실수. 노드를 뒤쪽에 추가하기 위해 노드를 변경하면 "거의 효과가있는 것 같습니다."D – mrjasmin

@ user1285737 코드에 문제가있는 다른 위치를 식별 할 수 있으면 자유롭게 다른 질문을 열어보십시오. 내 대답을 받아들이는 것이이 질문에 적절하게 대답했다. 행운을 빕니다! –

들어 폭 넓은 첫 번째 검색을 구현하면 uld는 대기열을 사용합니다. 이 과정은 매우 복잡해 질 수 있습니다. 그래서 간단하게 유지하는 것이 낫습니다. 노드의 하위 노드를 대기열 (왼쪽 및 오른쪽)로 밀어 넣은 다음 노드 (인쇄 데이터)를 방문해야합니다. 그런 다음 큐에서 노드를 제거해야합니다. 큐가 비게 될 때까지이 프로세스를 계속해야합니다. 내 BFS 구현을 여기서 볼 수 있습니다 : https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java

출처

2016-08-07 00:16:49 Mohammad

처음 검색 - 자바

답변

관련 문제