Làm thế nào để tìm tất cả bằng đường dẫn trong cây thoái hóa, bắt đầu trên đỉnh cụ thể?

Question

Tôi có một số degenerate tree (có vẻ như mảng hoặc danh sách được liên kết kép). Ví dụ: cây này là:

Mỗi cạnh có một số trọng lượng. Tôi muốn tìm tất cả các đường bằng nhau, bắt đầu từ mỗi đỉnh.

Nói cách khác, tôi muốn nhận tất cả các bộ dữ liệu (v1, v, v2) trong đó v1 và v2 là một tổ tiên tùy ý và hậu duệ sao cho số c(v1, v) = c(v, v2).

Hãy cạnh có trọng số như sau (nó chỉ là ví dụ):

a-b = 3

b-c = 1

c-d = 1

d-e = 1

Sau đó:

1. Đỉnh A không có đường dẫn bằng nhau (không có đỉnh từ bên trái).
2. Đỉnh B có một cặp bằng nhau. Đường dẫn B-A tương đương với đường dẫn B-E(3 == 3).
3. Đỉnh C có một cặp bằng nhau. Đường dẫn B-C bằng với đường dẫn C-D(1 == 1).
4. Đỉnh D có một cặp bằng nhau. Đường dẫn C-D bằng với đường dẫn D-E(1 == 1).
5. Đỉnh E không có bất kỳ đường dẫn nào bằng nhau (không có đỉnh từ bên phải).

Tôi triển khai thuật toán đơn giản, hoạt động trong O(n^2). Nhưng nó quá chậm đối với tôi.

Answer 1

Bạn viết, trong ý kiến, đó là cách tiếp cận hiện tại của bạn là

Dường như, tôi đang tìm kiếm một cách để giảm liên tục trong thời gian O (n^2). Tôi chọn một số đỉnh. Sau đó, tôi tạo ra hai bộ. Sau đó, tôi điền vào các bộ này với khoản tiền một phần, trong khi lặp lại từ đỉnh này để bắt đầu của cây và để kết thúc cây . Sau đó, tôi tìm giao lộ đã đặt và nhận số đường dẫn từ đỉnh này. Sau đó, tôi lặp lại thuật toán cho tất cả các đỉnh khác.

Có một cách tiếp cận đơn giản và nhanh hơn, tôi nghĩ, nhanh hơn O(n^2), dựa trên phương pháp được gọi là hai con trỏ.

Đối với mỗi đỉnh v đồng thời đi theo hai hướng có thể.Có một "con trỏ" tới một đỉnh (vl) di chuyển theo một hướng và một hướng khác (vr) theo một hướng khác và cố gắng giữ khoảng cách từ v đến vl gần với khoảng cách từ v đến vr càng tốt. Mỗi khi những khoảng cách này trở nên bằng nhau, bạn có các đường bằng nhau.

for v in vertices 
    vl = prev(v) 
    vr = next(v) 
    while (vl is still inside the tree) 
       and (vr is still inside the tree) 
     if dist(v,vl) < dist(v,vr) 
      vl = prev(vl) 
     else if dist(v,vr) < dist(v,vl) 
      vr = next(vr) 
     else // dist(v,vr) == dist(v,vl) 
      ans = ans + 1 
      vl = prev(vl) 
      vr = next(vr) 

(By precalculating số tiền tiền tố, bạn có thể tìm dist trong thời gian O (1).)

Thật dễ dàng để thấy rằng không có cặp tương đương sẽ được bỏ qua với điều kiện là bạn không cần phải cạnh zero-length .

Về một giải pháp nhanh hơn, nếu bạn muốn danh sách tất cả các cặp, thì bạn không thể làm điều đó nhanh hơn, vì số lượng các cặp sẽ được O (n^2) trong trường hợp xấu nhất. Nhưng nếu bạn chỉ cần số tiền của các cặp này, có thể tồn tại các thuật toán nhanh hơn.

UPD: Tôi đã đưa ra một thuật toán khác để tính số tiền , có thể nhanh hơn trong trường hợp các cạnh của bạn khá ngắn. Nếu bạn biểu thị tổng chiều dài của chuỗi (tổng của tất cả các cạnh trọng lượng) là L, thì thuật toán sẽ chạy trong O(L log L). Tuy nhiên, nó tiên tiến hơn nhiều về mặt khái niệm và tiên tiến hơn trong quá trình viết mã.

Trước hết là một số lý luận lý thuyết. Xem xét một số đỉnh v. Hãy để chúng tôi có hai mảng, a và b, không phải là các mảng được lập chỉ mục kiểu zero, nhưng các mảng có chỉ mục từ -L đến L.

Chúng ta hãy xác định

• cho i>0, a[i]=1 iff đến đúng của v vào khoảng cách chính xác i có là một đỉnh, nếu không a[i]=0
• cho i=0, a[i]≡a[0]=1
• cho i<0 , a[i]=1 iff đến bên trái trong số v vào khoảng cách chính xác -i có một đỉnh, nếu không a[i]=0

Một sự hiểu biết đơn giản của mảng này là như sau. Kéo biểu đồ của bạn và đặt nó dọc theo trục tọa độ sao cho mỗi cạnh có chiều dài bằng với trọng số của nó và đỉnh đó v nằm ở gốc. Sau đó a[i]=1 iff có một đỉnh tại tọa độ i.

