(का सेट) सेट की सूची (कार्तीय उत्पाद (ओं)) सूचियों

Question

की सूचियों के सेट (ए) सेट करने के लिए इसी:

{[a,b,d,f], 
[a,c,d,f], 
[a,b,e,f], 
[a,c,e,f]} 

जहां ए, बी, सी, डी, ई और च आइटम (एक शब्द में जरूरी नहीं कि वर्ण), एक निर्देशित अचक्रीय ग्राफ के रूप में शामिल होती जा सकता है (DAG, बी, बाएं से सभी किनारों बिंदु - सही करने के लिए>):

b-->d 
/\/\ 
a X f 
\/\/
    c-->e 

या की कार्तीय उत्पाद के रूप में वस्तुओं के 4 सेट (सी, अक्ष अक्ष कहा गया):

{a} * {b,c} * {d, e} * {f} 

गुवा के सेट (सी) की सूची से सूचियों (ए) का एक सेट उत्पन्न करने के लिए method अच्छा है।

मैं एक एल्गोरिदम की कोशिश कर रहा हूं जो बी जैसे ग्राफ को स्वीकार करता है और सी (वास्तव में एक या अधिक, नीचे उदाहरण देखें) की अक्ष की एक सूची देता है, जिसका उपयोग उपरोक्त विधि के साथ किया जा सकता है ताकि सूचियों का एक सेट उत्पन्न हो सके। ए

हालांकि, यह गारंटी नहीं है कि सूचियों का सेट कार्टेशियन उत्पाद होगा। उदाहरण के लिए:

{[a,b,d,f], 
-missing- 
[a,b,e,f], 
[a,c,e,f]} 

DAG करने के लिए इसी:

b-->d 
/\ \ 
a \ f 
\ \/
    c-->e 

कार्तीय उत्पाद के रूप में व्यक्त नहीं किया जा सकता, लेकिन के रूप में 2 व्यक्त किया जा सकता:

{a}*{b}*{d,e}*{f} and {a}*{c}*{e}*{f} 

रेखांकन करने के लिए इसी:

 d 
    /\ 
a-->b f   and  a-->c-->e-->f 
    \/
     e 

सूचियों में कुछ डिग्री की प्रासंगिकता होनी चाहिए (सोचें: एक बहुत बड़े कार्टेशियन उत्पाद का एक यादृच्छिक नमूना)।

नोट: विभिन्न लंबाई की सूचियां अक्ष के समान सेट को साझा नहीं कर सकती हैं।

क्या कोई एल्गोरिदम है जो यह करता है और मैंने अभी सही शर्तों को गुगल नहीं किया है? यदि नहीं, तो क्या हम इसे बना सकते हैं?

एल्गोरिदम की जटिलता एक मुद्दा हो सकता है क्योंकि सेट में 10^2 सूचियां हो सकती हैं और प्रत्येक सूची में 10^2 आइटम हो सकते हैं, यानी काफी बड़ा ग्राफ। मैं गारंटी दे सकता हूं कि इनपुट ग्राफ़ में सूचियों के सेट का प्रतिनिधित्व करने के लिए न्यूनतम संख्या में नोड्स संभव होंगे ..., और उस गैर-ब्रांचिंग नोड्स (ए-> सी-> ई-> एफ) को सिंगल में जोड़ा जा सकता है वस्तुओं (एसीएफ)।

पीएस। मुझे नहीं लगता कि यह Cartesian product of graphs जैसा ही है, लेकिन कुछ ओवरलैप हो सकता है।

Answer 1

यदि मैं आपके प्रश्न को सही ढंग से समझता हूं, तो आप (ए) के बाद हैं और केवल एक मध्यवर्ती चरण के रूप में (सी) चाहते हैं। उदाहरण के प्रयोग से ग्राफ के माध्यम से shortest paths उत्पन्न करें Dijkstra's algorithm - यह सूचियों (ए) का सेट उत्पन्न करेगा। यदि आपको अभी भी इस बिंदु पर कार्टेशियन उत्पाद की आवश्यकता है (यानी यदि आप कार्टेसियन उत्पाद को उत्पन्न करने के लिए मध्यवर्ती चरण के रूप में उत्पन्न नहीं कर रहे थे (ए)) तो इसे (ए) से (ए) से उत्पन्न करना बहुत आसान है।