스타 검색 알고리즘

Question

여기에 스타 검색 알고리즘에 관한 질문이 있습니다. 나는 8 조각 퍼즐로 알려진 것을 짓고 있습니다. 이 게임은 9 개 장소 (1 개는 비어 있음)가있는 게임이며 목표 위치를 맞추기 위해 올바른 순서로 타일을 정렬해야합니다.

문제를 해결하기 위해 코드를 올바르게 찾을 수 있도록 알고리즘을 올바르게 작성했는지 확인하면됩니다.

개인적으로 골격 위치에 도달하기 위해 한 번의 이동 만 필요로하는 내가 만든 첫 번째 사전 설정 퍼즐을 해결할 수 있기 때문에 알고리즘이 정확하다고 생각합니다. 그러나, 그것은 더 많은 움직임을 요구하는 퍼즐을 해결할 수 없습니다.

나는 이것을 3 가지 다른 방식으로 작동 시키려고 노력했으며 모두 동일한 문제를 가지고 있습니다.

시도 1 :

while (openList.Count() > 0) 
     { 
      PuzzleNode currentNode; 
      var orderedOpenList = openList.OrderBy(PuzzleNode => PuzzleNode.getPathCost()); 

      currentNode = orderedOpenList.First(); 
      if (compare(currentNode.getPuzzle(), goalArray) == true) 
      { 
       //openList.RemoveAt(0); //POLL 
       break; 
       // otherwise push currentNode onto closedList & remove from openList 
      } 
      else 
      { 
       openList.Remove(currentNode); 
       closedList.Add(currentNode); 
      } 

      //generate all the neighbor nodes 
      generateSuccessors(currentNode, tempList); 

      for (int i = 0; i < tempList.Count(); i++) 
      { 
       PuzzleNode tempNode = tempList[i]; 

       //skip the node if it's in the closed list 
       if (closedList.Contains(tempNode)) 
       { 
        continue; 
       }//end if 

       //We need to ensure that the G we have seen here is the shortest one 
       int gScore = currentNode.getG() + 1; 

       if (!openList.Contains(tempNode) || gScore < tempNode.getG()) 
       { 
        tempNode.setParentNode(currentNode); 
        tempNode.setH(tempNode.calcH(currentHueristic, tempNode.getPuzzle(), goalArray)); 
        tempNode.setG(gScore); 
        tempNode.updatePathCost(); 

        if (!openList.Contains(tempNode)) 
        { 
         openList.Add(tempNode); 
        }//end if 


       }//end if 
      }//end for 

     }//end while 

시도 2 ​​: Solving the 8-Puzzle Problem 그러나

I 완료 :

while (openList.Count() > 0) 
     { 
      PuzzleNode currentNode = GetBestNodeFromOpenList(openList); 

      openList.Remove(currentNode); 
      closedList.Add(currentNode); 

      generateSuccessors(currentNode, tempList); 

      foreach (PuzzleNode successorNode in tempList) 
      { 
       if (compare(successorNode.getPuzzle(), goalArray) == true) 
       { 
        //goto thebreak; 
        return successorNode; 
       } 
       successorNode.setG(currentNode.getG() + 1); 
       successorNode.setH(successorNode.calcH(currentHueristic, successorNode.getPuzzle(), goalArray)); 
       successorNode.updatePathCost(); 


       if (OpenListHasBetterNode(successorNode, openList)) 
        continue; 

       openList.Add(successorNode); 
      } 
     }//end while 

private static PuzzleNode GetBestNodeFromOpenList(IEnumerable<PuzzleNode> openList) 
    { 
     return openList.OrderBy(n => n.getPathCost()).First(); 
    } 

private static bool OpenListHasBetterNode(PuzzleNode successor, IEnumerable<PuzzleNode> list) 
    { 
     return list.FirstOrDefault(n => n.getG().Equals(successor.getG()) 
       && n.getPathCost() < successor.getPathCost()) != null; 
    } 

시도 2는 내가 인터넷에서 발견하는 알고리즘의 변경입니다 위키피디아의 psuedocode를 따르는 최선의 방법 :

function A*(start,goal) 
    closedset := the empty set // The set of nodes already evaluated. 
    openset := {start} // The set of tentative nodes to be evaluated, initially containing the start node 
    came_from := the empty map // The map of navigated nodes. 

    g_score[start] := 0 // Cost from start along best known path. 
    // Estimated total cost from start to goal through y. 
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal) 

    while openset is not empty 
     current := the node in openset having the lowest f_score[] value 
     if current = goal 
      return reconstruct_path(came_from, goal) 

     remove current from openset 
     add current to closedset 
     for each neighbor in neighbor_nodes(current) 
      tentative_g_score := g_score[current] + dist_between(current,neighbor) 
      if neighbor in closedset 
       if tentative_g_score >= g_score[neighbor] 
        continue 

      if neighbor not in openset or tentative_g_score < g_score[neighbor] 
       came_from[neighbor] := current 
       g_score[neighbor] := tentative_g_score 
       f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal) 
       if neighbor not in openset 
        add neighbor to openset 

내가 왜 퍼즐 중 하나에서만 작동하는지 혼란 스럽기 때문에 문제를 찾을 수 있는지 물어 본다. 이 퍼즐을 분리하면 목표 상태를 해결하는 데 필요한 이동량입니다.

몇 시간 동안 디버깅을했는데 볼 수 없으며 코드에 문제가있는 부분을 볼 수 없습니다. 그래서 나는 단지 묻고있는 것 같아,이 모양이 맞습니까?

질문이 있으시면 가능한 경우 자세히 알려 주시기 바랍니다. 미리 감사드립니다.

Answer 1

참고 : 당신이

여기에 자신의 휴리스틱 값 문제 상태를 준비 할 기본적으로 내가 PriorityQueue 인을 사용 그래서 여기 here

을 찾을 수 있습니다 (itowlson에 의해 작성) CustomPriorityQueue 클래스를 사용하고 있습니다 C#의 간단한 A * 템플릿으로 A * 검색의 작동 방식을 보여줍니다.

희망이 도움이되었습니다.