בקטעים הבאים מוצגת דוגמה לבעיה בתהליך המקסימלי (maxflow).
דוגמה לנתיב מקסימלי
הבעיה מוגדרת באמצעות התרשים הבא, שמייצג רשת תחבורה:
אתם רוצים להעביר חומרים מצומת 0 (המקור) לצומת 4 (sink). המספרים שמופיעים ליד הקשת מייצגים את הקיבולת שלהם – הקיבולת של קשת היא הכמות המקסימלית שניתן להעביר בה בפרק זמן קבוע. הקיבולת היא האילוצים של הבעיה.
flow הוא העברה של מספר לא שלילי לכל קשת (סכום הזרימה) בהתאם לכלל שימור הזרימה הבא:
הבעיה של הזרימה המקסימלית היא למצוא זרימה שבה הסכום של סכומי הזרימה ברשת כולה גדול ככל האפשר.
בקטעים הבאים מוסבר איך למצוא את הזרימה המקסימלית מהמקור (0) לשקע (4).
ייבוא הספריות
הקוד הבא מייבא את הספרייה הנדרשת.
Python
import numpy as np from ortools.graph.python import max_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/max_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MaxFlow;
C#
using System; using Google.OrTools.Graph;
מצהירים על הפותר
כדי לפתור את הבעיה, תוכלו להשתמש בכלי לפתרון SimpleMaxFlow.
Python
# Instantiate a SimpleMaxFlow solver. smf = max_flow.SimpleMaxFlow()
C++
// Instantiate a SimpleMaxFlow solver. SimpleMaxFlow max_flow;
Java
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
C#
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
הגדרת הנתונים
אתם מגדירים את התרשים של הבעיה עם שלושה מערכים: לצומתי ההתחלה, לצומתי הסיום ולקיבולת של הקשתות. האורך של כל מערך שווה למספר הקשתות בתרשים.
לכל i, קשת i משתנה מ-start_nodes[i] ל-end_nodes[i], והקיבולת שלה ניתנת על ידי capacities[i]. בקטע הבא מוסבר איך ליצור את הקשתות באמצעות הנתונים האלה.
Python
# Define three parallel arrays: start_nodes, end_nodes, and the capacities # between each pair. For instance, the arc from node 0 to node 1 has a # capacity of 20. start_nodes = np.array([0, 0, 0, 1, 1, 2, 2, 3, 3]) end_nodes = np.array([1, 2, 3, 2, 4, 3, 4, 2, 4]) capacities = np.array([20, 30, 10, 40, 30, 10, 20, 5, 20])
C++
// Define three parallel arrays: start_nodes, end_nodes, and the capacities
// between each pair. For instance, the arc from node 0 to node 1 has a
// capacity of 20.
std::vector<int64_t> start_nodes = {0, 0, 0, 1, 1, 2, 2, 3, 3};
std::vector<int64_t> end_nodes = {1, 2, 3, 2, 4, 3, 4, 2, 4};
std::vector<int64_t> capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20};
Java
// Define three parallel arrays: start_nodes, end_nodes, and the capacities
// between each pair. For instance, the arc from node 0 to node 1 has a
// capacity of 20.
// From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = new int[] {0, 0, 0, 1, 1, 2, 2, 3, 3};
int[] endNodes = new int[] {1, 2, 3, 2, 4, 3, 4, 2, 4};
int[] capacities = new int[] {20, 30, 10, 40, 30, 10, 20, 5, 20};
C#
// Define three parallel arrays: start_nodes, end_nodes, and the capacities
// between each pair. For instance, the arc from node 0 to node 1 has a
// capacity of 20.
// From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = { 0, 0, 0, 1, 1, 2, 2, 3, 3 };
int[] endNodes = { 1, 2, 3, 2, 4, 3, 4, 2, 4 };
int[] capacities = { 20, 30, 10, 40, 30, 10, 20, 5, 20 };
הוספת הקשתות
לכל צומת התחלה וצומת קצה, יוצרים קשת מצומת התחלה לצומת קצה עם הקיבולת הנתונה באמצעות השיטה AddArcWithCapacity. הקיבולת היא האילוצים של הבעיה.
Python
# Add arcs in bulk. # note: we could have used add_arc_with_capacity(start, end, capacity) all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities)
C++
// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]);
}
Java
// Add each arc.
for (int i = 0; i < startNodes.length; ++i) {
int arc = maxFlow.addArcWithCapacity(startNodes[i], endNodes[i], capacities[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}
C#
// Add each arc.
for (int i = 0; i < startNodes.Length; ++i)
{
int arc = maxFlow.AddArcWithCapacity(startNodes[i], endNodes[i], capacities[i]);
if (arc != i)
throw new Exception("Internal error");
}
מזמינים את הפותר
אחרי שהגדרתם את כל הקשתות, כל מה שנשאר זה להפעיל את המפענח ולהציג את התוצאות. אתם מפעילים את השיטה Solve(), כשמציינים את המקור (0) ואת sink (4).
Python
# Find the maximum flow between node 0 and node 4. status = smf.solve(0, 4)
C++
// Find the maximum flow between node 0 and node 4. int status = max_flow.Solve(0, 4);
Java
// Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.solve(0, 4);
C#
// Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.Solve(0, 4);
הצגת התוצאות
עכשיו אפשר להציג את הזרימה בכל קשת.
Python
if status != smf.OPTIMAL:
print("There was an issue with the max flow input.")
print(f"Status: {status}")
exit(1)
print("Max flow:", smf.optimal_flow())
print("")
print(" Arc Flow / Capacity")
solution_flows = smf.flows(all_arcs)
for arc, flow, capacity in zip(all_arcs, solution_flows, capacities):
print(f"{smf.tail(arc)} / {smf.head(arc)} {flow:3} / {capacity:3}")
print("Source side min-cut:", smf.get_source_side_min_cut())
print("Sink side min-cut:", smf.get_sink_side_min_cut())
C++
if (status == MaxFlow::OPTIMAL) {
LOG(INFO) << "Max flow: " << max_flow.OptimalFlow();
LOG(INFO) << "";
LOG(INFO) << " Arc Flow / Capacity";
for (std::size_t i = 0; i < max_flow.NumArcs(); ++i) {
LOG(INFO) << max_flow.Tail(i) << " -> " << max_flow.Head(i) << " "
<< max_flow.Flow(i) << " / " << max_flow.Capacity(i);
}
} else {
LOG(INFO) << "Solving the max flow problem failed. Solver status: "
<< status;
}
Java
if (status == MaxFlow.Status.OPTIMAL) {
System.out.println("Max. flow: " + maxFlow.getOptimalFlow());
System.out.println();
System.out.println(" Arc Flow / Capacity");
for (int i = 0; i < maxFlow.getNumArcs(); ++i) {
System.out.println(maxFlow.getTail(i) + " -> " + maxFlow.getHead(i) + " "
+ maxFlow.getFlow(i) + " / " + maxFlow.getCapacity(i));
}
} else {
System.out.println("Solving the max flow problem failed. Solver status: " + status);
}
C#
if (status == MaxFlow.Status.OPTIMAL)
{
Console.WriteLine("Max. flow: " + maxFlow.OptimalFlow());
Console.WriteLine("");
Console.WriteLine(" Arc Flow / Capacity");
for (int i = 0; i < maxFlow.NumArcs(); ++i)
{
Console.WriteLine(maxFlow.Tail(i) + " -> " + maxFlow.Head(i) + " " +
string.Format("{0,3}", maxFlow.Flow(i)) + " / " +
string.Format("{0,3}", maxFlow.Capacity(i)));
}
}
else
{
Console.WriteLine("Solving the max flow problem failed. Solver status: " + status);
}
הנה הפלט של התוכנה:
Max flow: 60 Arc Flow / Capacity 0 -> 1 20 / 20 0 -> 2 30 / 30 0 -> 3 10 / 10 1 -> 2 0 / 40 1 -> 4 20 / 30 2 -> 3 10 / 10 2 -> 4 20 / 20 3 -> 2 0 / 5 3 -> 4 20 / 20 Source side min-cut: [0] Sink side min-cut: [4, 1]
סכומי הזרימה בכל קשת מוצגים בקטע Flow.
השלמה של תוכניות
הנה כל התוכניות האפשריות.
Python
"""From Taha 'Introduction to Operations Research', example 6.4-2."""
import numpy as np
from ortools.graph.python import max_flow
def main():
"""MaxFlow simple interface example."""
# Instantiate a SimpleMaxFlow solver.
smf = max_flow.SimpleMaxFlow()
# Define three parallel arrays: start_nodes, end_nodes, and the capacities
# between each pair. For instance, the arc from node 0 to node 1 has a
# capacity of 20.
start_nodes = np.array([0, 0, 0, 1, 1, 2, 2, 3, 3])
end_nodes = np.array([1, 2, 3, 2, 4, 3, 4, 2, 4])
capacities = np.array([20, 30, 10, 40, 30, 10, 20, 5, 20])
# Add arcs in bulk.
# note: we could have used add_arc_with_capacity(start, end, capacity)
all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities)
# Find the maximum flow between node 0 and node 4.
status = smf.solve(0, 4)
if status != smf.OPTIMAL:
print("There was an issue with the max flow input.")
print(f"Status: {status}")
exit(1)
print("Max flow:", smf.optimal_flow())
print("")
print(" Arc Flow / Capacity")
solution_flows = smf.flows(all_arcs)
for arc, flow, capacity in zip(all_arcs, solution_flows, capacities):
print(f"{smf.tail(arc)} / {smf.head(arc)} {flow:3} / {capacity:3}")
print("Source side min-cut:", smf.get_source_side_min_cut())
print("Sink side min-cut:", smf.get_sink_side_min_cut())
if __name__ == "__main__":
main()
C++
// From Taha 'Introduction to Operations Research', example 6.4-2."""
#include <cstdint>
#include <vector>
#include "ortools/graph/max_flow.h"
namespace operations_research {
// MaxFlow simple interface example.
void SimpleMaxFlowProgram() {
// Instantiate a SimpleMaxFlow solver.
SimpleMaxFlow max_flow;
// Define three parallel arrays: start_nodes, end_nodes, and the capacities
// between each pair. For instance, the arc from node 0 to node 1 has a
// capacity of 20.
std::vector<int64_t> start_nodes = {0, 0, 0, 1, 1, 2, 2, 3, 3};
std::vector<int64_t> end_nodes = {1, 2, 3, 2, 4, 3, 4, 2, 4};
std::vector<int64_t> capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20};
// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]);
}
// Find the maximum flow between node 0 and node 4.
int status = max_flow.Solve(0, 4);
if (status == MaxFlow::OPTIMAL) {
LOG(INFO) << "Max flow: " << max_flow.OptimalFlow();
LOG(INFO) << "";
LOG(INFO) << " Arc Flow / Capacity";
for (std::size_t i = 0; i < max_flow.NumArcs(); ++i) {
LOG(INFO) << max_flow.Tail(i) << " -> " << max_flow.Head(i) << " "
<< max_flow.Flow(i) << " / " << max_flow.Capacity(i);
}
} else {
LOG(INFO) << "Solving the max flow problem failed. Solver status: "
<< status;
}
}
} // namespace operations_research
int main() {
operations_research::SimpleMaxFlowProgram();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.graph.samples;
import com.google.ortools.Loader;
import com.google.ortools.graph.MaxFlow;
/** Minimal MaxFlow program. */
public final class SimpleMaxFlowProgram {
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Instantiate a SimpleMaxFlow solver.
MaxFlow maxFlow = new MaxFlow();
// Define three parallel arrays: start_nodes, end_nodes, and the capacities
// between each pair. For instance, the arc from node 0 to node 1 has a
// capacity of 20.
// From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = new int[] {0, 0, 0, 1, 1, 2, 2, 3, 3};
int[] endNodes = new int[] {1, 2, 3, 2, 4, 3, 4, 2, 4};
int[] capacities = new int[] {20, 30, 10, 40, 30, 10, 20, 5, 20};
// Add each arc.
for (int i = 0; i < startNodes.length; ++i) {
int arc = maxFlow.addArcWithCapacity(startNodes[i], endNodes[i], capacities[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}
// Find the maximum flow between node 0 and node 4.
MaxFlow.Status status = maxFlow.solve(0, 4);
if (status == MaxFlow.Status.OPTIMAL) {
System.out.println("Max. flow: " + maxFlow.getOptimalFlow());
System.out.println();
System.out.println(" Arc Flow / Capacity");
for (int i = 0; i < maxFlow.getNumArcs(); ++i) {
System.out.println(maxFlow.getTail(i) + " -> " + maxFlow.getHead(i) + " "
+ maxFlow.getFlow(i) + " / " + maxFlow.getCapacity(i));
}
} else {
System.out.println("Solving the max flow problem failed. Solver status: " + status);
}
}
private SimpleMaxFlowProgram() {}
}
C#
// From Taha 'Introduction to Operations Research', example 6.4-2.
using System;
using Google.OrTools.Graph;
public class SimpleMaxFlowProgram
{
static void Main()
{
// Instantiate a SimpleMaxFlow solver.
MaxFlow maxFlow = new MaxFlow();
// Define three parallel arrays: start_nodes, end_nodes, and the capacities
// between each pair. For instance, the arc from node 0 to node 1 has a
// capacity of 20.
// From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = { 0, 0, 0, 1, 1, 2, 2, 3, 3 };
int[] endNodes = { 1, 2, 3, 2, 4, 3, 4, 2, 4 };
int[] capacities = { 20, 30, 10, 40, 30, 10, 20, 5, 20 };
// Add each arc.
for (int i = 0; i < startNodes.Length; ++i)
{
int arc = maxFlow.AddArcWithCapacity(startNodes[i], endNodes[i], capacities[i]);
if (arc != i)
throw new Exception("Internal error");
}
// Find the maximum flow between node 0 and node 4.
MaxFlow.Status status = maxFlow.Solve(0, 4);
if (status == MaxFlow.Status.OPTIMAL)
{
Console.WriteLine("Max. flow: " + maxFlow.OptimalFlow());
Console.WriteLine("");
Console.WriteLine(" Arc Flow / Capacity");
for (int i = 0; i < maxFlow.NumArcs(); ++i)
{
Console.WriteLine(maxFlow.Tail(i) + " -> " + maxFlow.Head(i) + " " +
string.Format("{0,3}", maxFlow.Flow(i)) + " / " +
string.Format("{0,3}", maxFlow.Capacity(i)));
}
}
else
{
Console.WriteLine("Solving the max flow problem failed. Solver status: " + status);
}
}
}