Формальное агрегированное представлние предфрактального графа-скелета двумерного изображения

Краткие сообщения

рали, то матрица Б будет решением ЗКТ, если между элементами будут отсутствовать вертикальные и горизонтальные конфликты.

Формирование решения ЗКТ осуществляется в процессе эволюционной модификации матрицы Б. На первом этапе формирование матрицы Б производится с помощью генетического алгоритма трассировки в канале. На втором этапе производится эволюционная модификация матрицы Б путём перестановок трасс, которая удовлетворяет ограничениям взаимных наводок.

Хромосома Нк является упорядоченной совокупностью генов g к . Значением

gк является некоторый вектор ^, соответствующий столбцу матрицы Б. Гены

gк И ё\ хромосом Нк И Н/ гомологичны, они одинаковы по составу элементов, соответствуют одному и тому же подмножеству фрагментов , но отличаются порядком расположения элементов.

Декодирование хромосомы и определение магистралей для фрагментов осуществляется с помощью рассмотренной выше адаптивной процедуры. Основными генетическими операторами являются кроссинговер, мутация и селекция. В общем случае хромосомы могут обмениваться группами гомологичных участков, . . . -зуется принцип “рулетки”.

Операция мутации гена заключается в следующем. Случайным образом выбираются два элемента в гене для перестановки. Перестановка возможна, если не будет нарушения ограничений на допустимые позиции элементов в гене. Таким , .

Исследования трудоемкости алгоритма показали, что при фиксированных значениях размера популяции - М, числе генераций - Т, она пропорциональна 0(Ы), где N - число связываемых контактов.

Предложенный подход полностью применим для “бессеточной” трассировки соединений разной ширины. Модернизированная процедура декодирования будет последовательно размещать фрагменты, «прижимая» их на допустимую величину к ранее размещенным. Результатом работы будут физические координаты

.

Н.В. Браташенко, В.И. Кодачигов

ФОРМАЛЬНОЕ АГРЕГИРОВАННОЕ ПРЕДСТАВЛНИЕ ПРЕДФРАКТАЛЬНОГО ГРАФА-СКЕЛЕТА ДВУМЕРНОГО ИЗОБРАЖЕНИЯ

В данной работе предлагается способ задания графа-скелета 8 двумерного изображения р. Этот тип графов может быть отнесен к типу укрупненных пред-фрактальных графов р с вершинами-звездами различной звездной величины. Цель же нашей работы - описание метода формального их представления, ориентированного на простое расположение в памяти ЭВМ и удобное для восстановления по скелету как предфрактального графа р, так и исходного изображения 8.

Теория графов рекомендует три наиболее распространенных способа зада.

Известия ТРТУ

Тематический выпуск

1. С помощью матрицы смежности. Основной недостаток: для задания графов из n вершин требуется матрица из n X n элементов a, е {0,l} дня графов с

.

n X n. Ее элементы С, - это веса ребер. Они характеризуются числами С, 0 S С, > 1.

2. Списковое задание: для каждой i-той вершины графа составляется список смежных с ней вершин. Элементы этого списка - номера К, этих вершин,

К, е {¡Д..,n}.

3. С помощью матрицы инцидентности. Это список смежности вершин и

.

Наиболее удобен для задания графа типа S 1-ый метод - матрица смежности. Однако, для задания графов типа Q средств представляемых в рамках всех указанных методов не достаточно. В частности, наряду с указанием номера вершины (сО необходимо указывать ее ранг ri (звездную величину) и номер (тип) затравки, связанный с рангами r — 1,r — 2,...,1. В результате в матрице смежности , , : ее ранговая история (т.е. ранги шагов i —1,...,1, а также указатель направления

), . .,

матрицы С, - это магазин длиной минимум r+2. Из них один элемент - указатель смежности i и j (это 0,1 или С, ), r - предыстория роста предфрактального графа и

один элемент - наличие перемычки. Таким образом, формируется матрица смеж-.

Преобразуем ее из 2-мерной в 3-мерную. Некоторые уменьшения объема здесь может быть достигнуто при переходе к списочному представлению. Однако, оценить его можно лишь при практической реализации. Пока же можно сказать, что предлагаемое формальное задание целесообразно использовать для графов со ( ) 10,

.

С.В. Скороход

ПРИМЕНЕНИЕ НЕЧЁТКИХ ЧИСЕЛ ДЛЯ ОЦЕНКИ КВАЛИФИКАЦИИ

ПЕРСОНАЛА

Одной из центральных проблем в сфере управления персоналом является профессиональный отбор сотрудников из числа возможных кандидатов. Главная его задача - выбор кандидата, который лучше всего соответствует предъявленным требованиям. Однако, сами требования, в большинстве случаев, имеют нечёткие формулировки типа уверенное владение текстовым процессором Microsoft Word» или «опытный пользователь ПК». Такие формулировки допускают широкую интерпретацию в зависимости от субъективных предпочтений и личных симпатий работников кадровой службы, что, в конечном итоге, снижает качество отбора.