कैसे निर्धारित करें दो नोड्स जुड़े हुए हैं तो क्या होगा?

वोट
13

मेरा सवाल है कि यह एक एनपी पूरा समस्या पर काम किया जा सकता है कर रहा हूँ। मैं आशा करती हूं कोई मुझे चाहे वह है या नहीं करने के लिए के रूप में एक जवाब दे सकते हैं। और मैं सिर्फ हां या नहीं की तुलना में एक जवाब के और अधिक के लिए देख रहा हूँ। मुझे पता है क्यों चाहते हैं। तो आप कह सकते हैं यह मूल रूप से इस समस्या को 'एक्स' है जो है / एनपी पूर्ण (विकिपीडिया लिंक) नहीं है।

(कोई इस होमवर्क नहीं है)

वहाँ निर्धारित करने के लिए दो अंक एक मनमाना गैर निर्देशित ग्राफ पर जुड़े हुए हैं एक रास्ता है। जैसे, निम्नलिखित

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

अंक एक यद्यपि एम (कोई 'मैं') नियंत्रण अंक (एक प्राकृतिक गैस पाइप में एक वाल्व की तरह) हैं कि या तो खुली या बंद हो सकता है। '+' रों नोड्स (पाइप टी) की तरह हैं, और मैं अच्छी तरह से और सभा कर रहे हैं के रूप में भी अच्छी तरह से नोड लगता है।

मुझे पता है कि अगर मैं एक मनमाना नियंत्रण बिंदु (जैसे, सी) कि क्या ठीक है और हाउस अभी भी जुड़े हुए हैं (अन्य नियंत्रण अंक भी बंद हो सकता है) बंद करना चाहते हैं। उदाहरण के लिए, यदि बी, कश्मीर और डी बंद हो जाती हैं, हम अभी भी एक रास्ता AEJFCGLM के माध्यम से है, और समापन सी अच्छी तरह से और हाउस डिस्कनेक्ट कर देगा। बेशक; अगर सिर्फ विकास बंद हो गया, बंद करने ही सी हाउस डिस्कनेक्ट नहीं है।

इस डालने का एक और तरीका, सी एक पुल / कटौती बढ़त / स्थलडमरूमध्य है?

मैं ग्राफ पर एक वजन के रूप में प्रत्येक नियंत्रण बिंदु का इलाज कर सकता है (या तो या खुले के लिए 0 से बंद के लिए 1); (एक परिणाम और फिर ठीक है और सदन के बीच सबसे कम रास्ता ढूंढने> = 1 संकेत मिलता है कि वे डिस्कनेक्ट हो गए। वहाँ विभिन्न तरीकों से मैं शॉर्ट सर्किट कम से कम पथ बहुत खोजने के लिए एल्गोरिथ्म (जैसे, एक रास्ता त्यागने कर सकते हैं एक बार यह 1 तक पहुँच जाता है, बंद करो सर्च कर रहे हैं एक बार हम किसी भी पथ ठीक है और हाउस, आदि) से जोड़ता है की है। और बेशक, मैं भी कुछ कृत्रिम सीमा में कितने देने से पहले जांच करने के लिए होप्स पर डाल सकते हैं।

किसी ने पहले इस तरह की समस्या में वर्गीकृत किया जाना चाहिए, मैं सिर्फ नाम याद कर रहा हूँ।

09/12/2008 को 22:41
का स्रोत उपयोगकर्ता
अन्य भाषाओं में...                            


11 जवाब

वोट
31

आपका वर्णन संकेत मिलता है कि आप सिर्फ दो नोड्स जुड़े हुए हैं, कम से कम पथ नहीं मिल रहा है कि क्या में रुचि रखते हैं लगता है।

दो नोड्स जुड़े हुए हैं, तो ढूँढना अपेक्षाकृत आसान है:

Create two sets of nodes:  toDoSet and doneSet
Add the source node to the toDoSet 
while (toDoSet is not empty) {
  Remove the first element from toDoList
  Add it to doneList
  foreach (node reachable from the removed node) {
    if (the node equals the destination node) {
       return success
    }
    if (the node is not in doneSet) {
       add it to toDoSet 
    }
  }
}

return failure.

आप एक हैश तालिका या toDoSet और doneSet के लिए कुछ इसी तरह का उपयोग करते हैं, मेरा मानना ​​है कि यह एक रेखीय एल्गोरिथ्म है।

ध्यान दें कि यह एल्गोरिथ्म मूल रूप से निशान और झाडू कचरा संग्रहण का निशान हिस्सा है।

09/12/2008 को 22:52
का स्रोत उपयोगकर्ता

वोट
6

देखें http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , सभी ग्राफ से संबंधित समस्याओं के लिए एक स्टॉप शॉप। मेरा मानना है कि आपकी समस्या तथ्य द्विघात समय में व्याख्या करने योग्य है।

09/12/2008 को 22:45
का स्रोत उपयोगकर्ता

वोट
5

तुम्हें पता है, इस समस्या के लिए डिज्कस्ट्रा एल्गोरिथ्म की जरूरत नहीं, क्योंकि यह आपके जटिलता के एक ढेर जो की जरूरत नहीं है का उपयोग करता है और लॉग (एन) का एक पहलू का परिचय है। यह सिर्फ पहली खोज चौड़ाई है - किनारों के रूप में बंद किनारों शामिल नहीं हैं।

09/12/2008 को 23:08
का स्रोत उपयोगकर्ता

वोट
3

कम से कम पथ खोजने की समस्या एनपी पूरा नहीं हुआ है। यह शोर्टेस्ट पाथ समस्या (मूल रूप से पर्याप्त) कहा जाता है और देखते हैं एल्गोरिदम यह के कई अलग अलग रूपों को सुलझाने के लिए।

दो नोड्स जुड़े हुए हैं, तो निर्धारित करने की समस्या या तो एनपी पूरा नहीं हुआ है। आप या तो नोड पर शुरू करता है, तो यह अन्य नोड से जुड़ा है निर्धारित करने के लिए एक गहराई पहले खोज का उपयोग कर सकते हैं।

09/12/2008 को 22:51
का स्रोत उपयोगकर्ता

वोट
2

मान लें कि आप एक निकटता मैट्रिक्स है:

bool[,] adj = new bool[n, n];

bool [i, j] सच = कहाँ अगर वहाँ मैं और जे और bool बीच एक खुली मार्ग है [मैं, मैं] = false।

public bool pathExists(int[,] adj, int start, int end)
{
  List<int> visited = new List<int>();
  List<int> inprocess = new List<int>();
  inprocess.Add(start);

  while(inprocess.Count > 0)
  {
    int cur = inprocess[0];
    inprocess.RemoveAt(0);
    if(cur == end)
      return true;
    if(visited.Contains(cur))
      continue;
    visited.Add(cur);
    for(int i = 0; i < adj.Length; i++)
      if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i))
        inprocess.Add(i);
  }
  return false;
}

