В чем разница между "восхождением на холм" и "жадными" алгоритмами?

Ответ 1

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

В эвристике поднятия холма вы начинаете с первоначального решения. Создайте один или несколько соседних решений. Выбирайте лучшее и продолжайте, пока нет лучших соседних решений. Это, как правило, дает одно решение. В восхождении на холм нам нужно знать, как оценить решение и как создать "соседа".

В жадной эвристике нам нужно знать что-то особенное в этой проблеме. Жадный алгоритм использует информацию для создания единого решения.

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

Жадный алгоритм будет выбирать объекты с наивысшей плотностью и помещать их до тех пор, пока рюкзак не будет заполнен. Например, по сравнению с кирпичом бриллиант имеет большую ценность и небольшой вес, поэтому мы сначала поместим алмаз.

Вот пример того, где жадный алгоритм потерпит неудачу: скажем, у вас есть рюкзак с емкостью 100. У вас есть следующие предметы:

• Алмаз, значение 1000, вес 90 (плотность = 11,1)
• 5 золотых монет, значение 210, вес 20 (плотность каждый = 10,5)

Жадный алгоритм будет помещен в бриллиант, а затем будет сделан, давая значение 1000. Но оптимальным решением будет включение 5 золотых монет, дающих значение 1050.

Алгоритм подъема холма будет генерировать начальное решение - просто произвольно выберите некоторые предметы (убедитесь, что они находятся под лимитом веса). Затем оцените решение, то есть определим значение. Создайте соседнее решение. Например, попробуйте обменять один предмет на другой (убедитесь, что вы все еще находитесь под лимитом веса). Если это значение имеет более высокое значение, используйте этот выбор и начните.

Скалолазание не является жадным алгоритмом.

Ответ 2

Да, вы правы. Hill climbing - общий математический метод оптимизации (см. http://en.wikipedia.org/wiki/Hill_climbing). Жадным алгоритмом является любой алгоритм, который просто выбирает лучший выбор, который он видит в то время, и берет его.

Примером этого является внесение изменений при минимизации количества монет (по крайней мере, с USD). Вы берете большую часть наивысшего достоинства монеты, а затем большую часть следующего максимума, пока не достигнете необходимого количества.

Таким образом, подъем холма является жадным алгоритмом.