Эвристика fixed partinioning

Ссылки сюда (3) →

Эвристика fixed partinioning — техника, позволяющая сокращать перебор и получать приближенные полиномиальные алгоримтмы из алгоритмов динамического программирования, ищущих точное решение. Это обобщение процедуры скейлинга коэффициентов входной задачи, рассмотренной в разделе про FPTAS-алгоритм для рюкзака.

Например, для того же рюкзака, мы не трогали бы коэффициент, но разделили весь диапазон возможных значений на P эквивалентных интервалов, и в алгоритме динамического программирования, отбирали бы самый легкий набор для того «интервала - класса эквивалентности по стоимости», куда бы он попал.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.