Làm cách nào để tìm cách tối thiểu số cạnh?

Question

Tôi đang suy nghĩ một thuật toán để giải quyết vấn đề bên dưới:

Biểu đồ nhất định bao gồm đỉnh và cạnh.

Có N khách hàng muốn di chuyển từ đỉnh đến đỉnh khác. Và mỗi yêu cầu của khách hàng cần một cạnh đạo diễn để kết nối hai đỉnh.

Vấn đề là làm cách nào để tìm số cạnh tối thiểu để đáp ứng tất cả các yêu cầu của khách hàng?

Có một ví dụ đơn giản:

• khách hàng 1 muốn đi từ đỉnh a đến đỉnh b.
• Khách hàng 2 muốn di chuyển từ đỉnh b đến đỉnh c.
• Khách hàng 3 muốn di chuyển từ đỉnh a đến đỉnh c.

Cách đơn giản nhất là đem lại lợi thế cho mỗi khách hàng:

• cạnh 1: đỉnh a -> đỉnh b
• cạnh 2: đỉnh b -> đỉnh c
• cạnh 3 : vertex a -> vertex c

Nhưng thực sự chỉ cần 2 cạnh (tức là cạnh 1 và cạnh 2) để thỏa mãn ba yêu cầu của khách hàng.

Nếu số lượng khách hàng lớn, cách tìm các cạnh tối thiểu để đáp ứng tất cả các yêu cầu của khách hàng?

Có một thuật toán để giải quyết vấn đề này không?

Answer 1

Bạn có thể mô hình hóa vấn đề dưới dạng chương trình số nguyên hỗn hợp. Bạn có thể định nghĩa các biến nhị phân cho "arc a-> b được sử dụng" và "customer c sử dụng arc a -> b" và ghi lại các yêu cầu dưới dạng bất đẳng thức tuyến tính. Nếu biểu đồ của bạn không quá lớn, bạn có thể giải quyết các mô hình như vậy trong thời gian hợp lý bằng bộ giải chương trình số nguyên hỗn hợp (CPLEX, GUROBI, nhưng cũng có các lựa chọn thay thế miễn phí trên web). Tôi biết rằng giải pháp này đòi hỏi một số công việc nếu bạn không quen với lập trình tuyến tính, nhưng nó đảm bảo để tìm giải pháp tốt nhất trong thời gian hữu hạn và bạn có thể giải quyết nó cho (1000) khách hàng và 1000 vòng cung.

Answer 2

Nếu bạn có N đỉnh, bạn luôn có thể xây dựng một giải pháp với các cạnh N (hướng). Chỉ cần tạo chu trình chỉ đạo V_1 -> V_2 -> V_3 -> ... -> V_N -> V_1. Bạn không bao giờ có thể có đường dẫn trực tiếp từ mọi đỉnh V_a đến mọi đỉnh V_b khác với các cạnh ít hơn (bởi vì bạn có một cây dẫn hướng nhất thiết phải chứa một chiếc lá). Lá là một trong hai không thể truy cập (nếu cạnh đi từ lá ra) hoặc lá là một bồn rửa (không thể kết nối với bất cứ điều gì khác) nếu cạnh là -> lá.

Answer 3

Không cần sử dụng bất kỳ thuật toán mới nào. Bạn có thể sử dụng thuật toán BFS/DFS.

Find if there exists any path between source and destination. 
    if !true 
     add a direct edge between source and destination 
     count++; 
return count; 

Đây là phần quan trọng thay vì lặp qua biểu đồ chúng tôi phải lặp qua các cạnh mới được thêm vào.

Answer 4

Bạn có thể sử dụng cấu hình dữ liệu bộ tách rời.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

while (num_edges--) 
    if root(vertex_a) != root(vertex_b) 
    count++ 
    union(vertex_a,vertex_B)