Методы синтеза технических решений, страница 23

р (а, Р) - 1 - | а П Р I / max (| а |, | р |).                               (4.19)

Теорема 3. 1. р (а, Р) — 0 тогда и только тогда, когда а = р. 2. Для любых а, р, у из Ет р (а, Р)< р (а, у) + р (р, у).

Доказательство. 1. Пусть р (а, Р) = 0, тогда | a f] р | = = max ([ а |, | р |). Но это возможно лишь в случае а = р. Так как пути рассматриваются из прадерева, то а = р. Обратное утверждение очевидно.

а = [#!, #2, . . ., х

р = [а?!, *2, . . ., xk, z/fe+1, . . ., i/J,                                                                                             (4.21)

V = 1^1, хъ-> • • •» хъ %и> • • •> xii %i> • • •> Zpl-               (4.22)

Вершины перечислены в порядке прохождения соответствую­
щих путей, причем.^ ф yj Ф zk при любых i = 1, иг, / = fc+1, тг
и /с = Z + 1» Р' Распишем по определению (4.19):

р (а, Р) - 1 — fc/max (m, л);                                         (4.23)

р (а, у) = 1 — Z/max (ттг, р);                                              (4.24)

p(p,Y) = 1 - Л/max (л, р).                                              (4.25)

Доказательство сводится к доказательству справедливости неравенств:

р (а, р)< р (а, т) + Р (Р, Т),                                                 (4.26)

Р (а, Т)< Р («, Р) + р (т, Р),                                                (4.27)

Р (Р, Т) < Р (Р, «) + Р (V. «)-                                              (4.28)

Подставим в эти неравенства значения расстояний из (4. 23) — (4.25). Заметим, что возможны следующие соотношения чисел

2. Из определения (4.19) следует, что р (а, Р) = р (р, а). Так как Т (X, U) — прадерево, то с точностью до обозначений можно записать:

(4.20)


i=lfm k=i,

niax min

Из теоремы 3 следует,  что для  всех   i = i, т,   j = i,nи

Р(«i, Р?) < Р (<*г, Tfc) + Р (Р* ТО-

В  это неравенство вместо k подставим ki такое, что rninp(ai? тО = Р(оц,

te=i,p

Р (ai, pj

От обеих частей этого неравенства возьмем min по / = 1, п: min р (аг-, Pj) < min р (аь Тл) + mi

Заметим, что  min р (Р,, Y^) ^  m^f min^p (P,-, Vfc)- Подставляя

j=l»n                                              fc=bP j=l^n"

это выражение в предыдущее неравенство и беря от обеих частей max по  i = 1, т,  получаем:

та£тш_р(оц, &) ^ max min р (оц, Yfe) +

_

i=i,m fc=i,

г=1,тп j=i ,n

/c=l,p j=l,n

Таким же образом показывается справедливость неравенства max min р (сц, р;-) < max min р (ось ^) + max min р (ру, Yft)-

fe=i,p i=i,n

j==l,ni=i,m

Складывая последние два неравенства, получаем требуемое. Теорема доказана.

Таким образом, множество R? с введенным расстоянием пред­ставляет собой метрическое пространство. Предложенное расстоя­ние можно использовать для поиска ближайшего прототипа к некоторому найденному техническому решению. Кроме этого, если мощность множества Ry (А) после решения задачи поиска рациональных комбинаций слишком велика, то можно использо­вать введенное расстояние для выбора нескольких комбинаций из Дт 0^)» попарно отстоящих друг от друга на заданном рас­стоянии.