Mantieni tutto organizzato con le raccolte
Salva e classifica i contenuti in base alle tue preferenze.
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:
[[["Facile da capire","easyToUnderstand","thumb-up"],["Il problema è stato risolto","solvedMyProblem","thumb-up"],["Altra","otherUp","thumb-up"]],[["Mancano le informazioni di cui ho bisogno","missingTheInformationINeed","thumb-down"],["Troppo complicato/troppi passaggi","tooComplicatedTooManySteps","thumb-down"],["Obsoleti","outOfDate","thumb-down"],["Problema di traduzione","translationIssue","thumb-down"],["Problema relativo a esempi/codice","samplesCodeIssue","thumb-down"],["Altra","otherDown","thumb-down"]],["Ultimo aggiornamento 2024-08-09 UTC."],[],["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"]]