यहाँ से ऊपर (रूबी में लिखा) एल्गोरिथ्म के एक पुनरावर्ती संस्करण है:

def connected? from, to, edges
  return true if from == to
  return true if edges.include?([from, to])
  return true if edges.include?([to, from])

  adjacent = edges.find_all { |e| e.include? from }
                  .flatten
                  .reject { |e| e == from }

  return adjacent.map do |a|
    connected? a, to, edges.reject { |e| e.include? from }
  end.any?
end
09/12/2008 को 23:23
का स्रोत उपयोगकर्ता

वोट
2

मेरे लिए यह लगता है कि आप समाधान के प्रयास जारी हैं, लेकिन यह मैं इस समस्या को गलत समझा संभव है। यदि आप आप की तरह कहते हैं करते हैं, और बंद किनारों 1 वजन के रूप में देते हैं, तो आप सिर्फ डिज्कस्ट्रा एल्गोरिथ्म, आवेदन कर सकते हैं http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm । यह हे में आपकी समस्या का समाधान करना चाहिए (ई * एलजी (वी))

09/12/2008 को 22:49
का स्रोत उपयोगकर्ता

वोट
2

नहीं एन पी-सम्पूर्ण, एक प्रसिद्ध समाधान के साथ हल - डिज्कस्ट्रा के एल्गोरिथ्म

09/12/2008 को 22:43
का स्रोत उपयोगकर्ता

वोट
0

मैं तुम्हें अपने जवाब मिल गया है कि यह निश्चित रूप से नहीं एनपी पूरा है देख सकते हैं और यह एक बहुत पुरानी सवाल भी है।

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

आप डेटा संरचना के बारे में पढ़ सकते हैं यहाँ

03/09/2018 को 13:36
का स्रोत उपयोगकर्ता

वोट
0

आप सभी की जरूरत निर्धारित करने के लिए 2 नोड्स जुड़े हुए हैं, तो आप के बजाय सेट का उपयोग कर सकते हैं, जो ग्राफ एल्गोरिथम की तुलना में तेजी से होता है है।

  1. किनारों में अपने पूरे ग्राफ विभाजित करें। एक सेट करने के लिए प्रत्येक बढ़त जोड़ें।
  2. अगले चरण पर, सेट मूल किनारे से था बढ़त के 2 बाहरी नोड्स के बीच किनारों चरण 2. (उनकी संगत सेट के साथ) नई नोड्स जोड़ने इसका मतलब यह है में किया आकर्षित। (मूल रूप से सेट विलय)
  3. दोहराएँ 2 2 नोड्स आप देख रहे हैं जब तक एक ही सेट में हैं। तुम भी चरण 1 के बाद एक जांच करने की आवश्यकता होगी (बस मामले में 2 नोड्स निकट हैं)।

