नियम एक इनपुट (एल्गोरिथ्म) दिया मिलान

Question

के मैं निम्नलिखित श्रेणियां (उनके संभावित मानों के साथ) है लगता है:

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

या अधिक आम तौर पर ...

category: <array of values> 

(1) मान लीजिए मेरे पास कॉन्फ़िगर करने योग्य नियमों का एक सेट है जैसे:

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) और कुछ इनपुट मान।

प्रश्न: क्या कोई एल्गोरिदम है जो दिए गए इनपुट के अनुसार मिलान करने वाले नियम (सबसे विशिष्ट नियम को दी गई प्राथमिकता के साथ) खोजने की समस्या हल करता है?

Ex.1:

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

यह कहेंगे "y"

Ex.2:

input (color:gray, gender:female) 

यह "Z" कहेंगे

अधिक उपयुक्त है ऐसा करने का तरीका नियमों के आधार पर एक खोज पेड़ का निर्माण कर रहा है (पेड़ का प्रत्येक स्तर एक श्रेणी है)?

चाहते:

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

वहाँ यह करने का एक बेहतर तरीका है?

धन्यवाद!

Answer 1

निम्नलिखित संशोधनों के साथ एक निर्णय वृक्ष काम करेगा:

1. 'कोई भी' किनारों सभी नियमों

2. का उपयोग कर के रूप में एक ओर जहां रिकर्सिवली traversing, पार दोनों 'मान' पर साथ सामान्य तरीके से निर्णय वृक्ष बनाएं और 'कोई भी' और संख्या का ट्रैक रखने 'प्रत्येक समाधान में किसी भी की, कम से कम के साथ एक वापसी' किसी भी

   डीईएफ़ पार (मूल्यों, स्तर, पेड़, anyCount) है: (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

मैं एक मानचित्र में नियमों को हश करता हूं और फिर उसी हैश के साथ देखता हूं।

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

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

यह इनपुट के आधार पर कॉल करने के लिए सही फ़ंक्शन के नियमों और संकल्प के तेज़ी से निर्माण सुनिश्चित करेगा।

नियम बिल्कुल वरना किसी भी सामान्य, किसी भी, किसी भी उसके बाद यह सामान्य द्वारा किया जाता है पर गिर मिलान किया जाना चाहिए:

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

अन्यथा अगर यह इनपुट के साथ शुरू होता है और क्रमिक पर किसी भी नियम का चयन करता है प्रत्येक पैरामीटर तो आप यह कर सकते हैं।

हैश फ़ंक्शन मानों की एक सरणी स्वीकार करता है। जब आप किसी नियम से मिलान करने का प्रयास करते हैं, तो आप इनपुट के साथ शुरू करते हैं, और तब तक प्रत्येक को लगातार स्विच करते हैं, जब तक आपको कोई मिलान न मिल जाए।

def key hash(array[]) 

....

संकल्प प्रक्रिया ...

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

सही जवाब कैसे कल्पना आप प्राप्त करना चाहते हैं पर निर्भर करता है। Rete algorithm जैसी चीजें हैं। Google "विशेषज्ञ सिस्टम"। मैंने बड़े निगमों में काम किया है जिनके पास नियम मूल्यांकन प्रणाली है, लेकिन वे उन्हें घर में नहीं लिखते हैं - वे एक वाणिज्यिक पैकेज खरीदते हैं।

यदि आपकी ज़रूरतें सरल हैं, तो एक खोज पेड़ जहां प्रत्येक स्तर एक श्रेणी काम करेगा। यदि एप्लिकेशन में केवल विशिष्ट आइटम और एक सामान्य "कोई भी" आइटम है, तो यह ठीक काम करेगा। यदि सामान्यता के कई स्तर हैं ("स्तनपायी", "कशेरुकी", "पशु") यह मुश्किल हो जाता है।

यदि गति एक समस्या है, लेकिन स्मृति उपयोग नहीं है, तो आप हैशटेबल्स-ऑफ-हैशटेबल्स दृष्टिकोण भी आज़मा सकते हैं। हैशटेबल में प्रत्येक प्रविष्टि एक महत्वपूर्ण मूल्य जोड़ी है। शीर्ष-स्तर हैशटेबल में, कुंजी शीर्ष श्रेणी है: "कुत्ता", "बिल्ली", "कोई भी"। मान एक और हैशटेबल है। दूसरे स्तर के हैशटेबल में, कुंजी रंग है और मान एक और हैशटेबल है। और इसी तरह। गहन हैशटेबल के मूल्य में एक फ़ंक्शन पॉइंटर, क्लोजर, या आपके प्रोग्रामिंग भाषाओं की गतिशील आमंत्रण की जो भी विधि शामिल है।

Answer 4

मैं पहले सभी चर एक अद्वितीय मूल्य (सरणी स्थिति)

पशु: कोई = 0; बिल्ली = 1; कुत्ता = 2
लिंग: कोई = 0; पुरुष = 1; मादा = 2
रंग: कोई = 0; सफेद = 1; काला = 2; ग्रे = 3;

तो मैं प्रत्येक संभावित संयोजन को एक लुकअप मान दिया जाएगा।

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

या के मामले में: पशु किसी भी है, (0) रंग धूसर है, (3) लिंग पुरुष है

   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 | 
        ============================================================= 

प्रत्येक देखने मूल्य द्वारा निम्नलिखित गणना की जा सकती , (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 का मतलब है कॉल एक्स

तो अपने कार्यक्रम में:

की गणना आप ज्ञात मामलों

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 

जाहिर है उन मूल्य वास्तव में एक कॉन्फ़िग फ़ाइल में संग्रहित किया जा सकता है ताकि आप एक फिर से संकलन के बिना तर्क को बदल सकता है के खिलाफ है कि मूल्य की तुलना महत्व देते हैं।

Answer 5

आप लगभग सीधे स्केला कोड में इस अनुवाद कर सकते हैं।

मुहावरे, आप पशु, बिल्ली, कुत्ते का प्रयोग करेंगे - स्केला में अपरकेस साथ है, लेकिन अपने उदाहरण मैच के लिए, मैं सम्मेलन की सड़क यहाँ छोड़:

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)) 

परिणाम:

y called without freedom 
x called with animal: None 

आपको 'इनपुट' विधि में सॉर्टिंग पर ध्यान रखना होगा। विशिष्ट तरीकों से पहले विशिष्ट तरीकों को आना होगा।

और वहाँ कुछ मामलों में, जहां, अपने विवरण से यह क्या करना undecideable है, लेकिन आप तय करने के लिए है, जो परीक्षण पहले आता है:

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

कर सभी 1 खुला मामला है। यदि कुछ और नहीं है, (ए, सी, जी) उनमें से किसी से मेल खा सकता है, लेकिन केवल पहले मैच करेगा।

आपको एक सामान्य मामला (_, _, _) प्रदान करना होगा, लेकिन अगर यह समझ में नहीं आता है, तो एक त्रुटि फेंक सकती है।