Диссертация (1150576), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Переиспользуются.mArr <- array ( zero , c (n , n , n + 1) )mNew <- array ( zero , c (n , n , n + 1) )# Массив, отвечающий за S_ {k ,n -1} после завершения работы функции.# В процессе работы в нем хранятся S_ { km } предыдущих слоев.sArr <- array ( zero , c (n , n , n + 1) )# Массив, отвечающий за S_ { kn }.snArr <- array ( zero , c (n , n , n + 1) )# Необходимо добавить единичную матрицу M_ {00}.diag ( sArr [ , ,1]) <- identitymArr [ , ,1] <- BmArr [ , ,2] <- Aif ( is . null ( pplus ) )pplus <- function (...) parplus (... , plus = plus )for ( i in 2: n ) {for ( j in 1:( i + 1) )sArr [ , ,j ] <- pplus ( sArr [ , , j] , mNew [ , , j ])# Вычисляем следующий слой M_ { km }.mNew [ , ,1] <- multiply (B , mArr [ , ,1] , plus , mult )mNew [ , ,i + 1] <- multiply (A , mArr [ , , i ] , plus , mult )for ( j in 2: i )mNew [ , ,j ] <- pplus ( multiply (A , mArr [ , , j - 1] , plus , mult ) ,multiply (B , mArr [ , , j ]) )mArr <- mNew}snArr <- pplus ( sArr , mNew )list ( sArr = sArr [ , ,1: n ] , snArr = snArr , A = A , B = B )}184185186# Функция, решающая задачу с ограничениями.constr <- function (A , p , q , r , B , plus = max , mult = add ,108zero = -Inf , identity = 0 , pplus = pmax , deg = div ,inv = maxplusinv ) {lambda <- spectr (A , plus , mult , deg )if ( lambda == zero )stop (" Incorrect matrix : eigenvalue equals zero !")# Проверяем, что Tr ( B ) \ leq \ mathbb {1}.# Пользуемся тем, что x \ leq y <= > x \ oplus y = y.trB <- Tr (B , plus , mult )if (( trB != identity ) && ( plus ( trB , identity ) == trB ))stop (" Incorrect matrix : Tr (B ) > \ mathbb {1}")n <- nrow ( A )temp <- sCreate (A , B , plus , mult , zero , identity , pplus )myu <- rfor ( i in 1: n ) {myu <- plus ( myu , deg ( tr ( temp$snArr [ , , i +1] , plus ) , 1/ i ) ,deg ( multiply ( multiply (conjInv (q , inv = inv , zero = zero ) ,temp$sArr [ , , i ] , plus , mult ) ,p , plus , mult ) , 1/( i + 1) ) )}myuminus <- inv ( myu )if ( is .

null ( pplus ) )pplus <- function (...) parplus (... , plus = plus )matr <- ast ( pplus ( mult ( myuminus , A ) , B ) , plus , mult , zero ,identity )qm <- conjInv (q , inv = inv , zero = zero )left <- mult ( myuminus , p )right <- mult ( myu , conjInv ( multiply ( qm , matr , plus , mult ) ,inv = inv , zero = zero ) )xleft <- multiply ( matr , left , plus , mult )xright <- multiply ( matr , right , plus , mult )list ( myu = myu , matr = matr , left = left , right = right , A = A ,p = p , q = q , r = r , B = B , xleft = xleft , xright = xright )187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220}221222223# Функция умножения чисел в полуполе R_ { max ,+}.add <- function (x , y ) x + y224225226# Функция возведения в степень в полуполе R_ { max ,+}.div <- function (x , m ) x * m109227228229# Функция взятия обратного в полуполе R_ { max ,+}.maxplusinv <- function ( x ) -x110Приложение БПрограммнаяреализациярасширеннойзадачи псевдочебышевской аппроксимацииДля расчетов в главе 3 использовались следующие процедуры, написанныена языке , листинг которых приводится в настоящем приложении, а такжеразмещен в репозитории по адресу https://github.com/SovanSB/Idempotent/.С их помощью можно проводить вычисления и решать рассмотренные вышезадачи оптимизации в различных идемпотентных полуполях.

Для их работытребуются основные функции работы с полуполями, исходные коды которыхприведены в приложении А.Структура программного обеспеченияВ программе реализованы следующие функции:– Функция нахождения минимума в расширенной задаче чебышевской аппроксимации (3.3), — ;– Функция разрежения матрицы в расширенной задаче чебышевской аппроксимации (3.3), — ;– Функция получения модифицированной разреженной матрицы задачи, — ;111– Функция для упорядочивания элементов в столбцах по возрастанию, — ;– Функция поиска наилучшей строки из списка, — ;– Функция для отбрасывания избыточных границ, — ;– Процедура поиска множества решений расширенной задачи чебышевскойаппроксимации (3.3), — .Функция для вычисления минимума целевой функции полемме 5 в задаче (3.3) принимает на вход обязательные параметры: матрицу ,векторы , , необязательные: функцию тропического сложения , функциютропического умножения , функцию тропического возведения в степень , тропический нуль , тропическую единицу , функцию взятияобратного по умножению , функцию сложения матриц .Функция для нахождения разреженной матрицы задачи (3.3) принимает на вход обязательные параметры: матрицу , векторы , , необязательные: функцию тропического сложения , функцию тропического умножения , функцию тропического возведения в степень , тропическийнуль , тропическую единицу , функцию взятия обратного по умножению , функцию сложения матриц , функцию нахождения меньшегоэлемента .̂︀′ для упрощения процедуФункция для получения матрицы ры выбора следующей рассматриваемой строки принимает на вход обязательные параметры: матрицу , вектор , необязательные: функцию тропическогоумножения , функцию взятия обратного по умножению .Функция для создания порядковой матрицы для упрощения процедуры выбора следующей рассматриваемой строки принимает на вход обязательные параметры: матрицу , необязательные: функцию тропического сложения , тропический нуль .

