โฟลว์สูงสุด

ในส่วนต่อไปนี้ คุณจะเห็นตัวอย่างของปัญหาโฟลว์สูงสุด (โฟลว์สูงสุด)

ตัวอย่างโฟลว์สูงสุด

ดูปัญหาได้จากกราฟต่อไปนี้ ซึ่งแสดงเครือข่ายการขนส่ง

คุณต้องการส่งเนื้อหาจากโหนด 0 (แหล่งที่มา) ไปยังโหนด 4 (ซิงก์) ตัวเลขที่อยู่ข้างส่วนโค้งคือความสามารถของเส้นโค้ง ความจุของเส้นโค้งคือจำนวนเงินสูงสุดที่สามารถส่งผ่านเส้นโค้งนี้ได้ในระยะเวลาที่กำหนด ขีดจำกัดคือข้อจำกัดของปัญหา

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();

กําหนดข้อมูล

คุณระบุกราฟสำหรับปัญหาที่มีอาร์เรย์ 3 รายการ สำหรับโหนดเริ่มต้น โหนดสิ้นสุด และความจุของส่วนโค้ง ความยาวของแต่ละอาร์เรย์เท่ากับจำนวนส่วนโค้งในกราฟ

สำหรับ 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) และซิงก์ (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);
        }
    }
}