Как работает алгоритм Hill Climbing?

Я изучаю искусственный интеллект из книги, книга смутно объясняет код, который я собираюсь опубликовать здесь, я полагаю, потому что автор предполагает, что все испытывали алгоритм подъема в гору раньше. Концепция довольно проста, но я просто не понимаю некоторый код ниже, и я хотел бы, чтобы кто-то помог мне понять этот алгоритм немного яснее, прежде чем я продолжу.

Я прокомментировал рядом с частями, которые меня больше всего смущают, краткое изложение того, что делают эти строки, было бы очень полезно для меня.

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);
}

Также в книге не указано, что это за тип восхождения на гору. Я предполагаю, что это простое восхождение на холм, поскольку оно не перезапускается, когда застревает?

-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-till, внутренний цикл while перебирает все элементы.

if (CurrentDistance < BestDistance) part просто проверяет, приведет ли изменение этого списка путем замены результатов в меньшую длину, если это так, обновите расстояние, если нет, отмените это изменение.

Я охватил все, что вы хотели знать? Вопрос о конкретной части?

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]