Алгоритм сходження на вершину

Алгоритм пошуку зі сходженням до вершини (англ. Hill climbing) являє собою звичайний цикл, в якому постійно відбувається переміщення в напрямку зростання деякого значення, тобто підйом. Робота цього алгоритму закінчується після досягнення «піку», в якому жоден з сусідніх станів не має більш високого значення. В даному алгоритмі не передбачено супровід дерева пошуку, тому в структурі даних поточного вузла необхідно реєструвати тільки стан і відповідне йому значення цільової функції.

В алгоритмі зі сходженням до вершини не здійснюється прогнозування за межами станів, які є безпосередньо сусідніми по відношенню до поточного стану. Це нагадує спробу альпініста, який страждає від амнезії, знайти вершину гори Еверест в густому тумані.

В інформатиці алгоритм сходження на вершину є математичним методом оптимізації, який належить до сімейства локального пошуку. Це ітераційний алгоритм, який починається з довільного вирішення проблеми, а потім намагається знайти краще рішення, поступово змінюється один елемент рішення.

Наприклад, алгоритм сходження на вершину може бути застосований до задачі комівояжера. Легко знайти початкове значення, яке відвідує всі міста, але це буде дуже «бідним» в порівнянні з оптимальним рішенням. Алгоритм починається з таким рішенням і робить невеликі зміни до нього, такі, як зміна порядку, в якому два міста вже відвідали. Зрештою, набагато коротший маршрут, ймовірно, буде отримано.

Алгоритм сходження на вершину хороший для знаходження локального оптимуму (рішення, яке не може бути поліпшене шляхом розгляду сусідніх конфігурацій), але це не гарантується, щоб знайти оптимальне рішення (глобальний оптимум) з усіх можливих рішень (простір пошуку).

Відносна простота алгоритму робить його популярним вибором серед алгоритмів оптимізації. Він широко використовується в галузі штучного інтелекту, для досягнення стану(цілі) від початкового вузла. Вибір наступного вузла та початкового вузла може бути змінено, щоб дати перелік відповідних алгоритмів. Незважаючи на більш просунуті алгоритми, таких як імітація відпалу або табу-пошук, які можуть дати кращі результати, в деяких ситуаціях алгоритм сходження на вершину працює так само добре. Алгоритм сходження на вершину часто дає кращий результат, ніж інші алгоритми, коли кількість часу для виконання пошуку обмежені, наприклад, з системами реального часу.