Flussi di rete
Molti problemi dell'informatica possono essere rappresentati da un grafico composto da nodi e link tra loro. Alcuni esempi sono i problemi di flusso della rete, che riguardano il trasporto di beni o materiali attraverso una rete, ad esempio un sistema ferroviario.
Puoi rappresentare un flusso di rete da un grafico i cui nodi sono città e i cui archi sono linee ferroviarie tra loro. Sono chiamati flussi perché le loro proprietà sono simili a quelle dell'acqua che scorre attraverso una rete di tubi.
Un vincolo chiave nei flussi di rete è che ogni arco ha una capacità: la quantità massima che può essere trasferita attraverso l'arco in un periodo di tempo prestabilito.
Il problema massimo di flusso è determinare la quantità totale massima che può essere trasportata su tutti gli archi della rete, in base ai vincoli di capacità.
La prima persona a studiare questo problema è stata la matematica russa A.N. Tolstoj, negli anni '30. La mappa seguente mostra la rete ferroviaria effettiva di cui desidera trovare un flusso massimo.
OR-Tools fornisce diversi risolutori per i problemi dei flussi di rete nelle sue librerie graph.
Le seguenti sezioni presentano alcuni esempi di problemi di flusso di rete e mostrano come risolverli:
Salvo quando diversamente specificato, i contenuti di questa pagina sono concessi in base alla licenza Creative Commons Attribution 4.0, mentre gli esempi di codice sono concessi in base alla licenza Apache 2.0. Per ulteriori dettagli, consulta le norme del sito di Google Developers. Java è un marchio registrato di Oracle e/o delle sue consociate.
Ultimo aggiornamento 2024-08-09 UTC.
[null,null,["Ultimo aggiornamento 2024-08-09 UTC."],[[["Network flow problems, like transporting goods across a railway system, can be represented by graphs with nodes and links, where links have capacity limits."],["The maximum flow problem aims to find the maximum transportable amount across a network, respecting capacity constraints."],["OR-Tools offers various solvers in its graph libraries to address network flow problems like maximum flows and minimum cost flows."],["Example applications of network flows include assignments with individual workers or teams, solvable using OR-Tools."]]],["Computer science utilizes graphs to model problems like network flow, where goods are transported across a network (e.g., railway). Each link (arc) in the network has a capacity, limiting transport volume. The maximum flow problem determines the highest total transport volume across all arcs, respecting these capacity constraints. This problem, first studied by A.N. Tolstoi, can be solved using solvers from the OR-Tools graph libraries, which are useful for problems such as maximum flows, minimum cost flows, and assignment problems.\n"]]
