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

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

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

null ( dim ( cur )) || is . na ( dim ( cur ) [2]) ) {if ( is . null ( cur ) ) warning (" Ooops , cur is NULL ")dim ( cur ) <- c ( length ( cur ) , 1)}k <- ncol ( cur )toAdd <- matrix ( TRUE , k , 1)res <- NULLif ( k > 1) {for ( i in 1:( k -1) ) {if ( toAdd [i ,1]) {for ( j in ( i +1) : k ) {if ( toAdd [j ,]) {temp <- pplus ( cur [ , i ] , cur [ , j ])if ( all ( temp == cur [ , i ]) ) {toAdd [i ,1] <- FALSEbreak}if ( all ( temp == cur [ , j ]) ) {toAdd [j ,1] <- FALSE}}}}}res <- cur [ , toAdd [ ,1]]}else {res <- cur [ ,1]}res}130131# Процедура выбора следующей строки порядковой матрицы116132133134135136137138139140141142143144145146147148149150151152153154155156maxRow <- function ( ordMatr , numbers ) {num <- length ( numbers )n <- ncol ( ordMatr )maxNum <- 1maxValue <- - Inf# Если осталась единственная строка, возвращаем номерif ( num < 2) {maxNum <- numbers [[1]]}# Иначе считаем вес каждой из строкelse {# Чем больше строк будет зафиксировано, тем лучшеfor ( i in 1: num ) {temp <- sum ( ordMatr [ numbers [[ i ]] ,] , na .

rm =T ) n /2 * sum ( ordMatr [ numbers [[ i ]] ,]== n )# Вес нулевого значения считаем n /2if ( temp > maxValue ) {maxValue <- tempmaxNum <- numbers [[ i ]]}}}# Возвращаем номер наилучшей строкиmaxNum}157158159160161162163164165166167168169170171# Процедура поиска множества решений задачи аппроксимации# На первом шаге переменные prev , selected , sorted = NULLnextmatr <- function (A , p , q , prev = NULL ,selected = NULL , sorted = NULL , plus = max ,mult = add , deg = div , zero = - Inf , identity =0 ,inv = maxplusinv , pplus = pmax , less = maxplusless ,ordering = ordering , maxRow = maxRow , decreasingА=) {n <- ncol ( A )quantity <- 0# На первом шаге добавляем все строки для рассмотренияfut <- 1: n# Если шаг не первый, то prev -- зафиксированные строкиif (! is .

