Temukan titik sudut pada jarak d

Saya memiliki pohon dengan N simpul. Saya ingin merancang suatu algoritma untuk menjawab beberapa pertanyaan dengan cepat. Mengingat simpul V dan bilangan bulat d, saya ingin mencari simpul pada jarak d dari V. Jika ada lebih dari satu simpul pada jarak d maka keluaran apa saja. Saya jelas tahu cara melakukan kekerasan. Saya juga mencoba beberapa ide yang mirip dengan algoritma pencarian LCA (menghitung leluhur pada jarak 1, 2, 4, 8...), tetapi tidak ada hasil.

Saya akan memiliki banyak pertanyaan, seperti 10^6, jadi saya ingin menjawabnya dalam waktu O(1) atau O(log N)


algorithm graph-theory
person user128409235    schedule 21.01.2016    source sumber
comment
Untuk menemukan suatu titik pada jarak tertentu, Anda cukup mengulang semua titik dan mengujinya. Untuk kueri yang lebih kompleks - seperti k-titik terdekat dan sejenisnya, gunakan pohon kd, pohon rentang, atau struktur data serupa lainnya.   -  person Jaa-c    schedule 21.01.2016
comment
Mengapa solusi seperti LCA tidak berhasil?   -  person Sorin    schedule 21.01.2016
comment
Karena menghitung jarak ke nenek moyang, bukan ke keturunan.   -  person user128409235    schedule 21.01.2016
comment
Apakah Anda menginginkan sebuah simpul yang memiliki jalur d tepi antara simpul tersebut dan akarnya atau Anda ingin jarak minimumnya adalah d? Yaitu. Jika terdapat jalur a->b->c->d->e->f->g dan a->g maka apakah simpul g berjarak 6 dari simpul a atau hanya berjarak 1 (atau dapatkah kedua jarak tersebut)?   -  person MT0    schedule 21.01.2016
comment
@MT0 di pohon, jalur (sederhana) antar simpul adalah unik. Jadi situasi seperti itu tidak bisa terjadi   -  person Niklas B.    schedule 21.01.2016
comment
@NiklasB. Ah iya. Saya melewatkan satu kata yang sangat penting itu.   -  person MT0    schedule 21.01.2016

Jawaban (4)


arrow_upward
1
arrow_downward

Pendekatan ini akan berhasil

  1. Hitung pusat massa jalur terpanjang pada pohon. Untuk melakukannya, gunakan penelusuran depth-first untuk menemukan titik x di mana kedalaman titik maksimum pada pohon yang berakar di x adalah minimal
  2. Hitung kedalaman semua simpul pada pohon yang berakar di x menggunakan traversal pohon sederhana
  3. Kelompokkan kueri berdasarkan indeks komponen yang terhubung ke dalam kuerinya jika x dihapus
  4. Ulangi semua kueri berdasarkan komponen. Katakanlah kueri Anda adalah (v, d). Jika kedalaman(v) ‹= d, maka Anda cukup menggunakan nenek moyang ke-d dari v sebagai jawabannya, menggunakan pendekatan standar di O(log n). Jika tidak, periksa apakah ada titik solusi w dengan path(v, w) melintasi x dan dist(v, w) = d dengan mencari kedalaman d - depth(v) pada salah satu komponen lainnya (misalnya pada O( 1) melalui hashing)

Ini berfungsi karena jika ada jawaban untuk pertanyaan (v, d) dengan kedalaman(v) >= d, maka ada jalur dengan panjang d mulai dari v yang melintasi x, karena sifat x.

Anda dapat menerapkan langkah 1 dan 2 menggunakan pencarian mendalam pertama.

Untuk langkah 4, Anda ingin menyimpan tabel hash yang mengaitkan kedalaman dengan simpul sedemikian rupa sehingga Anda dapat menghapus dan menambahkan simpul di O(1). Kemudian Anda dapat melakukannya dalam waktu linier saat mengerjakan komponen demi komponen.

Total waktu berjalan adalah O((n + q) * log n).

Hal ini dapat dilakukan secara online dengan menghitung terlebih dahulu struktur data kedalaman dari langkah 4 menggunakan pohon pencarian biner persisten, sekali lagi dalam O(log n) per kueri.

