İki düğüm bağlıysanız nasıl belirlenir?

oy
13

Bunun bir NP-Tam problem üzerinde çalışıyor olabilir endişeleniyorum. Birinin bunun istenip olmadığına dair bana bir cevap verebilir umut ediyorum. Ve sadece evet ya da hayır daha bir cevap daha arıyorum. Nedenini bilmek istiyorum. Eğer söyleyebiliriz Eğer bu temelde bu sorunun 'x' olduğunu / NP-Complete değildir. (wikipedia bağlantı)

(Hayır bu ödev değildir)

İki nokta keyfi yönlü olmayan grafikte bağlı olup olmadığını belirlemek için bir yol var. örneğin aşağıdaki

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

açık ya da kapalı olabilir Nokta A (Daha 'I') (bir doğal gaz borusu içinde bir valf gibi) kontrol noktaları olsa. '+' In (boru T'nin gibi) düğümleri, ve ben Eh ve Evi aynı zamanda düğümlerin sanırım.

Ben Eh ve Ev hala bağlı olup olmadığını keyfi bir kontrol noktasını (örneğin, C) (diğer kontrol noktaları da kapalı olabilir) kapamak olmadığını bilmek istiyorum. B, K ve D kapalı ise Örneğin, biz hala AEJFCGLM üzerinden bir yol var ve kapanış C Kuyusu ve Ev kesilir. Tabii ki; Sadece eğer D sadece C Evi kesmez kapatarak kapatıldı.

Bunu başka bir şekilde, C, bir köprü / kesme kenar / kıstak mı?

I (açık 0 veya kapalı 1 olarak) grafiğinde bir ağırlık olarak her bir kontrol noktasını tedavi olabilir; ve sonra Kuyusu ve Saray arasındaki en kısa yolu bulmak (Sonuç> = 1 kişilerin bağlantıları olduğunu işaret eder. o 1 ulaştığında ben kısa devre çok kısa yolu bulmak için algoritma (örneğin, bir yol atmak için çeşitli yollar söz var, dur biz Kuyusu ve Evi, vs.) bağlayan HERHANGİ yoluna sahip bir kez. ve tabii ki, ben de vazgeçmeden önce kontrol etmek şerbetçiotu kaç bazı yapay sınırı koyabilirsiniz arıyor.

Birisi sadece adını kaçırıyorum, daha önce de bu tür sorunlar sınıflandırılmış olmalı.

Oluştur 09/12/2008 saat 22:41
kaynak kullanıcı
Diğer dillerde...                            


11 cevaplar

oy
31

Açıklamanız iki düğüm kısa yolu bulmak değil, bağlanmış mı sadece ilgi olduğunu gösteriyor gibi görünüyor.

İki düğüm bağlıysanız bulma nispeten kolaydır:

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.

Eğer bir karma tablo veya toDoSet ve doneSet için benzer bir şey kullanırsanız, bu doğrusal bir algoritma olduğuna inanıyoruz.

Bu algoritma temelde mark-ve-süpürme çöp toplama işareti kısmı olduğuna dikkat edin.

Cevap 09/12/2008 saat 22:52
kaynak kullanıcı

oy
6

Bkz http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , tüm grafik ile ilgili sorunları için tek bir yerden. Ben senin sorunun kuadratik sürede çözülebilir aslında olduğuna inanıyoruz.

Cevap 09/12/2008 saat 22:45
kaynak kullanıcı

oy
5

sizin karmaşıklığına ihtiyaç duyulmayan bir öbek kullanır ve günlük (N) bir faktör tanıtır gibi, bu sorun için Dijkstra'nın algoritması gerekmez. Bu sadece ilk arama breadth edilir - kenarları gibi kapalı kenarları içermez.

Cevap 09/12/2008 saat 23:08
kaynak kullanıcı

oy
3

Kısa yolu bulma problemi NP-tam değildir. O (aslında yeterli) Kısa Yol Problemi denir ve orada algoritmalar bunun birçok farklı halini çözümü için.

iki düğüm bağlanır saptanması problemi ya da NP tam değildir. Bunu diğer düğüme bağlı olup olmadığını belirlemek için düğüm ya başlayan bir derinlik ilk aramayı kullanabilirsiniz.

Cevap 09/12/2008 saat 22:51
kaynak kullanıcı

oy
2

Bir bitişiklik matrisi olduğunu varsayarsak:

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

i ve j ve bool arasında açık bir yolu [i, i] = sahte olup olmadığını BOOL [ij] = true yere.

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;
}

İşte (Ruby ile yazılmış) Yukarıdaki algoritmanın bir özyinelemeli versiyonudur:

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
Cevap 09/12/2008 saat 23:23
kaynak kullanıcı

oy
2

Bana göre sen bir çözüme vardır gibi görünüyor, ama ben sorunu yanlış olabilir. Eğer dediğin gibi yap, ve kapalı kenarları ağırlık olarak 1 verin, sadece Dijkstra'nın algoritması uygulayabilirsiniz http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm . Bu O'da sorunu çözmek gerekir (E * lg (V))

Cevap 09/12/2008 saat 22:49
kaynak kullanıcı

oy
2

değil NP-tam, iyi bilinen bir çözüm ile çözüldü - Dijkstra'nın Algoritma

Cevap 09/12/2008 saat 22:43
kaynak kullanıcı

oy
0

Ben kesinlikle NP-Complete olmadığını cevap var görmek ve bu yanı çok eski bir sorudur.

Ancak, ben sadece sorunun bakmak için başka bir yaklaşım önermek gerekir. Bunun için ayrık setleri kullanabilirsiniz. Çoğu durumda, belirli bir senaryo için, bu yaklaşım bir grafiktir geçişi (O içerir yaparak daha iyi süresine neden olur sabit zaman testleri büyük bir yığın için). Ancak, grafik yapı rütbe veya yol sıkıştırma ile birlik kullanılırsa zaman iyi bir miktar, sürebilir.

Veri Yapısı okuyabilirsiniz burada .

Cevap 03/09/2018 saat 13:36
kaynak kullanıcı

oy
0

İhtiyacınız olan tüm 2 düğümleri grafiği algoritmaları daha hızlıdır ki, bunun yerine setleri kullanabilirsiniz bağlı olup olmadığını belirlemek için ise.

  1. kenarları içine tüm grafiğini bölün. bir dizi her kenar ekleyin.
  2. Bir sonraki tekrarda, orijinal kenar oldu ayarlamak için kenarının 2 dış düğüm arasındaki kenarları 2. adımda bu (karşılık gelen kümeler) ile yeni noktalarının ilave edilmesi anlamına gelir yapılan çizin. (Temelde set birleştirme)
  3. Aradığınız 2 düğümler kadar tekrarlayın 2 aynı grubundad. Ayrıca 1. adımda sonra bir çek yapmanız gerekecektir (her ihtimale karşı 2 düğümleri bitişik).

İlk başta senin düğümleri, kendi kümesinde her olacak

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

Algoritma setleri ilerledikçe ve birleştirir gibi, nispeten girişi yarıya indirir.

Örnekte ben o1 ve o2 arasında bir yol olmadığını görmek için bakıyordu yukarıda. Ben sadece tüm kenarları birleştirdikten sonra sonunda bu yolu buldum. Bazı grafikler Sonunda bir set olması mümkün olmayacaktır gerektirir ki ayrı bileşenler (bağlı) olabilir. Böyle bir durumda size bağlılık için test etmek ve hatta bir grafikte bileşenlerin sayısını saymak için bu algoritmayı kullanabilir. bileşenlerin sayısı algoritması tamamlandığında elde edebiliyoruz setleri sayısıdır.

(Yukarıda ağaç) olası bir grafiktir:

o-o1-o-o-o2
  |    |
  o    o
       |
       o
Cevap 17/12/2011 saat 04:14
kaynak kullanıcı

oy
0

Dijkstra en overkill !! Sadece Ulaşmak istediğiniz düğümü aramak için A'dan Genişlik ilk arama özelliğini kullanın. Eğer bulamıyorsanız, bu bağlı değil. Karmaşıklık O (mil) Dijkstra daha az olan, her bir arama için,.

Biraz ilgili maksimum akış / dakika kesilmiş bir sorundur. o senin sorunun ile ilgili olabilir, onu arayın.

Cevap 12/12/2008 saat 15:11
kaynak kullanıcı

oy
-1

Tek ihtiyacınız bir düğüm başka bağlıysa bulmak için ise herhangi bir grafik en kısa yol algoritması overkill olacak. O gerçekleştirir İyi bir Java kütüphanesidir JGraphT . Bu kullanım burada, oldukça basit bir tamsayı grafiğinin bir örnek var:

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)));
}

Bu lib aynı zamanda tüm kısa yollar algoritmaları sunar.

Cevap 14/11/2016 saat 06:34
kaynak kullanıcı

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