null ( prev ) ) {# Удаляем их из будущего рассмотрения117172173174175176177178179180181182183184185186187188189190191fut <- fut [ - prev ]}else {# Мы на первом шаге, получаем разреженную матрицуA <- sparsify (A , p , q , plus , mult , deg , zero ,identity , inv , pplus , less )# Для нулевых компонент p исследование не требуетсяpnull <- which ( p == zero )if ( length ( pnull ) > 0) {prev <- c ( prev , pnull )for ( i in pnull ) {selected <- c ( selected ,which ( A [ pnull ,] != zero ) [[1]])}fut <- fut [ - pnull ]}# Вычисляем порядковую матрицуsorted <- ordering ( pmodify (A , p , mult , inv ) ,plus , zero )}192193ll <- NULL194195196197198199200201202203204205206207208209210211# Если для рассмотрения осталось более одной строкиif ( length ( fut ) > 1) {# Выбираем из них наилучшуюbest <- maxRow ( sorted , fut )if ( best < 1) print (" Error , best < 1")if ( best > n ) print (" Error , best > n ")# Исследуем все ненулевые значения в наилучшей строкеfor ( j in 1: n ) {if ( A [ best , j ] != zero ) {# В зависимости от настроек decreasing фиксируем строкиif ( decreasing ) {toFix <- which (( sorted [ fut , j ] >= sorted [ best , j ])& ( A [ fut , j ] != zero ))}else {toFix <- which (( sorted [ fut , j ] <= sorted [ best , j ])& ( A [ fut , j ] != zero ))118212213214215#216217#218219220221222223224225226227228229230#231232233234235236237#238239240241242243244245246247248249250251#}toDel <- fut [ toFix ]count <- length ( toFix )Определяем оставшиеся для исследования строкиtoStay <- fut [ - toFix ]Если такие строки есть, то рекурсивно исследуем ихif ( length ( toStay > 0) ) {res <- nextmatr (A , p , q , c ( prev , toDel ) ,c ( selected , rep (j , count ) ) , sorted ,plus , mult , deg , zero , identity , inv , pplus ,less , ordering , maxRow , decreasing)ll <- cbind ( ll , res [[1]])quantity <- quantity + res [[2]]}else{Если в текущей ветке не осталось неисследованных строкtoMult <- matrix ( zero , n , n )bindedList <- cbind ( c ( prev , toDel ) ,c ( selected , rep (j , count ) ))toMult [ bindedList ] <- A [ bindedList ]delta = minimumFinder (A , p , q , plus , mult , deg ,zero , identity , inv , pplus )То формируем список найденных решенийll <- cbind ( ll , mult ( inv ( delta ) ,multiply ( conjInv ( toMult , inv , zero ) ,p , plus , mult ) ) )quantity <- quantity + 1}}}}else {Осталась последняя строка, исследуем ненулевые значенияnum = sum ( A [ fut ,] != zero )ret <- matrix ( zero , n , num )counter = 1tempA <- matrix ( zero , n , n )119252253254255256257258259260261262263264265266267268269270271272bindedList <- cbind ( prev , selected )tempA [ bindedList ] <- A[ bindedList ]delta = minimumFinder (A , p , q , plus , mult , deg ,zero , identity , inv , pplus )# Каждое из ненулевых значений формирует нижнюю границуfor ( j in 1: n ) {if ( A [ fut , j ] != zero ) {toMult <- tempAtoMult [ fut , j] <- A [ fut , j ]ret [ , counter ] <- mult ( inv ( delta ) , multiply (conjInv ( toMult , inv , zero ) , p , plus , mult ) )counter = counter + 1}}# Формируем из них список, считаем общее число границll <- cbind ( ll , ret )quantity <- num}# Отфильтровываем несущественные границы и возвращаем ихlist ( fp = filterPoints ( ll ) , quant = quantity )}120Приложение ВСхема поиска решений неравенстваВ приложении с использованием псевдокода приведена схема поиска решений неравенства 4.1, рассмотренная в главе 4Сначала нормируем матрицу как указано в (4.1.1).

Создадим массив из осей (списков узлов) и заполним его по принципу, описанному в (4.1.2) Введемследующие обозначения (переменные):coordlist – список координат, для которых неравенство уже выполнено (изначально пустой)nodelist – список уже добавленных узлов вместе с координатами, на которыхстало выполняться неравенство после добавления данных узлов (изначальнопустой)cur – номер текущей оси (изначально равен единице)nextnode – следующий узел на оси, NULL, если предыдущий был последним.Под ++nextnode будем понимать переход к следующему узлу. Под nodelist :=nodelist - nextnode - удаление из всех предыдущих узлов координат, которыевстречаются в nextnode. Если при этом в каком-нибудь узле не останется координат: hasNull(nodelist) == TRUE, то есть добавление одного из предыдущихузлов стало бессмысленным, то возвращаемся на уровень выше.

(изначальносписок пустой)(все переменные используются локально на каждом уровне, т.е. для каждогоуровня создается своя копия, которая впоследствии модифицируется)Addlist(coordlist, nodelist, nextnode) – процедура, которая пытается добавитьследующий узел, действует по алгоритму: (Алгоритм 2)Рекурсивно вызываем процедуру Gfind(coordlist, nodelist, cur) (Алгоритм 3).121После завершения работы данной процедуры у нас оказывается набор «граней», то есть минимальный набор таких векторов , что неравенство ≥ выполнено для любого вектора , для которого ≥ при каком-то .

При этом,если вектор таков, что не существует индекса , для которого справедливонеравенство ≥ , то ̸≥ .Если требуется получить набор непересекающихся множеств, то его можно получить с помощью стандартной процедуры: сопоставим каждой «грани»полуоткрытый справа интервал (то есть пару векторов), который она задает.Произвольным образом перенумеруем все грани, получив упорядоченный набор множеств.

После этого начинаем по порядку попарно сравнивать каждоемножество с остальными. Если есть пересечение множества с каким-то множеством , то заменяем множество с большим индексом (то есть ) на ихразность ∖ (в теоретико-множественном смысле) и продолжаем сравнениядальше.122Algorithm 2 Процедура Addlist для добавления новых узлов.1: function Addlist( coordlist, nodelist, nextnode)2:3:4:5:6:7:8:9:10:11:12:13:14:if nextnode == NULL thenreturn FALSEend ifnodelist ← nodelist - nextnode ◁ Убираем повторяющиеся координаты◁ из добавленных узлов, чтобы узлы отображали◁ какие уникальные координаты они привносятif hasNull(nodelist) == TRUE then ◁ Если в каком-то из предыдущих◁ узлов не осталось уникальных координатreturn FALSE ◁ то удалим этот узел: конфигурация не изменитсяend ifif nextnode ∈ coordlist thenreturn Addlist(coordlist, nodelist, ++nextnode)15:16:17:18:19:20:21:22:23:24:◁ Дошли до края координатной осиelse◁ На данном шаге не удалось добавить ничего нового◁ пытаемся добавить в следующем узле, проверяя◁ не стало ли бессмысленным добавление какого-либо◁ узла на прошлых уровняхnodelist ← nodelist + nextnodecoordlist ← coordlist + nextnode++nextnodereturn TRUEend ifend function◁ Добавляем новый узел◁ и координаты в списки123Algorithm 3 Процедура Gfind: Рекурсивно ищет новые «грани», при нахожде-нии распечатывает и продолжает работу.1: function Gfind(coordlist, nodelist, cur)2:if cur < m then◁ Если находимся не на последней оси3:Gfind(coordlist, nodelist, cur + 1) ◁ то cпускаемся на уровень ниже4:while Addlist(coordlist, nodelist, nextnode) == TRUE do5:if coordlist is full then◁ Найдена новая грань6:print(nodelist)◁ Фиксируем eе и возвращаемся выше7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:24:25:returnelse◁ Addlist изменила переменные, добавила узлыGfind(coordlist, nodelist, cur+1)end ifend whileelse ◁ Это последняя ось, необходимо добрать недостающие индексы◁ или вернуться на уровень выше, если это невозможноwhile !(coordlist is full) doif Addlist(coordlist, nodelist, nextnode) == TRUE thennextnode++elsereturnend ifend whileprint(nodelist)returnend ifreturnend function◁ Выводим найденную грань◁ Ничего не нашли, возвращаемся выше.

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

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