爬山算法是如何工作的？

Question

我是从一本书上学习人工智能的，这本书对我即将post的代码进行了模糊的解释，我假设是因为作者假设每个人之前都经历过爬山算法。这个概念相当简单，但我只是不理解下面的一些代码，我希望有人能在我继续之前帮助我更清楚地理解这个算法。

我在最让我困惑的部分旁边做了评论，总结一下这些行在做什么对我很有帮助。

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 是计算两个节点之间距离的助手外层 while 循环就是我所说的 do-until，内层 while 循环遍历所有元素。

if (CurrentDistance < BestDistance) 部分只是检查通过交换更改列表是否会导致更小的长度，如果是，则更新距离，如果不是，则撤消该更改。

我是否涵盖了您想知道的所有内容？关于特定部分的问题？

爬山算法是如何工作的？

How does the Hill Climbing algorithm work?

c++

artificial-intelligence

hill-climbing