Zadbaj o dobrą organizację dzięki kolekcji
Zapisuj i kategoryzuj treści zgodnie ze swoimi preferencjami.
Wiele problemów informatycznych może mieć postać wykresu składającego się z węzłów i linków. Przykładem mogą tu być problemy z przepływem sieci polegające na transportowaniu towarów lub materiałów w sieci, np. w systemie kolejowym.
Możesz przedstawić przepływ danych na wykresie, którego węzły są miastami i których łuki tworzą linie kolejowe. Są to tzw. przepływy, ponieważ ich właściwości są podobne do właściwości przepływającej przez sieć rur.
Głównym ograniczeniem w przepływach sieci jest to, że każdy z nich ma pojemność, czyli maksymalną ilość, jaką można przenieść, wykorzystując do tego określony przedział czasu.
Problem z maksymalnym przebiegiem przepływu określa maksymalną łączną ilość ruchu, jaką można przenieść we wszystkich łukach sieci, z uwzględnieniem ograniczeń pojemności.
Pierwszą osobą, która badała ten problem, był rosyjski matematyk A.N. Tolstoi. Na poniższej mapie przedstawiliśmy rzeczywistą sieć kolejową, dla której chcieliśmy znaleźć maksymalną prędkość.
Narzędzie OR-Tools zawiera kilka rozwiązań problemów z przepływem sieci w jego bibliotekach graph.
Poniżej znajdziesz przykłady problemów z przepływem sieci oraz sposoby ich rozwiązywania:
[[["Łatwo zrozumieć","easyToUnderstand","thumb-up"],["Rozwiązało to mój problem","solvedMyProblem","thumb-up"],["Inne","otherUp","thumb-up"]],[["Brak potrzebnych mi informacji","missingTheInformationINeed","thumb-down"],["Zbyt skomplikowane / zbyt wiele czynności do wykonania","tooComplicatedTooManySteps","thumb-down"],["Nieaktualne treści","outOfDate","thumb-down"],["Problem z tłumaczeniem","translationIssue","thumb-down"],["Problem z przykładami/kodem","samplesCodeIssue","thumb-down"],["Inne","otherDown","thumb-down"]],["Ostatnia aktualizacja: 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"]]