Ví dụ bạn và cho đỉnh "b" chọn làm v:

  a--------b--c--d--e 
    --|--|--|--|--|--|--|--|--|--> 
     -4 -3 -2 -1 0 1 2 3 4 
a: ... 0 1 0 0 1 1 1 1 0 ... 

Đối với mảng khác, mảng b, chúng tôi xác định các giá trị trong một cách đối xứng đối với nguồn gốc với, như thể chúng tôi đã đảo ngược sự hướng trục:

• cho i>0, b[i]=1 iff đến trái của v vào khoảng cách chính xác i có là một đỉnh, nếu không b[i]=0
• cho i=0, b[i]≡b[0]=1
• cho i<0, b[i]=1 iff đến đúng của v vào khoảng cách chính xác -i có một đỉnh, nếu không b[i]=0

Bây giờ hãy xem xét một mảng thứ ba c sao cho c[i]=a[i]*b[i], dấu hoa thị ở đây vẫn cho phép nhân thường. Rõ ràng là c[i]=1 iff đường dẫn có độ dài abs(i) đến đầu bên trái trong một đỉnh và đường dẫn có chiều dài abs(i) đến đầu bên phải trong một đỉnh. Vì vậy, đối với i>0 mỗi vị trí trong c có c[i]=1 tương ứng với đường dẫn bạn cần. Ngoài ra còn có các vị trí phủ định (c[i]=1 với i<0), chỉ phản ánh các vị trí dương và một vị trí khác trong đó c[i]=1, cụ thể là vị trí i=0.

Tính tổng của tất cả các phần tử trong c. Số tiền này sẽ là sum(c)=2P+1, trong đó P là tổng số đường dẫn bạn cần với v làm trung tâm của nó. Vì vậy, nếu bạn biết sum(c), bạn có thể dễ dàng xác định P.

Bây giờ chúng ta xem xét các mảng chặt chẽ hơn a và b và cách chúng thay đổi khi chúng ta thay đổi đỉnh v. Hãy để chúng tôi biểu thị v0 đỉnh ngoài cùng bên trái (gốc cây của bạn) và a0 và b0 các mảng a và b tương ứng cho đỉnh đó.

Đối với đỉnh tùy ý v biểu thị d=dist(v0,v). Sau đó, nó rất dễ dàng để thấy rằng đối với đỉnh v các mảng a và b chỉ là mảng a0 và b0 chuyển bởi d:

a[i]=a0[i+d] 
b[i]=b0[i-d] 

Rõ ràng nếu bạn nhớ những bức tranh với cây trải dài dọc theo một trục tọa độ.

Bây giờ chúng ta hãy xem xét một mảng hơn, S (một mảng cho tất cả các đỉnh), và đối với mỗi đỉnh v chúng ta hãy đặt giá trị của sum(c) vào S[d] yếu tố (d và c phụ thuộc vào v).

Chính xác hơn, chúng ta hãy xác định mảng S để cho mỗi d

S[d] = sum_over_i(a0[i+d]*b0[i-d]) 

Một khi chúng ta biết các mảng S, chúng ta có thể lặp trên đỉnh và đối với mỗi đỉnh v lấy nó sum(c) đơn giản là S[d] với d=dist(v,v0), vì mỗi đỉnh v chúng tôi có sum(c)=sum(a0[i+d]*b0[i-d]).

Nhưng công thức cho S rất đơn giản: S chỉ là convolution trong số các chuỗi a0 và b0. (Công thức không chính xác theo định nghĩa, nhưng rất dễ sửa đổi thành dạng định nghĩa chính xác.)

Vì vậy, những gì chúng ta cần được cung cấp a0 và b0 (mà chúng tôi có thể tính toán trong thời gian và không gian), tính toán S mảng. Sau đó, chúng ta có thể lặp qua mảng S và chỉ cần trích xuất số lượng đường dẫn từ S[d]=2P+1.

Áp dụng trực tiếp công thức trên là O(L^2). Tuy nhiên, sự kết hợp của hai chuỗi can be calculated in O(L log L) bằng cách áp dụng thuật toán biến đổi Fast Fourier. Hơn nữa, bạn có thể áp dụng một Number theoretic transform tương tự (không biết liệu có một liên kết tốt hơn) để làm việc với chỉ số nguyên và tránh các vấn đề về độ chính xác.

Vì vậy, đề cương chung của thuật toán trở nên

calculate a0 and b0 // O(L) 
calculate S = corrected_convolution(a0, b0) // O(L log L) 
v0 = leftmost vertex (root) 
for v in vertices: 
    d = dist(v0, v) 
    ans = ans + (S[d]-1)/2 

(tôi gọi nó corrected_convolution vì S là không chính xác một chập, nhưng một đối tượng rất giống nhau mà một thuật toán tương tự có thể được áp dụng. Hơn nữa, bạn có thể thậm chí xác định S'[2*d]=S[d]=sum(a0[i+d]*b0[i-d])=sum(a0[i]*b0[i-2*d]), và sau đó S' là chập chững phù hợp.)