Tôi nên sử dụng thuật toán nào để tìm dòng chảy tối thiểu trên bản đồ có các giới hạn dưới nhưng không có giới hạn trên?

Question

Tôi nên sử dụng thuật toán nào để tìm luồng tối thiểu trên bản đồ nơi có giới hạn dưới, nhưng không phải là giới hạn trên của luồng? Chẳng hạn như ví dụ đơn giản này:

Trong văn học này là một vấn đề lưu lượng chi phí tối thiểu. Tuy nhiên, trong trường hợp của tôi, chi phí cũng giống như một giới hạn thấp hơn trên luồng không cần thiết trên mỗi cạnh vì vậy tôi đã đặt câu hỏi như trên. Trong văn học, câu hỏi sẽ là: thuật toán tốt nhất để tìm luồng chi phí tối thiểu của đồ thị tuần hoàn hướng đơn/nguồn đơn, trong đó mỗi cạnh có công suất vô hạn, một giới hạn dưới khác trên dòng chảy, và chi phí bằng với giới hạn dưới của dòng chảy.

Từ nghiên cứu của tôi, dường như cách thức chính mà mọi người đối phó với bất kỳ loại chi phí tối thiểu nào của bất kỳ loại mạng nào là đặt vấn đề thành LP-type problem và giải quyết theo cách đó. Trực giác của tôi, tuy nhiên, là không có giới hạn trên lưu lượng, tức là. có các cạnh với các tụ điện vô hạn, làm cho vấn đề trở nên dễ dàng hơn, vì vậy tôi đã tự hỏi liệu có một thuật toán cụ thể nhắm vào trường hợp này hay không bằng cách sử dụng các kỹ thuật "graphy" nhiều hơn so với phương thức simplex et. al.

Ý tôi là, nếu tất cả các chi phí và giới hạn dưới là 1 như ở trên ... thì chúng tôi sẽ tìm kiếm một luồng bao gồm tất cả các cạnh, tuân theo quy tắc luồng và không đẩy quá nhiều luồng qua bất kỳ đường dẫn nào từ s đến t. Điều này chỉ cảm thấy như nó không nên yêu cầu một bộ giải LP cho tôi và thực sự bài viết trên Wikipedia về các luồng chi phí nhỏ nói rằng "nếu ràng buộc năng lực bị loại bỏ, vấn đề sẽ giảm xuống vấn đề đường đi ngắn nhất" nhưng tôi nghĩ họ đang nói về trường hợp trong đó các giới hạn dưới là tất cả không.

Cũng có mã nguồn C/C++ mã nguồn mở cho chi phí tối thiểu ở bất kỳ đâu? Từ googling những gì có sẵn tôi thấy rằng tôi có thể thiết lập vấn đề lên như là một vấn đề LP bản thân mình và giải quyết với một giải mã LP mã nguồn mở, hoặc tôi có thể sử dụng LEMON cung cấp một số thuật toán cho dòng chảy chi phí tối thiểu. Thư viện đồ thị tăng cường không bao gồm việc triển khai theo như tôi có thể nói.

Còn gì khác không?

Answer 1

Trong sự vắng mặt của thượng-giới hạn, cách dễ nhất - đơn giản nhất để thực hiện, hiểu, và đó là một cách hợp lý hiệu quả - để tìm dòng chảy tối thiểu của một đồ thị như sau:

1. Tìm một dòng chảy khả thi, tức là một luồng đáp ứng các quy tắc dòng chảy và giới hạn dưới về lưu lượng nhưng không nhất thiết phải là một luồng tối thiểu. Điều này có thể được thực hiện bằng cách thực hiện một chiều ngang đầu tiên của đồ thị, theo dõi đường đi hiện tại khi chúng ta đi qua và khi truy cập nút đã phát hiện trước đó hoặc t, nút đích, tăng luồng trên đường dẫn hiện tại với mức tối đa thấp nhất -giới hạn của các cạnh không hài lòng trên đường dẫn hiện tại tất cả các cách để t.

