Эвристика fixed partinioning — различия между версиями

Текущая версия на 14:59, 9 декабря 2017

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

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