zasad dopasowania podane dane wejściowe (algorytm)

Question

Załóżmy mam następujące kategorie (wraz z ich możliwych wartości):

animal: any, cat, dog 
color: any, white, black, gray 
gender: any, male, female 
[...] 

lub bardziej ogólnie ...

category: <array of values> 

(1) Załóżmy Mam zestaw konfigurowalnych reguł, takich jak:

when animal is any, color is gray, gender is male, call x 
when animal is dog, color is gray, gender is male, call y 
when animal is any, color is any, gender is any, call z 
[...] 

(2) I niektóre wartości wejściowe.

P. Czy istnieje algorytm, który rozwiązuje problem znalezienia pasującej reguły (z priorytetem nadanym najbardziej konkretnej znalezionej regule) zgodnie z podanymi danymi wejściowymi?

Ex.1:

input (animal:dog, color:gray, gender:male) 

byłoby nazwać "y"

Ex.2:

input (color:gray, gender:female) 

byłoby nazwać "z"

Czy bardziej odpowiednie sposobem na to jest budowanie drzewa wyszukiwania na podstawie reguł (każdy poziom drzewa jest kategorią)?

lubię:

- any animal 
    - any color 
    - any gender => z 
    - gray 
    - male => x 
- dog 
    - gray 
    - male => y 

Czy istnieje lepszy sposób to zrobić?

Dzięki!

Answer 1

drzewa decyzyjnego z następującymi modyfikacjami będzie działać:

1. Utwórz drzewo decyzyjne w normalny sposób z „każdy”, jak krawędzie stosując wszystkie zasady

2. Przemierzając rekurencyjnie, trawers zarówno „wartość” i „każdy” i śledzić liczbę „każdy w każdym roztworze, powrót jednego z minimum” każdy jest

   def ukośnymi (wartości, poziom, drzewo, AnyCount): Jeśli drzewo jest to liść: powrotu (appr_func , anyCount)

   v1 = None 
   if values[level] in tree: 
       v1 = traverse(values, level+1, tree[values[level]]], anyCount) 
   
   v2 = None 
   if 'any' in tree: 
       v2 = traverse(values, level+1, tree['any'], anyCount+1) 
   
   if v1!=None: 
       if v2!=None: 
        if v1[1]<v2[1]: 
         return v1 
        else: 
         return v2 
       else: 
        return v1 
   elif v2!=None: 
       return v2 
   else: 
       return None 
   

Answer 2

Przepisałbym reguły na mapę, a następnie sprawdziłam z tym samym hashem.

map[hash(animal, color, gender)] = function to call 

call map[hash(inputanimal, inputcolor, inputgender)] 

Zapewniłoby to szybsze tworzenie reguł i rozwiązywanie prawidłowych funkcji wywoływania w oparciu o dane wejściowe.

Jeśli reguła musi być dokładnie albo spaść do rodzajową any, any, any to jest po prostu zrobione przez dopasowane:

if map.contains(hash(inAnimal, inColour, inGender)) 
    x = map[hash(inAnimal, inColour, inGender)] 
else 
    x = map[hash(any, any, any)] 

W przeciwnym razie, jeśli zaczyna się od wejścia i kolejno wybiera żadnej reguły na każdy parametr możesz to zrobić.

Funkcja skrótu akceptuje tablicę wartości. Gdy próbujesz dopasować regułę, zacznij od wejścia, a następnie sukcesywnie przełączaj każdą z nich, aż znajdziesz dopasowanie.

def key hash(array[]) 

....

proces rozdzielczości ...