Больший номер в ячейке результирующейпорядковой матрице отражает большее количество строк, которые будут зафиксированные при выборе соответствующего элемента разреженной матрицы.112Функция для создания порядковой матрицы для упрощения процедуры выбора следующей рассматриваемой строки принимает на вход обязательные параметры: матрицу , и вектор строк для рассмотрения .Функция для отбрасывания избыточных границ путём их попарного сравнения принимает на вход обязательный параметр: матрицу границ, необязательный: функцию сложения матриц .Рекурсивная функция для поиска множества всех решений задачи (3.3) принимает на вход обязательные параметры: матрицу , векторы, , служебные: , , используются при рекурсивных вызовах функции, необязательные: функцию тропического сложения , функциютропического умножения , функцию тропического возведения в степень , тропический нуль , тропическую единицу , функцию взятияобратного по умножению , функцию сложения матриц , функцию нахождения меньшего элемента , функция преобразования матрицы в желаемую порядковую, функция поиска наилучшей строки изсписка, флаг , отражающий то, что строки меньшего порядка имеютбольший приоритет.

С помощью задания функций , и флага можно встроить собственные дискриминационные функции длястрок.Эти функции использовались для проведения расчетов в главе 3. Несмотряна то, что все примеры рассматривались в полуполе Rmax,+ , приведенные вышефункции могут корректно работать и в иных полуполях при задании соответствующих этим полуполям необязательных параметров.Листинг Б.1: Исходные коды использованных функций123# Функция вычисления меньшего значения в полуполе R_ { max ,+}.maxplusless <- function (x , y ) x < y4567891011# Функция нахождения минимума в задаче аппроксимацииminimumFinder <- function (A , p , q , plus = max , mult = add , deg = div ,zero = - Inf , identity =0 , inv = maxplusinv , pplus = pmax ) {delta <- deg ( multiply ( conjInv ( multiply (A , q , plus , mult ) ,inv , zero ) , p , plus , mult ) , 1/2)delta [1 ,1]}11312131415161718192021# Функция разрежения матрицы в задаче аппроксимацииsparsify <- function (A , p , q , plus = max , mult = add , deg = div ,zero = - Inf , identity =0 , inv = maxplusinv , pplus = pmax ,less = maxplusless ) {delta <- minimumFinder (A , p , q , plus , mult , deg , zero ,identity , inv , pplus )n <- ncol ( A )As <- Adelta2 <- inv ( mult ( delta , delta ) )22for ( i in 1: n ) {for ( j in 1: n ) {if ( less (A [i , j ] , mult ( delta2 , mult ( p [ i ] , inv ( q [ j ]) ) ) ) ) {# Обнуляем элементы ниже порогового значенияAs [i , j ] = zero}}}As23242526272829303132}33343536373839404142434445̂︀′# Функция для получения матрицы pmodify <- function (A , p , mult = add , inv = maxplusinv ) {n <- ncol ( A )k <- ncol ( A )mA <- matrix ( NA , n , n )for ( i in 1: k ) {for ( j in 1: n ) {mA [i , j ] <- mult ( A [i , j ] , inv ( p[i ,1]) )}}mA}464748495051# Функция для создания порядковой матрицыordering <- function (A , plus = max , zero = - Inf ) {n <- ncol ( A )k <- nrow ( A )fixA <- A114525354555657585960616263646566676869ord <- matrix ( rep (1: k , times = n ) , k , n )tempord <- matrix ( rep (1: k , times = n) , k , n )for ( j in 1: n ) {for ( i in 1:( k -1) ) {for ( m in 1:( k - i ) ) {# Упорядочиваем элементы столбца по возрастаниюif ( plus (A [m , j ] , A [ m +1 , j ]) == A [m ,j ]) {tV <- A [ m +1 , j ]tN <- ord [ m +1 , j ]A [ m +1 , j ] <- A [m , j ]ord [ m +1 , j ] <- ord [m , j ]A [m , j ] <- tVord [m , j ] <- tN}}}tempord [ , j] <- ord [, j ]}70717273747576777879808182838485868788899091res <- matrix ( NA , k , n )for ( j in 1: n ) {res [ tempord [ , j ] , j ] <- 1: k# Назначаем одинаковые номера равным элементамfor ( m in 1:( k -1) ) {if ( plus (A [m , j ] , A [ m +1 , j ]) == A [m , j ]) {res [ ord [m , j ] , j ] <- max ( res [ ord [m , j ] , j ] ,res [ ord [ m +1 , j ] , j ])res [ ord [ m +1 , j ] , j ] <- res [ ord [m , j ] , j ]}}for ( m in (k -1) :1) {if ( plus (A [m , j ] , A [ m +1 , j ]) == A [m , j ]) {res [ ord [m , j ] , j ] <- max ( res [ ord [m , j ] , j ] ,res [ ord [ m +1 , j ] , j ])res [ ord [ m +1 , j ] , j ] <- res [ ord [m , j ] , j ]}}}# Инвертируем порядок для удобстваres <- res - 1115res <- n -1 - resres [ fixA == zero ] <- nres92939495}96979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129# Функция отбрасывания избыточных границfilterPoints <- function ( cur , pplus = pmax ) {if ( is .

Характеристики

Список файлов диссертации