Πώς να καθορίσει εάν συνδέονται δύο κόμβοι;

ψήφοι
13

Είμαι ανησυχούν ότι αυτό μπορεί να εργάζεται σε ένα NP-Complete πρόβλημα. Ελπίζω κάποιος μπορεί να μου δώσει μια απάντηση για το αν είναι ή όχι. Και ψάχνω για περισσότερο από μια απάντηση όχι μόνο ναι ή όχι. Θα ήθελα να ξέρω γιατί. Αν μπορείτε να πείτε, «Αυτό είναι βασικά το πρόβλημα“x”, η οποία είναι / δεν είναι NP-Complete. (Wikipedia link)»

(Όχι αυτό δεν είναι κατ 'οίκον εργασία)

Είναι ένας τρόπος για να καθοριστεί εάν τα δύο σημεία που συνδέονται σε μια αυθαίρετη μη-κατευθυνόμενο γράφημα εκεί. για παράδειγμα, η ακόλουθη

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

Τα σημεία Α και αν Μ (όχι «Ι») είναι σημεία ελέγχου (όπως μια βαλβίδα σε ένα σωλήνα φυσικού αερίου), που μπορεί να είναι είτε ανοικτή ή κλειστή. Οι «+» s είναι κόμβοι (όπως το σωλήνα Τ), και υποθέτω ότι το Πηγάδι και η Βουλή είναι κόμβοι, επίσης, όπως καλά.

Θα ήθελα να ξέρω αν έχω κλείσει ένα αυθαίρετο σημείο ελέγχου (π.χ., C) εάν η Καλά και της Βουλής εξακολουθούν να συνδέονται (άλλα σημεία ελέγχου μπορεί επίσης να είναι κλειστή). Π.χ., αν Β, Κ και D είναι κλειστά, έχουμε ακόμα ένα μονοπάτι μέσα από AEJFCGLM, και το κλείσιμο C θα αποσυνδέσει το Πηγάδι και το Σώμα. Φυσικά; αν απλά D έκλεισε, κλείνοντας μόνο C δεν αποσυνδέει το Σώμα.

Ένας άλλος τρόπος να θέσουμε αυτό, είναι C μια γέφυρα / κομμένη ακμή / ισθμό;

Θα μπορούσα θεραπεία κάθε σημείο ελέγχου σε εκατοστιαία αναλογία βάρους στο γράφημα (είτε 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, πιστεύω ότι αυτό είναι ένα γραμμικό αλγόριθμο.

Σημειώστε ότι ο αλγόριθμος αυτός είναι ουσιαστικά το τμήμα σήμα της συλλογής απορριμμάτων mark-and-sweep.

Απαντήθηκε 09/12/2008 στις 22:52
πηγή χρήστη

ψήφοι
6

Δείτε http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , ένα κατάστημα σας στάση για όλα τα προβλήματα που σχετίζονται με γράφημα. Πιστεύω ότι το πρόβλημά σας είναι στην πραγματικότητα επιλύσιμο σε τετραγωνική χρόνο.

Απαντήθηκε 09/12/2008 στις 22:45
πηγή χρήστη

ψήφοι
5

Δεν χρειάζεται αλγόριθμο του Dijkstra για το πρόβλημα αυτό, καθώς χρησιμοποιεί ένα σωρό που δεν χρειάζεται και εισάγει ένα παράγοντα του log (N) με την πολυπλοκότητα σας. Αυτό ακριβώς αναζήτηση πρώτα κατά βάθος - δεν περιλαμβάνουν τις κλειστές άκρες ως τις άκρες.

Απαντήθηκε 09/12/2008 στις 23:08
πηγή χρήστη

ψήφοι
3

Το πρόβλημα της εύρεσης του συντομότερου μονοπατιού δεν είναι NP-complete. Ονομάζεται το πρόβλημα εύρεσης συντομότερης διαδρομής (αρκετά αρχικά) και υπάρχουν αλγόριθμοι για την επίλυση πολλές διαφορετικές παραλλαγές του.

Το πρόβλημα του καθορισμού αν συνδέονται δύο κόμβοι δεν είναι NP-complete, είτε. Μπορείτε να χρησιμοποιήσετε μια αναζήτηση κατά βάθος ξεκινώντας είτε κόμβο για να διαπιστωθεί εάν είναι συνδεδεμένο με το άλλο κόμβο.

Απαντήθηκε 09/12/2008 στις 22:51
πηγή χρήστη

ψήφοι
2

Αν υποθέσουμε ότι έχετε μια πίνακας γειτνίασης:

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

Σε περίπτωση που bool [i, j] = true αν υπάρχει μια ανοιχτή διαδρομή μεταξύ i και j και bool [i, i] = 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;
}

Εδώ είναι μια αναδρομική έκδοση του αλγορίθμου παραπάνω (γραμμένο σε Ruby):

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 και το βάρος, μπορείτε να εφαρμόσετε μόνο ο αλγόριθμος του Dijkstra, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm . Αυτό θα πρέπει να λύσει το πρόβλημά σας σε O (E * lg (V))

Απαντήθηκε 09/12/2008 στις 22:49
πηγή χρήστη

ψήφοι
2

δεν NP-πλήρης, επιλύεται με ένα καλά-γνωστή λύση - Αλγόριθμος του Dijkstra

Απαντήθηκε 09/12/2008 στις 22:43
πηγή χρήστη

ψήφοι
0

Βλέπω έχετε την απάντησή σας ότι σίγουρα δεν είναι NP-Complete και αυτό είναι ένα πολύ παλιό ζήτημα, καθώς και.

Ωστόσο, εγώ θα προτείνω απλά μια άλλη προσέγγιση για να δούμε το πρόβλημα. Θα μπορούσατε να χρησιμοποιήσετε ξένα σύνολα γι 'αυτό. Στις περισσότερες περιπτώσεις, για το συγκεκριμένο σενάριο, η προσέγγιση θα οδηγήσει σε καλύτερο χρόνο από ό, τι κάνει μια διάσχιση γράφου (Αυτό περιλαμβάνει σταθερά χρόνου για ένα μεγάλο κομμάτι των δοκιμών). Ωστόσο, με βάση τη γραφική παράσταση μπορεί να πάρει καλό χρονικό διάστημα, αν χρησιμοποιείται ένωση από βαθμίδα ή διαδρομή συμπίεσης.

Μπορείτε να διαβάσετε σχετικά με τη δομή των δεδομένων εδώ .

Απαντήθηκε 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

Καθώς ο αλγόριθμος προχωράει και συγχωνεύει τα σύνολα, σχετικά μισά της εισόδου.

Στο παραπάνω παράδειγμα έψαχνα να δω αν υπήρχε ένα μονοπάτι μεταξύ Ο1 και Ο2. Βρήκα αυτό το μονοπάτι μόνο στο τέλος, μετά τη συγχώνευση όλων των άκρων. Μερικά γραφήματα μπορούν να έχουν ξεχωριστές συνιστώσες (αποσυνδεθεί), το οποίο συνεπάγεται ότι δεν θα είναι σε θέση να έχουμε ένα σύνολο στο τέλος. Σε μια τέτοια περίπτωση, μπορείτε να χρησιμοποιήσετε αυτήν τη αλγόριθμο για τον έλεγχο της συνεκτικότητας και ακόμη μετρήσει τον αριθμό των εξαρτημάτων σε ένα γράφημα. Ο αριθμός των στοιχείων είναι ο αριθμός των συνόλων που είναι σε θέση να πάρει, όταν ο αλγόριθμος τελειώνει.

Μια πιθανή γράφημα (για την ανωτέρω δέντρο):

o-o1-o-o-o2
  |    |
  o    o
       |
       o
Απαντήθηκε 17/12/2011 στις 04:14
πηγή χρήστη

ψήφοι
0

Dijkstra είναι υπερβολή !! Απλά χρησιμοποιήστε το εύρος πρώτη έρευνα από το Α για να αναζητήσετε τον κόμβο που θέλετε να φτάσετε. Εάν δεν μπορείτε να το βρείτε, δεν είναι συνδεδεμένο. Πολυπλοκότητα είναι O (nm) για κάθε αναζήτηση, η οποία είναι μικρότερη από Dijkstra.

Κάπως σχετική είναι η μέγιστη ροή / min-κομμένο πρόβλημα. Κοιτάξτε επάνω, θα μπορούσε να είναι σχετικές με το πρόβλημά σας.

Απαντήθηκε 12/12/2008 στις 15:11
πηγή χρήστη

ψήφοι
-1

Κάθε γράφημα αλγόριθμο συντομότερη διαδρομή θα είναι υπερβολή αν το μόνο που χρειάζεται είναι να βρούμε αν ένας κόμβος είναι συνδεδεμένος με ένα άλλο. Μια καλή βιβλιοθήκη Java που επιτυγχάνει αυτό είναι 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