input[] = {inAnimal, inColour, inGender} 
function x 
for(i = 0 to input.size) { 
    if(map.contains(hash(input)) { 
     x = map[hash(input)] 
     break 
    } 
    input[i] = any 
} 
call x 

Answer 3

Prawo Odpowiedź zależy od tego, jak fantazyjne chcesz uzyskać. Są takie rzeczy, jak Rete algorithm. Google "systemy eksperckie". Pracowałem w dużych korporacjach, które mają systemy oceny reguł, ale nie piszą ich w domu - kupują pakiet komercyjny.

Jeśli Twoje potrzeby są proste, a następnie drzewo szukaj gdzie każdy poziom to kategoria będzie działać. Jeśli aplikacja zawiera tylko określone pozycje i jeden ogólny element "dowolny", działałoby to dobrze. Jeśli istnieje wiele poziomów ogólności ("ssak", "kręgowiec", "zwierzę") staje się trudniejsze.

Jeśli prędkość jest problem, ale zużycie pamięci nie jest, to można też spróbować podejścia hashtables-of-hashtables. Każdy wpis w hashtable jest parą klucz-wartość. W hashtable najwyższego poziomu kluczem jest najwyższa kategoria: "pies", "kot", "dowolny". Wartością jest inny hashtable. W hashtable drugiego poziomu kluczem jest kolor, a wartość jest kolejnym hashtable. I tak dalej. Wartość najgłębszej hashtable zawiera wskaźnik funkcji, zamknięcie lub dowolną metodę dynamicznego wywoływania twoich ofert języków programowania.

Answer 4

Najpierw dałbym wszystkim zmiennym unikalną wartość (pozycja tablicy)

Zwierzę: dowolne = 0; cat = 1; pies = 2
Płeć: każdy = 0; samiec = 1; kobiet = 2
Kolor dowolny = 0; biały = 1; czarny = 2; szary = 3;

Wtedy daję każdej możliwej kombinacji podaje wartość odnośnika.

   Animal-|  ANY  |  cat   |  dog   |  
        ------------------------------------------------------------- 
      Gender-| any | male |female| any | male |female| any | male |female| 
        ============================================================= 
     Color-any  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 
        ------------------------------------------------------------- 
      white | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 
        ------------------------------------------------------------- 
      black | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 
        ------------------------------------------------------------- 
      gray | 27 | 28 | 29 | 30 | 32 | 33 | 34 | 35 | 36 | 
        ============================================================= 

Każda wartość wyszukiwania może być obliczone z następujących:

(Animal * number of animals) + Gender + (Color * number of animals * number of sexes) 

lub w przypadku: zwierzę jest dowolny (0) kolor szary, (3) płci męskiej , (1)

(Animal * number of animals) + Sex + (Color * number of animals * number of sexes) 
( 0 *  3  ) + 1 + ( 3 *  3   *  3  ) 

(0 * 3) + 1 + (3 * 3 * 3) 
    0 + 1 +  27  = 28 (the lookup value from the grid above) 

28 oznacza połączenia X.

Więc w swoim programie:

Oblicz cenisz Porównaj tę wartość na znanych przypadków

if Value in (1,2,8,13,14,15,21,28) then X 
if value in (3,4,5,23,24,26,34,35,36) then Y 
if value in (0,9,12,16,17,22,25)  then Z 

Oczywiście te wartości mogą być właściwie przechowywane w pliku konfiguracyjnym, więc można zmienić logikę bez ponownej kompilacji.

Answer 5

Można to tłumaczyć niemal bezpośrednio do kodu Scala.

Idiomatically, należałoby użyć zwierząt, kot, pies - z wielkimi literami w Scala, ale pasujące do Twojego przykładu, zostawiam drogę konwencji tutaj:

abstract sealed class animal() {} 
object cat extends animal() {} 
object dog extends animal {} 

abstract sealed class color() {} 
object white extends color {} 
object black extends color {} 
object gray extends color {} 

abstract sealed case class gender() {} 
object male extends gender {} 
object female extends gender {} 

def input (a: Option[animal], c: Option[color], g: Option[gender]) = (a, c, g) match { 
    case (Some (dog), Some (gray), Some (male)) => println ("y called without freedom") 
    case (_,   Some (gray), Some (male)) => println ("x called with animal" + a) 
    case (_,   _,   _   ) => println ("z called with anmimal: " + a + "\tcolor: " + c + "\tgender: " + g) 
} 

input (Some (dog), Some (gray), Some (male)) 
input (None,  Some (gray), Some (female)) 

Wynik:

y called without freedom 
x called with animal: None 

Musisz zająć się sortowaniem w metodzie "input". Konkretne metody muszą pojawić się przed niespecyficznymi.

I istnieją pewne przypadki, w których, z opisem Jest undecideable co zrobić, ale trzeba się zdecydować, który test jest na pierwszym miejscu:

(a, c, _) 
(_, c, g) 
(a, _, g) 

zrobić wszystko mieć 1 Otwórz obudowę. Jeśli nie ma nic innego, (a, c, g) może dopasować dowolny z nich, ale będzie pasować tylko do pierwszego.

Musisz podać ogólny przypadek (_, _, _), ale możesz podać błąd, jeśli nie ma to sensu.