Tôi đã chơi đùa với một số thứ và nghĩ ra ý tưởng cố gắng tìm ra số Kevin Bacon. Tôi có dữ liệu cho một trang web cho mục đích này chúng ta có thể xem xét một mạng xã hội. Hãy giả vờ rằng đó là Facebook (để đơn giản hóa thảo luận). Tôi có người và tôi có một danh sách bạn bè của họ, vì vậy tôi có mối liên hệ giữa họ. Làm thế nào tôi có thể tính toán khoảng cách từ một người khác (về cơ bản, một số Kevin Bacon)?Tính số "Kevin Bacon"
Ý tưởng hay nhất của tôi là Bidirectional search, với giới hạn chiều sâu (để giới hạn độ phức tạp tính toán và tránh vấn đề của những người không thể kết nối trong biểu đồ), nhưng tôi nhận ra đây là lực mạnh. Có thể tốt hơn nếu tạo ít đồ thị phụ (nói điều gì đó tương đương với các nhóm trên Facebook), tính khoảng cách ngắn nhất giữa chúng (trước thời hạn, có lẽ) và sau đó thử sử dụng THOSE để tìm một liên kết? Trong khi điều này đòi hỏi tính toán trước, nó có thể làm cho nó có thể tìm kiếm nhiều nút ít hơn (các nút có thể là các nhóm thay vì cá nhân, làm cho đồ thị nhỏ hơn nhiều). Tuy nhiên, đây vẫn là một tìm kiếm hai chiều.
Tôi cũng có thể tính toán trước số lượng cá nhân được kết nối, tìm kiếm nút cho những người "phổ biến" trước tiên vì họ có cơ hội kết nối tốt nhất với cá nhân đích nhất định. Tôi nhận ra đây sẽ là một sự cân bằng tốc độ cho con đường ngắn nhất có thể. Tôi nghĩ rằng tôi cũng muốn sử dụng một tìm kiếm chiều sâu đầu tiên thay vì tìm kiếm rộng đầu tiên tôi dự định sử dụng trong các trường hợp khác.
Ai đó có thể nghĩ ra cách đơn giản/nhanh hơn để thực hiện việc này? Tôi muốn có thể tìm thấy chiều dài ngắn nhất giữa hai người, do đó, nó không phải dễ dàng như luôn luôn có cùng một điểm kết thúc (chẳng hạn như trong vấn đề Kevin Bacon).
Tôi nhận ra rằng có những vấn đề như tôi có thể nhận được chuỗi 200 người và như vậy, nhưng điều đó có thể giải quyết được việc tôi có giới hạn về chiều sâu mà tôi sẵn sàng tìm kiếm.
BTW, vì đây không phải là về phim, không có lý do thuyết phục để gọi nó là số Kevin Bacon thay vì số quen thuộc hơn (đối với một số ;-)) Erdős: http://en.wikipedia.org/wiki/Erdos_number – ShreevatsaR
Tôi thấy thuật ngữ đó trong khi thực hiện một số nghiên cứu, nhưng bằng cách gọi nó là số Kevin Bacon, mọi người đều biết ngay những gì tôi đang nói. Tôi nghĩ rằng sẽ cắt giảm việc giải thích. – MBCook
"mức độ tách" cũng sẽ có ý nghĩa –