person Niklas B.    schedule 21.01.2016
comment
Setelah menghapus x, apakah saya harus mencari centroid di komponen yang terhubung? - person user128409235; 21.01.2016
comment
@ user128409235 Setelah menghapus x, cukup terapkan algoritma secara rekursif ke setiap komponen yang terhubung. Jadi ya, itu melibatkan pencarian pusat massa setiap CC - person Niklas B.; 21.01.2016
comment
Hm... bukankah cukup hanya mencari pusat massa, membuat array simpul vektor‹int›simpul[N], dan menyimpannya dalam simpul[1] simpul pada jarak 1, simpul[2] menyimpannya pada jarak 2 dan seterusnya. dan juga jalur terpanjang dari centroid lalu menjawab setiap pertanyaan di O(1)? - person user128409235; 21.01.2016
comment
@ user128409235 Saya rasa Anda benar, sebenarnya kita tidak memerlukan rekursi. Namun, kita perlu memilih x yang sedikit berbeda agar ini berfungsi (lihat edit). Dan kita perlu menangani kasus di mana untuk query (v, d), depth(v) ‹= d, yaitu jawabannya adalah leluhur ke-d. Itu bisa dilakukan di O(1), tapi rumit. O(log n) jauh lebih sederhana - person Niklas B.; 21.01.2016

arrow_upward
0
arrow_downward

Tambahkan bobot pada setiap tepi pohon sesuai dengan jumlah keturunannya. Ini hanya dapat dilakukan sekali dan bernilai O(N)

Jika Anda hanya ingin mencari titik pada jarak tertentu d Anda dapat melakukannya dalam langkah O(d) hanya dengan berjalan di pohon ke atas dan akhirnya ke bawah, segera setelah Anda temukan cabang dengan bobot yang cukup tinggi untuk mencapai d langkah.

Jika Anda melakukan banyak pertanyaan pada pohon yang sama, kinerjanya akan sangat baik.

person Sklivvz    schedule 21.01.2016
comment
Sangat mudah untuk merancang kelas input di mana algoritma yang Anda usulkan akan memiliki waktu berjalan Omega(q*n) di mana q adalah jumlah kueri. Misalnya, bagaimana jika pohon hanyalah sebuah jalur dengan panjang n dan semua kueri berada di salah satu titik akhir? - person Niklas B.; 21.01.2016
comment
Dalam hal ini setiap kueri akan mengambil O(d) bukan O(N). satu-satunya kasus di mana kita perlu menelusuri seluruh pohon adalah ketika d = N - person Sklivvz; 21.01.2016
comment
Ya, jadi setiap kueri adalah (1, N - 1) dan Anda memiliki sisi 1 - 2 - 3 - ... - N - person Niklas B.; 21.01.2016
comment
@NiklasB. Bisakah Anda menjelaskan diri Anda dengan lebih baik? Apa arti setiap kueri (1,N)? ada elemen N di pohon, kueri q, masing-masing dengan jarak d tertentu (yang kurang dari atau sama dengan N). Algoritma ini berfungsi sebagai O(q * d) yang lebih kecil atau sama dengan O(q * N). - person Sklivvz; 21.01.2016
comment
tentu saja, tetapi OP menginginkan algoritma O(N + q) atau O((N + q) log N). Sekadar menunjukkan bahwa pendekatan ini memiliki kasus terburuk Ω(N) waktu per kueri - person Niklas B.; 21.01.2016
comment
@NiklasB.Saya melihatnya sebagai O(N) untuk setiap kueri, tidak masuk akal untuk menanyakan sebaliknya (tentunya Anda perlu menjawab setiap kueri setidaknya sekali!) - person Sklivvz; 21.01.2016
comment
Ya, tetapi mungkin saja Anda dapat menyelesaikan kueri misalnya dalam waktu O(log N) setelah beberapa pemrosesan awal dalam waktu O(N log N) atau kurang. Itulah gunanya struktur data - person Niklas B.; 21.01.2016
comment
Mari kita melanjutkan diskusi ini dalam chat. - person Sklivvz; 21.01.2016

arrow_upward
0
arrow_downward

Saat membuat tautan grafik/penambahan, untuk node tertentu Anda dapat menyimpan peta tepi untuk Vertex tersebut, dengan jarak sebagai kuncinya dan tepi pada jarak tersebut sebagai nilai. Dengan cara ini Anda dapat membangun dan mengambil di O(1)

class Vertex{
  String vertexLabel;
  Map<Integer,List<Edge> edgeMap;
}
person Pranalee    schedule 21.01.2016

arrow_upward
-1
arrow_downward

Jalankan algoritma Floyd – Warshall satu kali pada grafik Anda untuk menghitung jalur terpendek antara semua pasangan, lalu gunakan ini? Mungkin pencarian mendalam pertama yang dimulai dari V dan berhenti di kedalaman d sudah cukup, bergantung pada berapa banyak kueri yang ingin Anda lakukan.

person manuBriot    schedule 21.01.2016
comment
Ini adalah algoritma brute force, dan saya mencari O(n) atau O(n log n) - person user128409235; 21.01.2016
comment
depth-first-search akan menjadi O(n) (dan kemungkinan lebih kecil bergantung pada d), karena semua simpul dikunjungi paling banyak satu kali. - person manuBriot; 21.01.2016