맨해튼의 휴리스틱과 함께 IDA * 알고리즘의 올바른 구현은 무엇입니까?

Question

목표 C에서 15 가지 퍼즐 문제를 해결하기 위해 IDA * 알고리즘을 구현하려고합니다. 알고리즘을 잘 구현했지만 정확한 결과를 얻지 못했습니다. 다음은 내 코드입니다.

- (TreeNode *)IDAStarSolution:(TreeNode *)startState { 
int limit = 5;//2*[startState fx]; 

appDelegate.CN=[NSNumber numberWithInt:limit]; 

TreeNode *result=nil; 

while (result==nil) { 
    [appDelegate.closedList addObject:startState]; 
    newLimit = 99999; 
    result = [self depthLimitSearch:startState costLimit:limit]; 
    limit = newLimit; 
    appDelegate.CN=[NSNumber numberWithInt:newLimit]; 
    [appDelegate.closedList removeAllObjects]; 
} 
return result; 
} 

- (TreeNode*)depthLimitSearch:(TreeNode *)current costLimit:(int)currentCostBound { 
NSArray *neighbors =[current expandNodeToChilds]; 
for (TreeNode *s in neighbors) { 
    if ([s.puzzleBox isFinalStateBox]) { 
     appDelegate.result=s.moveString; 
     return s; 
    } 

    if (![self closedSetContains:s]) { 

     int currentCost = [s.cost intValue] + [s.puzzleBox.manhattanDistance intValue]; 
     if (currentCost <= currentCostBound) { 
      [appDelegate.closedList addObject:s]; 
      [s.puzzleBox displayPuzzleBox]; 

      TreeNode *solution = [self depthLimitSearch:s costLimit:currentCostBound]; 
      if (solution!=nil&& (bestSolution ==nil|| [solution.cost intValue] < [bestSolution.cost intValue])) { 
       bestSolution = solution; 
       //return solution; 
      } 
     }else { 
      if (currentCost < newLimit) { 
       NSLog(@"new limit %d", currentCost); 
       newLimit = currentCost; 
      } 
     } 
    } 
} 
return bestSolution; 
} 


-(BOOL)closedSetContains:(TreeNode *)node{ 
for (TreeNode *tNode in appDelegate.closedList) { 
    if (tNode==node) { 
     return YES; 
    } 
} 
return NO; 
} 

depthLimitedSearch는 항상 null을 반환하고 동일한 노드를 반복하여 확장합니다. 내가 잘못 한 것은 제안하시기 바랍니다. 내가 최적의 비용보다 더 많은 제한을 설정 한 경우 Iterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java

것은 내가 지금 bestSolution를 반환하고 따라 다음 그것이 최적하지 않은, 처음으로 발견 된 솔루션을 반환

구현에 주어진 자바 코드와 유사하다. 지금 무엇을해야할까요?

Answer 1

돌연변이/열거 문제는 closedSetContains 메서드의 구조로 인해 발생한다고 생각합니다. appDelegate.closedList을 열거하지만 열거의 중간에서 돌아옵니다. 나는 열거 형이 여전히 활성화되어있는 것처럼 보이기 때문에 appDelegate.closedList을 수정할 때 오류가 발생한다고 의심합니다. 디버거에서 배열 appDelegate.closedList 예외가있는 배열 참조를 확인하여이를 확인할 수 있어야합니다.

-(BOOL)closedSetContains:(TreeNode *)node{ 
    BOOL ret=NO; 
    for (TreeNode *tNode in appDelegate.closedList) { 
    if (tNode==node) { 
     ret=YES; 
     break; 
    } 
    } 

    return ret; 
} 

도움이 될 수 -

당신이에 closedSetContains 변경. 그러나 appDelegate.closedList이 NSMutableArray 인 경우 전체 메서드를 [appDelegate.closedList containsObject:node]