ВЕСТНИК ВГУ, Серия физика, математика, 2003, ¹ 1 УДК 519.112 АЛГОРИТМИЗАЦИЯ ОДНОЙ ЗАДАЧИ ПЕРЕДАЧИ ИНФОРМАЦИИ © 2003 И. <...> Ф¸дорова, Г. Д. Чернышова Воронежский государственный университет Рассматривается задача дискретной оптимизации, возникающая при исследовании проблемы передачи информации. <...> Предлагаются алгоритмы решения, основанные на теории двойственности и на возможности оценивания исходной постановки задачей более простой структуры. <...> Эта задача возникает, например, при размещении на местности опорных пунктов передачи радиосигнала. <...> Требуется выбрать минимальное число таких опорных пунктов, при условии получения сигнала каждым объектом-абонентом. <...> При этом существуют ограничения на количество обслуживаемых объектов для каждого опорного пункта. <...> Считается, что j -й пункт может обслуживать i -й объект, если последний находится в радиусе его действия. <...> Исходные данные задачи можно представить в виде булевой матрицы (), 1, Aa i m j n== = ij aij = обслуживать i - й объект. <...> Для приближенного решения задачи (1) (4) можно использовать двойственные алгоритмы, алгоритмы «жадного» типа и адаптивные алгоритмы, позволяющие оценивать среднее значение функции. <...> На каждом этапе алгоритмов «жадного» типа делается попытка максимального достижения некоторой локальной цели в соответствии с выбранным критерием. <...> Для оценки предыдущих и последующих шагов алгоритма и повышения результативности его работы могут быть использованы дополнительные эвристические приемы. <...> Рассмотрим два «жадных» алгоритма для задачи (1)(4): Алгоритм 1. <...> Исходными данными для алгоритма являются матрица Α и j aDj щественно и можно считать, что iI j ij Da ∈ jij iI D . <...> Обозначим через Cov ij 1 множество выбранных столбцов матрицы A, а через R множество покрытых строк (первоначально вом этапе алгоритма сначала рассматриваются все столбцы с максимальным j 189 Cov {}, { }R=∅ =∅ ). <...> Ф¸дорова, Г. Д. Чернышова столбец один, то он сразу включается в Cov , а если их несколько, то выбирается столбец <...>