ヒルクライミングアルゴリズムはどのように機能しますか？

Question

私は人工知能を本から学んでいますが、この本は私がここに投稿しようとしているコードを曖昧に説明しています。概念はやや単純ですが、私はちょうど以下のコードのいくつかを理解していないと私は私が移動する前に、このアルゴリズムを少し明確に理解するのを助ける人がほしいと思います。

私は最も混乱している部分の隣にコメントしました。これらの行が行っていることの概要は、私にとって非常に役立ちます。

int HillClimb::CalcNodeDist(Node* A, Node* B) 
{ 
    int Horizontal = abs(A->_iX - B->_iX); 
    int Vertical = abs(A->_iY - B->_iY); 
    return(sqrt(pow(_iHorizontal, 2) + pow(_iVertical, 2))); 
} 

void HillClimb::StartHillClimb() 
{ 
    BestDistance = VisitAllCities(); 
    int CurrentDistance = BestDistance; 

    while (true) 
    { 
     int i = 0; 
     int temp = VisitAllCities(); 
     while (i < Cities.size()) 
     { 
      //Swapping the nodes 
      Node* back = Cities.back(); 
      Cities[Cities.size() - 1] = Cities[i]; 
      Cities[i] = back; // Why swap last city with first? 
      CurrentDistance = VisitAllCities(); // Why visit all nodes again? 

      if (CurrentDistance < BestDistance) // What is this doing? 
      { 
       BestDistance = CurrentDistance; //??? 
       break; 
      } 
      else 
      { 
       back = Cities.back(); 
       Cities[Cities.size() - 1] = Cities[i]; 
       Cities[i] = back; 
      } 
      i++; 
     } 

     if (CurrentDistance == temp) 
     { 
      break; 
     } 
    } 

} 

int HillClimb::VisitAllCities() 
{ 
    int CurrentDistance = 0;  
    for (unsigned int i = 0; i < Cities.size(); i++) 
    { 
     if (i == Cities.size() - 1)//Check if last city, link back to first city 
     { 
      CurrentDistance += CalcNodeDist(Cities[i], Cities[0]); 

     } 
     else 
     { 
      CurrentDistance += CalcNodeDist(Cities[i], Cities[i + 1]); 
     } 
    } 
    return(CurrentDistance); 
} 

また、この本では、これがどのような山登りのタイプであるかは記載されていません。私はそれが立ち往生するときに再起動しないので、それは基本的な山登りだと思いますか？

Answer 1

本質的に、それは擬似コードでは、この行います

initialize an order of nodes (that is, a list) which represents a circle 

do{ 
    find an element in the list so that switching it with the last element of the 
    list results in a shorter length of the circle that is imposed by that list 
}(until no such element could be found) 

VisitAllCitiesその円の長さを計算するヘルパーであり、CalcNodeDistループがあるが二つのノード の外側との間の距離を計算するヘルパーです私がdo-untilと呼んでいたのは、内部のwhileループがすべての要素を反復処理することです。

if (CurrentDistance < BestDistance)の部分は、結果の長さを短くしてそのリストを変更するかどうかをチェックし、そうであれば距離を更新します。変更しない場合は、変更を元に戻します。

私が知りたいことすべてをカバーしましたか？特定の部分についての質問？