Как использовать Google.OrTools.Graph, чтобы показать оптимальный путь MinCostMaxFlow - C #

Question

КОРОТКАЯ ВЕРСИЯ ВОПРОСА: Здравствуйте, как использовать Google.OrTools.Graph, чтобы показать оптимальный путь выбранных узлов в программе " минимальная стоимость, максимальный поток "?

ПОЛНАЯ ВЕРСИЯ ВОПРОСА: Здравствуйте, я создал программу с минимальной стоимостью максимального потока (с использованием C # в Visual Studio). Здесь у вас есть скриншот полученного ввода (дополнительная информация: в левой части окна вы видите 5 массивов, которые я использовал). Вместо того, чтобы показывать «Минимальная стоимость: 150», мне нужно показать выбранный оптимальный путь узлов.

Код:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using Google.OrTools.Graph;

namespace MaxFlowMinCost
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void SolveMinCostFlow()
        {
            // Definesc arrays: sources, destinations, capacities, si unit costs
            // Pentru fiecare startNodes + endNodes(acestea reprezentand startul si finisul unei arce) am o capacitate si us cost corspunzator
            // Am folosit informatia din Taha's "Introduction to Operations Research",

            int numNodes = 5;
            int numArcs = 9;
            int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 };
            int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 };
            int[] capacities = { 15, 8, 20, 4, 10, 15, 5, 20, 4 };
            int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 };

            // Array-ul cu supply-ul fiecarui nod, in cazul meu supply-ul va intra prin nodul de start si va ajunge la destinatie(1 sau mai multe) unde se reprezinte cu semnul "-"

            int[] supplies = { 20, 0, 0, -5, -15 };



            // Definirea solverului de tip SimpleMinCostFlow.
            MinCostFlow minCostFlow = new MinCostFlow();

            // Adaug fiecare arca
            for (int i = 0; i < numArcs; ++i)
            {
                int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i],
                                                     capacities[i], unitCosts[i]);
                if (arc != i) throw new Exception("Internal error");
            }

            // Adaug supply-ul.
            for (int i = 0; i < numNodes; ++i)
            {
                minCostFlow.SetNodeSupply(i, supplies[i]);
            }


            //Rezolvarea + afisarea rezultatului

            // Se gaseste min cost flow.
            int solveStatus = minCostFlow.Solve();
            if (solveStatus == MinCostFlow.OPTIMAL)
            {
                long optimalCost = minCostFlow.OptimalCost();
                textBox1.AppendText("Costul minim: " + optimalCost + "\r\n");
                textBox1.AppendText("");
                textBox1.AppendText(" Arc           Flux / Capacitate  Cost\r\n");
                for (int i = 0; i < numArcs; ++i)
                {
                    long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
                    textBox1.AppendText(minCostFlow.Tail(i) + " -> " +
                                        minCostFlow.Head(i) + "  " +
                                        string.Format("{0,11}", minCostFlow.Flow(i)) + "  / " +
                                        string.Format("{0,5}", minCostFlow.Capacity(i)) + "       " +
                                        string.Format("{0,6}", cost));
                    textBox1.AppendText("\r\n");

                }
            }
            else
            {
                textBox1.AppendText("Rezolvarea problemei min cost flow a esuat. Statusul solverului: " +
                                  solveStatus);
            }
        }

        private void button1_Click(object sender, EventArgs e)
        {
            SolveMinCostFlow();
        }
    }
}

Если вы хотите проверить это самостоятельно. Вам необходимо установить пакет google: Перейдите в Инструменты -> Диспетчер пакетов NuGet -> Консоль диспетчера пакетов и введите «Install-Package Google.OrTools», чтобы устранить ошибку с x32 x64 совместимостью, перейдите в Диспетчер конфигурации ( см. ) и добавьте новую платформу решений с именем x64, затем выберите ее, и программа должна работать.

Теперь ВОПРОС: Как я могу показать путь узлов, которые функция "Solve ()" считает оптимальными?

Моя программа показывает оптимальную стоимость, но мне нужно показать оптимальный путь.

Я искал везде, но не могу найти решение.

Я активен 24/7 в этом вопросе, поэтому спросите все детали, которые я мог бы забыть добавить.

PS: я использовал это руководство для создания программы, возможно, эта информация поможет.

Спасибо!

Answer 1

Мне нужно то же самое, я уже некоторое время ищу ответ, это единственное место, где я вижу эту тему. Возможно, не удастся найти оптимальный путь, но я точно не знаю.