सबसे पहले अपने नोड्स अपने सेट में प्रत्येक हो जाएगा,

o   o1   o   o   o   o   o   o2
 \ /     \ /     \ /     \ /
 o o     o o     o o     o o
   \     /         \     /
   o o o o         o o o o 
      \               /
       o o1 o o o o o o2

एल्गोरिथ्म प्रगति होती है और सेट विलीन हो जाती है के रूप में, यह अपेक्षाकृत इनपुट आधा कर देगा।

उदाहरण में ऊपर मैं अगर वहाँ O1 और O2 के बीच एक रास्ता था देखने के लिए देख रहा था। मैं केवल सभी किनारों विलय करने के बाद अंत में इस मार्ग मिल गया। कुछ रेखांकन जो जरूरत पर जोर देता है कि आप अंत में एक सेट करने के लिए सक्षम नहीं होगा अलग घटकों (काट दिया) हो सकता है। इस तरह के एक मामले में आप संयुक्तता के लिए परीक्षण करने के लिए और यहां तक ​​कि एक ग्राफ में घटकों की संख्या की गिनती इस एल्गोरिथ्म का उपयोग कर सकते हैं। घटकों की संख्या सेट की संख्या आप जब एल्गोरिथ्म खत्म प्राप्त करने में सक्षम हो रहा है।

एक संभावित ग्राफ (ऊपर पेड़ के लिए):

o-o1-o-o-o2
  |    |
  o    o
       |
       o
17/12/2011 को 04:14
का स्रोत उपयोगकर्ता

वोट
0

डिज्कस्ट्रा के overkill है !! बस नोड तक पहुंचना चाहते हैं के लिए खोज करने के लिए एक से चौड़ाई पहले खोज का उपयोग करें। आप यह नहीं मिल रहा है, यह कनेक्ट नहीं है। जटिलता है हे (एनएम) प्रत्येक खोज है, जो कम डिज्कस्ट्रा है के लिए।

कुछ हद तक संबंधित अधिकतम प्रवाह / मिनट कटौती समस्या है। यह देखो ऊपर, यह आपकी समस्या के लिए प्रासंगिक हो सकता है।

12/12/2008 को 15:11
का स्रोत उपयोगकर्ता

वोट
-1

किसी भी ग्राफ कम से कम पथ एल्गोरिथ्म overkill हो सकता है अगर आप सभी की जरूरत है, तो एक नोड एक और से जुड़ा है मिल रहा है। एक अच्छा जावा पुस्तकालय है कि पूरा करता है JGraphT । यह उपयोग काफी सरल है, यहाँ एक पूर्णांक ग्राफ का एक उदाहरण है:

public void loadGraph() {
    // first we create a new undirected graph of Integers
    UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);

    // then we add some nodes
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addVertex(4);
    graph.addVertex(5);
    graph.addVertex(6);
    graph.addVertex(7);
    graph.addVertex(8);
    graph.addVertex(9);
    graph.addVertex(10);
    graph.addVertex(11);
    graph.addVertex(12);
    graph.addVertex(13);
    graph.addVertex(14);
    graph.addVertex(15);
    graph.addVertex(16);

    // then we connect the nodes
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(5, 6);
    graph.addEdge(6, 7);
    graph.addEdge(7, 8);
    graph.addEdge(8, 9);
    graph.addEdge(9, 10);
    graph.addEdge(10, 11);
    graph.addEdge(11, 12);
    graph.addEdge(13, 14);
    graph.addEdge(14, 15);
    graph.addEdge(15, 16);

    // finally we use ConnectivityInspector to check nodes connectivity
    ConnectivityInspector<Integer, DefaultEdge> inspector = new ConnectivityInspector<>(graph);

    debug(inspector, 1, 2);
    debug(inspector, 1, 4);
    debug(inspector, 1, 3);
    debug(inspector, 1, 12);
    debug(inspector, 16, 5);
}

private void debug(ConnectivityInspector<Integer, DefaultEdge> inspector, Integer n1, Integer n2) {
    System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2)));
}

इस lib के रूप में भी अच्छी तरह से सभी कम से कम पथ एल्गोरिदम प्रदान करता है।

14/11/2016 को 06:34
का स्रोत उपयोगकर्ता

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more