Tính toán khoảng cách xã hội giữa hai người dùng

Question

Cách bạn viết mã một thuật toán hiệu quả có thể trả về khoảng cách xã hội '' giữa hai người dùng.

Ví dụ: khi bạn truy cập tiểu sử trên LinkedIn, bạn có thể thấy khoảng cách giữa bạn và người dùng là bao nhiêu.

-> user A là người bạn với người sử dụng B - và B là bạn thân với C. khi A sẽ thăm C (khoảng cách sẽ là 1)

Đồ thị là rất lớn và vì vậy tôi đang tự hỏi làm thế nào nó có thể được thực hiện rất nhanh.

Tôi biết rằng câu hỏi này có thể bị đóng nhưng tôi thực sự nghĩ đó là câu hỏi lập trình/thuật toán - Tôi sẽ không chỉ định bất kỳ ngôn ngữ nào vì tôi quan tâm đến khái niệm.

Answer 1

giả sử bạn không có bất kỳ heuristic function về khoảng cách đến mục tiêu, giải pháp tốt nhất đó là hợp lệ là bi-directionalBFS:
Algorithm ý tưởng: thực hiện tìm kiếm BFS đồng thời từ nguồn và mục tiêu: [BFS cho đến độ sâu 1 ở cả hai, cho đến độ sâu 2 ở cả hai, ....].
Thuật toán sẽ kết thúc khi bạn tìm thấy v đỉnh, nằm ở cả hai mặt trước của BFS.

Hành vi thuật toán: Đỉnh v kết thúc chạy thuật toán sẽ chính xác ở giữa nguồn và đích.
Thuật toán này sẽ mang lại kết quả tốt hơn nhiều trong hầu hết các trường hợp sau đó BFS từ nguồn [giải thích tại sao nó tốt hơn BFS sau], và chắc chắn sẽ cung cấp câu trả lời, nếu có.

tại sao nó tốt hơn BFS từ nguồn?
giả định khoảng cách giữa nguồn đến đích là k và hệ số nhánh là B [mỗi đỉnh có B cạnh].
BFS sẽ mở: 1 + B + B^2 + ... + B^k đỉnh.
BFS hai hướng sẽ mở: 2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2) đỉnh.

cho lớn B và k, thứ hai rõ ràng là tốt hơn nhiều so với lần đầu tiên.

EDIT:
Chú ý, rằng giải pháp này không yêu cầu lưu trữ toàn bộ đồ thị trong bộ nhớ, nó chỉ yêu cầu thực hiện một chức năng: successor(v) mà trả về tất cả những người thừa kế của một đỉnh [tất cả các đỉnh bạn có thể tới, trong vòng 1 bước từ v]. Với điều này, chỉ các nút bạn mở [2 + 2B + ... + 2B^(k/2) như được giải thích ở trên] phải được lưu trữ. Để tiết kiệm hơn nữa bộ nhớ, bạn có thể sử dụng Iterative Deepening DFS từ một hướng, thay vì BFS, nhưng nó sẽ tiêu tốn nhiều thời gian hơn.

Answer 2

Tôi đã giả định rằng điều này sẽ được thực hiện bằng cách áp dụng thuật toán đường đi ngắn nhất, chẳng hạn như breadth first search đến graph database. Nhưng chúng xuất hiện để lưu trữ toàn bộ biểu đồ của chúng trong bộ nhớ, ít nhất là theo this.

Tôi chắc chắn rằng thuật toán cuối cùng sẽ chuyển thành một số hình thức đường đi ngắn nhất trên cấu trúc biểu đồ (các nút và cạnh).

Chỉnh sửa: Đã thay đổi thuật toán theo nhận xét.

Answer 3

Trước tiên, biểu đồ cần được điền. Tôi không thể nói về cách bạn có được đồ thị từ liên kết trong, có thể làm cho một BFS hoặc DFS của các nút, khám phá các đồ thị, và thiết lập các liên kết. Để tìm khoảng cách giữa hai cách tốt nhất là tạo BFS từ nút nguồn và dừng khi tìm thấy đích. Các liên kết không có trọng số, tôi nghĩ, nếu bạn không ngụ ý điều gì đó khác.

Trong trường hợp này, bạn cần áp dụng BFS cho mỗi khoảng cách để tìm khoảng cách giữa mỗi cặp, khi nút nguồn khác nhau. Khác, bạn có thể thực hiện thuật toán Floyd Warshall để có được tất cả nguồn tất cả các đường dẫn đích ngắn nhất, và bởi vì mỗi liên kết có cùng trọng số nó sẽ có được những gì bạn muốn. Trong trường hợp này một khi cấu trúc được tạo, cho bất kỳ nguồn và đích nào, khoảng cách ngắn nhất có thể được tìm thấy. Một vấn đề là mạng luôn thay đổi do đó cần xử lý lại. Do đó BFS tôi nghĩ sẽ tốt.

Để xử lý nhanh hơn, bạn có thể triển khai BFS để chạy song song. Hãy xem Design and analysis of a nondeterministic parallel breadth-first search algorithm