SE20101110025

branch and bound)tst efektywna w dużych grafach poszukiwań, gdy złe ścieżki szybko i wyraźnie wykazują brak perspekty w, jeśli chodzi o uzyskanie optymalnego rozwiązania.

Omawianie procedury programowania dynamicznego jest zbyteczne. Czytelnik znajdzie ją w wielu podręcznikach matematyki.

4.4*2. Wnioskowanie w warunkach niepewności ! i niepełności wiedzy

Ponieważ nie we wszystkich przypadkach wiedza jest pewna, wypada poświęcić parę słów wnioskowaniu w przypadku niepewności informacji. Ze względu na objętość tego opracowania, scharakteryzujemy tylko ogólne założenia wnioskowania w takich sytuacjach, odsyłając Czytelnika do literatury (na przykład [3]).

Niepewność w procesie rozumowania (poszukiwania rozwiązań) może dotyczyć zarówno faktów, jak i konkluzji. Najczęściej wykorzystywanymi metodami formalnymi są:

—    teoria prawdopodobieństwa (ang. probability theory), głównie prawo

Bayesa;.

—    współczynniki pewności (ang. confidence factors); '    ’

—    rozumowanie rozmyte (ang. fuzzy reasoning).

Tęofia Bayesa jest powszechnie znana i nie wymaga omawiania. Prawdopodobieństwa bayesowskie przypisywane są wszystkim hipotezom; Mdgąoriebyć modyfikowane na podstawie nowych faktów, pojawiających się W trakcie pracy systemu.,    'U'

Inną koncepcją postępowania w warunkach niepewności jest wykorzystanie współczynników pewności. Współczynniki te mogą być stosowane w różnych wariantach, a ich wartości mogą być zmieniane w trakcie pracy systernu. Jednym ze sposobów użycia współczynników jest przypisywanie pewności faktom lub konkluzjom (wnioskom), na przykład:

—    IF Fakt (CF - 0,3) THEN Konkluzja,

—    IF Fakt THEN Konkluzja (CF = 0,8).

Podane wartości współczynników traktowane są jako wartości progowe. Ustalane są przez inżyniera wiedzy (w porozumieniu z ekspertem dziedzinowym). Są podstawą do akty wowania reguł (przy przekroczeniu przez nie progów).

Inny wariant zastosowania współczynników pewności dotyczy sytuacji, gdy reguły mają wiele przesłanek. Wtedy każda z nich ma oznaczony współczynnik,'¹ na przykład:    ;

IF Faktl (CF = 0,2)    "

AND Fakt2 (CF = 0,4)

AND Fakt3 (CF = 0,8)

AND Fakt4 (CF=0,7)

TIIBN Konkluzja.

W (Mkltfi wypadku powstaje problem określenia współczynnika pewności dla Możrm przyjąć tu wiele różnych wariantów jego wyznaczenia, na

pyitNd

wnilosć średnia z CF dla przesłanek (w przykładzie 0,525); imiiUimm z CF dla przesłanek (w przykładzie 0,2);

-- maksimum z CF dla przesłanek (w przykładzie 0,8). frtHtmownnie rozmyte to trzeci ze sposobów wnioskowania w warunkach flHtyłUWitn^ i, Jego podstawą jest koncepcja zbiorów rozmytych wprowadzona f*»' > A . /. l uJeha. Istotą tej koncepcji jest zastąpienie klasycznej dwuwarto-hmk(j i / przynależności obiektu x do zbioru A:

/(x) = 1, gdyxe A,

/(x) = 0, gdy x e A,

funkcją

/: A <0,1>.

m w wrihalnym opisie przynależności pojawiają sie pojęcia “prawie”, "•feUT, "H orlic" itp. Odpowiada to otaczającej nas rzeczywistości, gdyż wprawę i iMfMo określenia nie są “ostre”, a informacje nie są jednoznaczne.

h'/yk Irtdowo, spróbujmy określić rozmyte funkcje wzrostu człowieka. Po-jftlA "niski" i “wysoki” nie są precyzyjne, nadają sie wiec do “rozmytej” IfMfHpiHm ) i. Jeżcli określeniu “x jest niski” przypiszemy funkcje:

/lOO ^r- 30 x ^{+ 6}’

A nlurSlniiu "x jest wysoki” funkcję:

,, .    1 A l 3    -

^MX) 2560000 ^X 6400 ^{X +}200 ’

Ift nli/yniiiiiiy obraz naszych preferencji co do werbalnego określenia wzrostu Wlnwlcka pizcdstawiony na rysunku 4.2.

ł i ysunkn wynika, że o człowieku mającym wzrost 150 cm na pewno powinny "niski". Człowiek o wzroście 240 cm jest na pewno “wysoki”.

49