| dbo:abstract
|
- L'algorisme de Ford-Fulkerson és un algorisme que calcula el flux màxim en una xarxa de flux. L'algorisme proposa buscar camins en els quals es pugui augmentar el flux, fins que s'aconsegueixi el flux màxim. La idea és trobar una ruta de penetració amb un flux positiu net que uneixi els nodes origen i destinació. El seu nom ve donat pels seus creadors, L. R. Ford, Jr. i D. R. Fulkerson. (ca)
- Fordův-Fulkersonův algoritmus (pojmenovaný podle a D. R. Fulkersona) počítá maximální tok v síti. Název Ford-Fulkerson je také často používán pro Edmondsův-Karpův algoritmus, který je specializací Fordova-Fulkersonova algoritmu. Myšlenka algoritmu je velmi jednoduchá: Dokud existuje cesta ze zdroje (výchozí bod) do spotřebiče (koncový bod), taková, že je možnost ještě zvětšit její tok, neboli, že každá hrana na této cestě muže ještě „propustit“ vyšší tok (není ve stavu saturace), tak na všech hranách této cesty zvýšíme tok o největší hodnotu, o kterou lze zvětšit tok ve všech hranách cesty. Poté celý postup opakujeme. Cesta s volnou kapacitou se nazývá . (cs)
- Der Algorithmus von Ford und Fulkerson ist ein Algorithmus aus dem mathematischen Teilgebiet der Graphentheorie zur Bestimmung eines maximalen Flusses in einem Flussnetzwerk mit rationalen Kapazitäten. Er wurde nach seinen Erfindern L.R. Ford Jr. und D.R. Fulkerson benannt.Die Anzahl der benötigten Operationen hängt vom Wert des maximalen Flusses ab und ist im Allgemeinen nicht polynomiell beschränkt.Weiterentwicklungen führten zum Algorithmus von Edmonds und Karp und dem Algorithmus von Dinic. (de)
- El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, y D. R. Fulkerson. (es)
- The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method. The idea behind the algorithm is as follows: as long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along one of the paths. Then we find another path, and so on. A path with available capacity is called an augmenting path. (en)
- En informatique, l'algorithme de Ford-Fulkerson est un algorithme pour le problème de flot maximum, un problème d'optimisation classique dans le domaine de la recherche opérationnelle. Il est dû à Lester Randolph Ford junior et D. R. Fulkerson et c'est une variante de l'algorithme de Busacker et Gowen. (fr)
- In informatica, l'algoritmo di Ford-Fulkerson permette di trovare il flusso massimo che attraversa un grafo da un punto ad un altro di questo. Il nome deriva dai suoi due ideatori, Lester Randolph Ford e . (it)
- フォード・ファルカーソンのアルゴリズム（英: Ford-Fulkerson algorithm）とは、フローネットワークにおける最大フローを求めるアルゴリズムである。 と にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。 このアルゴリズムの背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; augmenting path」と呼ぶ。 (ja)
- Metoda Forda-Fulkersona jest stosowana do znajdowania maksymalnego przepływu w sieci przepływowej. Stanowi podstawę wielu algorytmów, między innymi algorytmu Edmondsa-Karpa czy algorytmu Dynica Zasadę jej działania można streścić w następujący sposób: Należy zwiększać przepływ wzdłuż dowolnej ścieżki ze źródła do ujścia, dopóki jest to możliwe. (pl)
- Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника к стоку , вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь. (ru)
- O algoritmo de Ford-Fulkerson (assim designado em honra de e Delbert Ray Fulkerson) é um algoritmo utilizado para resolver problemas de fluxo em rede (network flow). O algoritmo é empregado quando se deseja encontrar um fluxo de valor máximo que faça o melhor uso possível das capacidades disponíveis na rede em questão. A história do algoritmo está relacionada à análise da rede ferroviária da União Soviética, tanto por russos quanto por americanos, nas décadas de 1930, 1940 e 1950. O problema resolvido pelo algoritmo é o de encontrar um fluxo máximo em uma rede. Uma rede pode ser uma rede elétrica, um sistema de transporte de fluidos ou a distribuição de produtos ao longo de uma rede de transportes, como uma malha ferroviária ou rodoviária. Por exemplo, deseja-se transportar o máximo de minério de ferro através de uma rede ferroviária, limitadas pela capacidade de cada via. O tratamento aqui dado ao algoritmo supõe a existência de um único “ponto de entrada” (uma fonte) e de um único “ponto de saída” (um terminal). Para valores de fluxo irracionais, o algoritmo poderá ficar em um loop infinito e nunca retornar o fluxo máximo desejado. O algoritmo de Edmonds-Karp é uma variação do algoritmo de Ford-Fulkerson, mas com um final garantido e com um tempo de execução independente do valor do fluxo máximo. (pt)
- 福特-富尔克森方法（英語：Ford–Fulkerson method），又稱福特-富尔克森算法（Ford–Fulkerson algorithm），是一类计算网络流的最大流的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在1956年由及发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。 算法的思想如下：只要有一条从源点（开始节点）到汇点（结束节点）的路径，在路径的所有边上都有可用容量，就沿着这条路径发送一个流，流量由路径上的最小容量限制。 然后再找到另一条路径，一直到网络中不存在这种路径为止。 一条有可用容量的路径被称为一条增广路径。 (zh)
- Алгоритм або метод Форда — Фалкерсона знаходить максимальний потік у транспортній мережі. Метод Форда — Фалкерсона — метод, який базується на трьох концепціях: залишкові мережі, шляхи що збільшуються і розрізи. Ключову роль у методі Форда — Фалкерсона грають два поняття: залишкові мережі і доповнюють шляху. Дані концепції лежать в основі важливої теореми про максимальний потік і мінімальний розріз, яка визначає значення максимального нащадка за допомогою розрізів траспортної мережі. Метод Форда — Фалкерсона є ітеративним. Спочатку величині потоку присвоюється значення 0: при будь-яких , Є . На кожній ітерації величина потоку збільшується за допомогою пошуку «шляху, що збільшується» (тобто деякого шляху від джерела до стоку , уздовж якого можна послати більший потік) і подальшого збільшення потоку. Цей процес повторюється до тих пір, поки вже неможливо буде відшукати збільшуючийся шлях. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 17365 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- L'algorisme de Ford-Fulkerson és un algorisme que calcula el flux màxim en una xarxa de flux. L'algorisme proposa buscar camins en els quals es pugui augmentar el flux, fins que s'aconsegueixi el flux màxim. La idea és trobar una ruta de penetració amb un flux positiu net que uneixi els nodes origen i destinació. El seu nom ve donat pels seus creadors, L. R. Ford, Jr. i D. R. Fulkerson. (ca)
- Der Algorithmus von Ford und Fulkerson ist ein Algorithmus aus dem mathematischen Teilgebiet der Graphentheorie zur Bestimmung eines maximalen Flusses in einem Flussnetzwerk mit rationalen Kapazitäten. Er wurde nach seinen Erfindern L.R. Ford Jr. und D.R. Fulkerson benannt.Die Anzahl der benötigten Operationen hängt vom Wert des maximalen Flusses ab und ist im Allgemeinen nicht polynomiell beschränkt.Weiterentwicklungen führten zum Algorithmus von Edmonds und Karp und dem Algorithmus von Dinic. (de)
- El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, y D. R. Fulkerson. (es)
- En informatique, l'algorithme de Ford-Fulkerson est un algorithme pour le problème de flot maximum, un problème d'optimisation classique dans le domaine de la recherche opérationnelle. Il est dû à Lester Randolph Ford junior et D. R. Fulkerson et c'est une variante de l'algorithme de Busacker et Gowen. (fr)
- In informatica, l'algoritmo di Ford-Fulkerson permette di trovare il flusso massimo che attraversa un grafo da un punto ad un altro di questo. Il nome deriva dai suoi due ideatori, Lester Randolph Ford e . (it)
- フォード・ファルカーソンのアルゴリズム（英: Ford-Fulkerson algorithm）とは、フローネットワークにおける最大フローを求めるアルゴリズムである。 と にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。 このアルゴリズムの背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; augmenting path」と呼ぶ。 (ja)
- Metoda Forda-Fulkersona jest stosowana do znajdowania maksymalnego przepływu w sieci przepływowej. Stanowi podstawę wielu algorytmów, między innymi algorytmu Edmondsa-Karpa czy algorytmu Dynica Zasadę jej działania można streścić w następujący sposób: Należy zwiększać przepływ wzdłuż dowolnej ścieżki ze źródła do ujścia, dopóki jest to możliwe. (pl)
- Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника к стоку , вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь. (ru)
- 福特-富尔克森方法（英語：Ford–Fulkerson method），又稱福特-富尔克森算法（Ford–Fulkerson algorithm），是一类计算网络流的最大流的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在1956年由及发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。 算法的思想如下：只要有一条从源点（开始节点）到汇点（结束节点）的路径，在路径的所有边上都有可用容量，就沿着这条路径发送一个流，流量由路径上的最小容量限制。 然后再找到另一条路径，一直到网络中不存在这种路径为止。 一条有可用容量的路径被称为一条增广路径。 (zh)
- Fordův-Fulkersonův algoritmus (pojmenovaný podle a D. R. Fulkersona) počítá maximální tok v síti. Název Ford-Fulkerson je také často používán pro Edmondsův-Karpův algoritmus, který je specializací Fordova-Fulkersonova algoritmu. (cs)
- The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method. (en)
- O algoritmo de Ford-Fulkerson (assim designado em honra de e Delbert Ray Fulkerson) é um algoritmo utilizado para resolver problemas de fluxo em rede (network flow). O algoritmo é empregado quando se deseja encontrar um fluxo de valor máximo que faça o melhor uso possível das capacidades disponíveis na rede em questão. A história do algoritmo está relacionada à análise da rede ferroviária da União Soviética, tanto por russos quanto por americanos, nas décadas de 1930, 1940 e 1950. (pt)
- Алгоритм або метод Форда — Фалкерсона знаходить максимальний потік у транспортній мережі. Метод Форда — Фалкерсона — метод, який базується на трьох концепціях: залишкові мережі, шляхи що збільшуються і розрізи. Ключову роль у методі Форда — Фалкерсона грають два поняття: залишкові мережі і доповнюють шляху. Дані концепції лежать в основі важливої теореми про максимальний потік і мінімальний розріз, яка визначає значення максимального нащадка за допомогою розрізів траспортної мережі. Метод Форда — Фалкерсона є ітеративним. Спочатку величині потоку присвоюється значення 0: при будь-яких , Є . На кожній ітерації величина потоку збільшується за допомогою пошуку «шляху, що збільшується» (тобто деякого шляху від джерела до стоку , уздовж якого можна послати більший потік) і подальшого збільш (uk)
|
| rdfs:label
|
- Algorisme de Ford-Fulkerson (ca)
- Fordův–Fulkersonův algoritmus (cs)
- Algorithmus von Ford und Fulkerson (de)
- Algoritmo de Ford-Fulkerson (es)
- Ford–Fulkerson algorithm (en)
- Algoritmo di Ford-Fulkerson (it)
- Algorithme de Ford-Fulkerson (fr)
- フォード・ファルカーソンのアルゴリズム (ja)
- Metoda Forda-Fulkersona (pl)
- Algoritmo de Ford-Fulkerson (pt)
- Алгоритм Форда — Фалкерсона (ru)
- 福特-富尔克森算法 (zh)
- Алгоритм Форда — Фалкерсона (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
