Статья в сборнике "Математические вопросы кибернетики" №4, Москва, 1992
Авторы:Воробьева Е.Г.
Монотонные преобразования в задачах дискретной оптимизации и минимизация стоимости кодирования в классе самосинхронизирующихся кодов
Аннотация:
В данной работе рассматриваются задача дискретной оптимизации. Для решения многих подобных задач используется метод Хаффмана, однако для его использования необходимо построение миноранты, что является сложной вычислительной задачей. Автор предлагает такой метод решения задачи дискретной оптимизации в классе двоичных самосинхронизирующихся кодов, который основан только на расширении области оптимизации и не требует построения миноранты. Предложенный алгоритм представляет собой соединение алгоритма монотонного поиска (с учетом мажорирования) и процедуры последовательной элиминации. Он имеет полиномиальную сложность, что асимптотически эквивалентно сложности некоторых реализаций алгоритма Хаффмана.
Ключевые слова:
дискретная оптимизация, самосинхронизирующиеся коды, метод Хаффмана, монотонные преобразования