2. Biến luồng khả thi thành luồng tối thiểu bằng cách giải quyết vấn đề dòng chảy tối đa. Bạn cần phải tìm dòng chảy tối đa trên đồ thị có dung lượng bằng dòng chảy (e) - giới hạn dưới (e), nơi dòng chảy (e) có nghĩa là dòng chảy từ dòng chảy khả thi. Dòng chảy tối đa này được trừ đi từ dòng chảy khả thi sẽ là dòng chảy tối thiểu.

Phiên bản trên cũng có thể được thực hiện trong trường hợp biểu đồ cũng có giới hạn trên. Trong trường hợp đó bước 1. phức tạp hơn nhưng có thể được giải quyết bằng cách thực hiện một phép tính dòng chảy tối đa ban đầu trên một đồ thị được xây dựng đặc biệt.

Answer 2

Thêm tất cả "giới hạn dưới" của các luồng trên mỗi cạnh: bất kỳ giải pháp khả thi nào cũng sẽ cần đến điều đó.

Đối với mỗi nút n theo thứ tự topo (tức là sau các cạnh) từ bồn rửa t, nếu tổng S- của những gì diễn ra ở mép lớn rằng tổng S+ những gì đi ra ngoài, sau đó thêm dòng chảy S+ - S- trên tất cả các cạnh của đường đi ngắn nhất giữa s và t (xây dựng danh sách đường đi ngắn nhất trong khi thực hiện điều này để có hiệu quả).

Sau đó, bạn có xác nhận 'tối thiểu' (theo nghĩa là cần thiết trong mọi giải pháp khả thi) chẳng hạn như S+ - S- là không âm ở mỗi nút và dung lượng tối thiểu được thỏa mãn trên mỗi cạnh.

Vấn đề sau đó giảm xuống một vấn đề Multiflow trên cùng một cấu trúc đồ thị:

• nguồn là như nhau;
• không có giới hạn dung lượng;
• mỗi nút trong đó S+ - S- hoàn toàn tích cực trở thành bồn rửa có lưu lượng bắt buộc S+ - S-.
• bồn rửa ban đầu (có lưu lượng yêu cầu F) trở thành bồn rửa có lưu lượng F - S- nếu F-S- không âm (nếu không thì ràng buộc ban đầu sẽ được thỏa mãn bởi bất kỳ giải pháp nào).

Edit: cho vấn đề của bạn, đồ thị trông như thế này

 x1 -- x2 
/ \  \ 
s  \  t 
    \  \ /
    x3 -- x4 

với năng lực tối thiểu 1 cho mỗi cạnh, và tôi cho rằng không có dòng chảy tối thiểu bắt buộc khi bồn rửa t.

Đầu tiên chỉ định 1 cho mỗi cạnh.

Sự khác biệt S+ - S- cho mỗi nút (trừ, tất nhiên, s và t) là:

x1: 1 
x2: 0 
x3: 0 
x4: -1 

duy nhất tiêu cực là cho x4; chúng tôi thêm 1 vào mọi cạnh trên con đường ngắn nhất từ ​​x4 đến t, trong trường hợp đó đến cạnh (x4, t).

Hiện tại S+ - S- không âm cho mỗi nút và chỉ tích cực cho x1; vấn đề giảm xuống một vấn đề đa chiều (trong trường hợp đó là một vấn đề dòng chảy đơn giản), nơi luồng yêu cầu là 1 tại x1 và nguồn vẫn là s.

Answer 3

Viết trình giải quyết là không nhỏ.

Xem thư viện LEMON (một phần của COIN-OR). Nó có một số thuật toán được tối ưu hóa cao cho vấn đề luồng chi phí tối thiểu. Bạn có thể chọn thuật toán nào hoạt động tốt nhất trên dữ liệu của mình.

Xem http://lemon.cs.elte.hu/trac/lemon để biết thông tin về LEMON.

Xem http://lemon.cs.elte.hu/pub/doc/1.3/a00607.html để biết chi tiết về luồng mạng chi phí tối thiểu.