अनिवार्य और वैकल्पिक स्थितियों के tuples पर नियम मिलान एल्गोरिदम के लिए सीएस शब्द

Question

मैं किसी विशेष समस्या को हल करने के लिए एल्गोरिदम के लिए साहित्य शोध करने की कोशिश कर रहा हूं, लेकिन मुझे नहीं लगता कि मैं सही खोज शब्द को जानता हूं कि मैं क्या कर रहा हूं खोज रहे हैं

लक्ष्य एक क्वेरी करने योग्य नियम डेटाबेस होना है, जहां प्रत्येक नियम को ट्यूपल स्थितियों के रूप में निर्दिष्ट किया गया है — कुछ अनिवार्य, कुछ वैकल्पिक। सिस्टम में एक प्रश्न में दुनिया के बारे में तथ्यों का एक झुकाव होता है, और उन सभी नियमों की एक सूची देता है जिनकी अनिवार्य स्थितियां क्वेरी में तथ्यों से मेल खाते हैं। प्रत्येक नियम संख्या × द्वारा मिलान की गई वैकल्पिक स्थितियों के वजन से स्कोर किया जाता है और इस प्रकार सूची को क्रमबद्ध किया जाता है।

एक उदाहरण के लिए

तो, क्वेरी होगा

(nightowl = no, pets = 1, smoker = no, musician = no) 

लौटने

तरह

alice : { mandatory : { nightowl = no, smoker = no, pets < 2 }, 
      optional : { pets = 0 } } 
bob : { mandatory : { nightowl = yes, pets = 0 }, 
      optional : {smoker = no} } 
charlie : { mandatory : { musician = no }, 
      optional : {nightowl = yes, pets < 2 } } 

और कुछ अगर मैं इस प्रयोग कर रहे थे एक रूममेट मिलान सेवा लिखने के लिए, नियमों होगा

(charlie : 1/1 mandatory matched, 1/2 optional matched, 
    alice : 3/3 mandatory matched, 0/1 optional matched) 

मुझे पता है कि यह एक समस्या है जिसे कंप्यूटर विज्ञान में कई बार हल किया जाना चाहिए , लेकिन मुझे नहीं पता कि कौन से कीवर्ड खोजना चाहते हैं। यह दूरी फ़ंक्शन नहीं है, क्योंकि कुछ स्थितियां अलग-अलग सत्य/झूठी अस्वीकार हैं जबकि अन्य वैकल्पिक हैं या रैखिक स्कोर हैं। यह पैटर्न मिलान या फ़ज़ी मिलान है, क्योंकि वे ज्यादातर स्ट्रिंग और ग्राफ को संदर्भित करते हैं। यह उत्पादन प्रणाली या नियम इंजनRete algorithm की तरह है, क्योंकि यह नियमों से IF-THEN संदर्भ नहीं खींचता है, और न ही यह एक कॉल से अगले तक तथ्यों को याद करता है।

कहा जाता है?

मुझे केवल एल्गोरिदम के शोध या विवरण की आवश्यकता है, वास्तविक कार्यान्वयन नहीं। हमारे आवेदन में इतनी गंभीर रीयलटाइम और मेमोरी बाधाएं हैं कि हमें किसी भी तरह का कार्यान्वयन करने की आवश्यकता होगी, लेकिन मैं जानना चाहता हूं कि कोड का आविष्कार शुरू करने से पहले अंतरिक्ष में और क्या किया गया है। एक एसीएम पेपर जो मैं उद्धरण का पीछा कर सकता हूं वह भी महान होगा।

Answer 1

शब्द जो मैं कहता हूं कि आप जिस प्रकार की समस्या के बारे में बात कर रहे हैं, उसका सटीक रूप से वर्णन करता है वह constraint satisfaction समस्या है।

अधिक विशेष रूप से, आप भारित बाधा संतुष्टि के दायरे में हैं।

बाधा प्रोग्रामिंग उन प्रकारों और भाषाओं के सेट के लिए सामान्य शब्द है जो विशेष रूप से इन प्रकार की समस्याओं को हल करने के लिए डिज़ाइन किए गए हैं।

Answer 2

अनिवार्य शर्तों का मिलान range searching है, विशेष रूप से ऑर्थोगोनल रेंज खोज। प्रासंगिक साहित्य कम्प्यूटेशनल ज्यामिति से संबंधित है। वैकल्पिक स्थितियों से रैंकिंग एक सॉर्टिंग ऑपरेशन है।