Раздел: Документация

0 ... 46 47 48 49 50 51 52 ... 96

4. Множество возможных решений У ={г/г}, / = i,k и множество возможных значений условий X, = {Ху;.}, iy = 1,яу определяют мат-

5. Для каждого решения уе в 1-й строке таблицы ставят единицу в клетках, соответствующих тем значениям условий, для которых данное решение существует.

Таким образом, процесс заполнения таблицы (матрицы) соответствий разбивается на ряд элементарных шагов, на каждом рассматривается только одно решение и только одно значение условия.

Анализ и корректировка таблиц

Таблица 4 является предварительной, се надо проанализировать и скорректировать. Пусть задана таблица:

У = {У{), / = 1А X={xjij}9 j = \,m, ij =1,яу. И матрица размерностью:

;=1

Требуется построить граф-схему анализа и поиска решений. Множеству вершин графа G ставится в соответствие множество условий:

Х={Ху},/ = 1Я

Множеству ребер - множество значений условий.

На вершины графа G навешиваются также решения г/1. (Граф G определяется как множество ребер).

Вначале, перед построением графа G, составляется нормализованная таблица, т.е. из множества линейно-зависимых столбцов оставляется один, удаляются единичные столбцы.

Вводится понятие коэффициента плотности. Это число aj, равное количеству единиц в столбцах, относящихся к j-му условию:

рицу соответствии

т *ч

й размерностью: К х V* •

т

Xjij, ij =1,Яу, j = 1,1Я.

Таблица упорядочивается в порядке возрастания плотности соответствия (см. табл.5, 6).

---

Таблица 5

Исходная

У		X	1		X	о	х.
							*31	*32	*33	*34
У\	1		1	1	1		1			1
У2	1	1	1		1	1	1	1	1		1
Уз		1	1	1		1				1
Ул	1		1		1		1	1	1		1
ys		1	1	1	1	1				1
Ук	1	1	1			1	1		1		1
У7	1		1	1	1		1	1	1	1	1
		<h	= 13		а2	= 9	д3 =16

Таблица 6

Преобразованная

У	х<		Хо			х.
		Х\2	*21	Х22	23	*31	32	*33	*34
t/1	1				1			1
У2	1	1	1	1		1	1		1
Уз		1		1	1			1
Уа	1		1			1	1		1
Уь	1	1		1	1			1
Ув		1	1	1		1			1
У7	1		1		1	1	1	1	1

Для построения графа G по таблице соответствий вводится понятие яруса, /-ым ярусом графа G называется совокупность вершин с выходящими из них дугами, длина пути к которым из начальной вершины равна j -1.

Первый ярус

Gt =(Х,,{*!/,}), ц = \,щ

Ьторой ярус

G2 =(112/2>;12»{2/2>;12»{2/2>»-->l/l,{2/2>,--)» *2 =

;-й ярус

Су = (дгу м ,{лу£/}; -1,2 »<у«7 >» - - -itiy -1 yiy >»•--); v = 1>"у

772-Й Ярус

---

Путь на графе G из вершины Х\ к дуге Xjy /-го уровня будет = {XW *xj-\tij-\ »-"»*l/l)- Каждой дуге ставится в соответствие значение некоторого условия. Множество решений г, значения /-го условия Rjij = R(xjjj ). Тогда пути Lyy соответствует множество решений, которое существует для всех xpip, р = 1,/, ip -\пр, т.е.

RiLjij ) = R(x2 / 2 ) n №х2/ 2 )n» • • • хргр V\ • • • ,r&(xjij )• Для построения дуги, исходящей из iy j вершины /-го уровня, из таблицы соответствий выбирают условие Xj и для каждого значения этого условия Xjij проверяют соотношение: Rixjij ) n MLy i у i) = 0. Если нет ~ дуга строится.

Последний уровень Хт содержит только висячие вершины (см. рис.2.19).

G

0 #6 #б Уб #4 0 ук 0 у4 6 у4 уе

Рис.2.19. Граф-схема поиска решений

\ + Щ + Щ x П2 + Щ x П2 x 72 3 = 1 + /2у

;=1;=1

Поиск решений по таблице соответствий

Исходной информацией является кортеж:

и таблица соответствий. Задача сводится к нахождению: У* = /XX).

0 ... 46 47 48 49 50 51 52 ... 96