Я читаю проблему одномерной упаковки в бункере и различные решения, которые можно использовать для ее решения.
Определение проблемы в бункере: дан список объектов и их веса, а также коллекциялотков фиксированного размера, найдите наименьшее количество лотков, чтобы все объекты были отнесены к корзине.
Решения, которые я изучаю: следующая подгонка, первая подгонка, наилучшая подгонка, наихудшая подгонка, первая подгонкаУменьшение, наилучшее соответствие Уменьшение
Я заметил, что некоторые статьи, которые я читаю, называют «алгоритмами приближения», а другие называют их «эвристикой».Я знаю, что есть разница между алгоритмами аппроксимации и эвристикой:
Эвристика: при некоторых сложных проблемах трудно найти приемлемое решение за приемлемое время выполнения, поэтому мы можем получить "нормальное" решение, применивкакие-то образованные догадки или произвольный выбор.
Алгоритм аппроксимации: это дает приблизительное решение с некоторой «гарантией» его производительности (может быть, соотношение или что-то в этом роде)
Итак, мой вопрос, эти решения, которые я 'Я изучаю эвристические или аппроксимационные алгоритмы?Я более склонен полагать, что они эвристические, потому что мы выбираем следующий элемент, который должен быть помещен в мусорное ведро некоторым «предположением».Нам не гарантировано какое-то оптимальное решение.Так почему некоторые люди называют их алгоритмами аппроксимации?
Если это не эвристические алгоритмы, то каковы примеры эвристических алгоритмов для решения проблемы упаковки бинов?