एक टाइमलाइन/क्रोनोलॉजी

Question

के लिए एल्गोरिदम मैं उपन्यासों की एक श्रृंखला की समयरेखा/कालक्रम को कम करने के लिए एल्गोरिदम पर लीड की तलाश में हूं। मैंने ग्रंथों को दिनों में विभाजित कर दिया है और उनके बीच संबंधों का डेटाबेस बनाया है, उदाहरण के लिए: एक्स वाई, वाई और जेड लगातार एक महीने पहले है, ज़ेड की तारीख ज्ञात है, एक्स मंगलवार को है, आदि अनिश्चितता है ('महीने' वास्तव में केवल 30 दिनों का मतलब है) और विरोधाभास भी। मैं कुछ रिश्तों को अस्पष्टता और विरोधाभासों को हल करने में मदद करने के लिए दूसरों की तुलना में अधिक विश्वसनीय के रूप में चिह्नित कर सकता हूं।

इस तरह के डेटा से सर्वोत्तम फिट क्रोनोलॉजी को कम करने के लिए किस प्रकार का एल्गोरिदम मौजूद है, जो प्रत्येक दिन उच्चतम संभाव्यता तिथि निर्दिष्ट करता है? कम से कम समय 1-आयामी है लेकिन असंगतता के साथ जटिल संबंध ग्राफ से निपटना गैर-तुच्छ लगता है। मेरे पास सीएस पृष्ठभूमि है इसलिए मैं कुछ कोड कर सकता हूं लेकिन लागू एल्गोरिदम के नामों के बारे में कुछ विचार उपयोगी होगा। मुझे लगता है कि मेरे पास क्या ग्राफ है जो दिनों के साथ संबंधों के रूप में नोड्स के रूप में है।

Answer 1

बाधा प्रोग्रामिंग आपको जो चाहिए वह है। प्रचार-आधारित सीपी में, आप (ए) खोज पेड़ में वर्तमान विकल्प बिंदु पर निर्णय लेने के बीच वैकल्पिक होते हैं और (बी) जहां तक ​​आप कर सकते हैं उस निर्णय के परिणामों का प्रचार करना। ध्यान दें कि आप प्रत्येक समस्या परिवर्तनीय x के लिए संभावित मानों के D को बनाए रखने के द्वारा ऐसा करते हैं, जैसे कि D(x)x के मानों का सेट है जिसे अभी तक वर्तमान खोज पथ से बाहर नहीं किया गया है। आपकी समस्या में, आप इसे बुलीयन वैरिएबल के बड़े सेट, x_ij पर कम करने में सक्षम हो सकते हैं, जहां x_ij सत्य iff event i ईवेंट j से पहले है। प्रारंभ में D(x) = {true, false} सभी चर के लिए। एक निर्णय केवल एक अनिश्चित चर के डोमेन को कम कर रहा है (एक बूलियन वैरिएबल के लिए इसका मतलब है कि अपने डोमेन को एक मूल्य, सत्य या गलत, जो असाइनमेंट के समान है) को कम करना है। यदि किसी भी x के लिए खोज पथ D(x) खाली हो जाता है, तो आप मृत अंत तक पहुंच गए हैं और बैकट्रैक करना है।

यदि आप स्मार्ट हैं, तो आप प्रत्येक विफलता से सीखने की कोशिश करेंगे और अनावश्यक खोज से बचने के लिए खोज पेड़ के पीछे पीछे हटने की कोशिश करेंगे (इसे बैकजंपिंग - उदाहरण के लिए, यदि आप इसकी पहचान करते हैं स्तर 7 पर पहुंचने वाले मृत अंत के कारण आप स्तर 3 पर किए गए चुनाव के कारण थे, केवल 6 स्तर पर बैकट्रैकिंग में कोई बात नहीं है क्योंकि कोई समाधान इस उपट्री में आपके द्वारा स्तर 3 पर किए गए विकल्प के अनुसार मौजूद है!)।

अब, आपके डेटा में आत्मविश्वास की अलग-अलग डिग्री हैं, तो आपके पास वास्तव में अनुकूलन समस्या है। यही है, आप केवल ऐसे समाधान की तलाश नहीं कर रहे हैं जो को सत्य होना चाहिए, लेकिन एक जो आपके भीतर मौजूद ट्रस्ट की डिग्री के अनुसार अन्य "मुलायम" बाधाओं को सर्वोत्तम रूप से संतुष्ट करता है। आपको यहां क्या करना है उद्देश्य फ़ंक्शन पर संतुष्ट/उल्लंघन किए गए आंशिक बाधाओं के दिए गए सेट पर स्कोर असाइन करना है। जब भी आप पाते हैं कि वर्तमान खोज पथ सबसे पहले मिले समाधान पर बेहतर नहीं हो सकता है तो आप अपनी खोज को छीनना चाहते हैं।

यदि आप बूलियन दृष्टिकोण के लिए जाने का निर्णय लेते हैं, तो आप लाभप्रद रूप से एसएटी सॉल्वर देख सकते हैं, जो इस तरह की समस्याओं से फाड़ते हैं। लेकिन पहली जगह जो मैं देखता हूं वह MiniZinc पर है, एक सीपी भाषा जो कला बाधाओं की पूरी तरह से विभिन्न राज्यों पर आधारित है।

शुभकामनाएँ!

Answer 2

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

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