Hopcroft–Karp algorithm (original) (raw)
هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي (G(U,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف. هذه المشكلة NP-كاملة. خوارزمية هوبكروفت و كارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف. إن هذه المشكلة تحظى باهتمام عملي كبير، تم طرحها في خمسينيات القرن العشرين وتبقى اليوم ذات أهمية كبيرة على سبيل المثال في ميدان التعلّم العميق وما يعرف بمشكلة تخصيص المهام في الأنظمة متعددة الروبوتات (أو أ سراب الروبوتات).
| Property | Value |
|---|---|
| dbo:abstract | هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي (G(U,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف. هذه المشكلة NP-كاملة. خوارزمية هوبكروفت و كارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف. إن هذه المشكلة تحظى باهتمام عملي كبير، تم طرحها في خمسينيات القرن العشرين وتبقى اليوم ذات أهمية كبيرة على سبيل المثال في ميدان التعلّم العميق وما يعرف بمشكلة تخصيص المهام في الأنظمة متعددة الروبوتات (أو أ سراب الروبوتات). (ar) Der Algorithmus von Hopcroft und Karp (1973 von John E. Hopcroft und Richard M. Karp entwickelt) dient in der Graphentheorie zur Bestimmung eines Matchings mit maximaler Kardinalität in einem bipartiten Graphen. Er geht aus von dem Matching, die keine Kanten enthält, und konstruiert dazu alternierende Pfade zwischen noch ungepaarten Knoten. Jeder solche Pfad liefert eine Vergrößerung (Augmentierung) des Matchings um eine Kante. (de) In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of as many edges as possible with the property that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability. The algorithm was discovered by John Hopcroft and Richard Karp and independently by Alexander Karzanov. As in previous methods for matching such as the Hungarian algorithm and the work of , the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding augmenting paths. These paths are sequences of edges of the graph, which alternate between edges in the matching and edges out of the partial matching, and where the initial and final edge are not in the partial matching. Finding an augmenting path allows us to increment the size of the partial matching, by simply toggling the edges of the augmenting path (putting in the partial matching those that were not, and vice versa). Simpler algorithms for bipartite matching, such as the Ford–Fulkerson algorithm‚ find one augmenting path per iteration: the Hopcroft-Karp algorithm instead finds a maximal set of shortest augmenting paths, so as to ensure that only iterations are needed instead of iterations. The same performance of can be achieved to find maximum cardinality matchings in arbitrary graphs, with the more complicated algorithm of Micali and Vazirani. The Hopcroft–Karp algorithm can be seen as a special case of Dinic's algorithm for the maximum flow problem. (en) En informatique, l'algorithme de Hopcroft-Karp est un algorithme qui prend en entrée un graphe biparti et qui produit en sortie un couplage de cardinalité maximum, c'est-à-dire un ensemble d'arêtes aussi grand que possible avec la propriété que deux arêtes ne partagent jamais une extrémité. L'algorithme a une complexité en temps en dans le pire des cas, où est l'ensemble des arêtes et est l'ensemble des sommets du graphe, et il est supposé que . Dans le cas de graphes denses, la borne devient , et pour des graphes aléatoires creux, le temps est pratiquement linéaire (en ). L'algorithme a été décrit par John Hopcroft et Richard Karp en 1973. De même nature que d'autres algorithmes antérieurs de calcul de couplages comme l'algorithme hongrois ou la méthode d'Edmonds, l'algorithme de Hopcroft-Karp incrémente itérativement la taille d'un couplage partiel par le calcul de chemins d'augmentation : ce sont des suites d'arêtes qui sont alternativement dans et en dehors du couplage, de sorte que le remplacement des arêtes dans le couplage par celles qui sont en dehors produit un couplage plus grand. Toutefois, au lieu de déterminer juste un seul chemin d'augmentation à chaque itération, l'algorithme calcule à chaque phase un ensemble maximal de chemins d'augmentation de longueur minimale. Il en résulte que itérations suffisent. Le même principe a aussi été employé pour développer des algorithmes plus compliqués de couplage dans des graphes non bipartis, avec la même complexité en temps que l’algorithme de Hopcroft-Karp. (fr) Em ciência da computação, o algoritmo de Hopcroft–Karp é um algoritmo que recebe como entrada um grafo bipartido e produz como saída um máximo de cardinalidade de acoplamento – um conjunto de quantas arestas forem possíveis com a propriedade de que não há duas bordas compartilhando um ponto na extremidade. Ele roda em tempo no pior caso, onde é o conjunto de arestas do grafo, e é o conjunto de vértices do grafo. No caso de grafos densos o tempo limite torna-se e para grafos aleatórios ele é executado em tempo quase linear. O algoritmo foi encontrado por John Hopcroft e Richard Karp. Como nos métodos anteriores para acoplamento, tais como o algoritmo húngaro e o trabalho de , o algoritmo de Hopcroft–Karp aumenta várias vezes o tamanho de um acoplamento parcial encontrando caminhos extensores. No entanto, em vez de encontrar apenas um único caminho extensor por iteração, o algoritmo encontra um conjunto máximo de caminhos extensores mais curtos. Como resultado, apenas iterações são necessárias. O mesmo princípio também foi utilizado para desenvolver algoritmos mais complicados para acoplamentos não-bipartidos com o mesmo tempo de do algoritmo de Hopcroft–Karp. (pt) В інформатиці, алгоритм Гопкрофта—Карпа отримує на вході двочастковий граф і видає на виході парування найбільшої потужності – множину, що містить якнайбільше ребер з властивістю, що жодна двійка ребер не має спільної вершини. Виконується за час у найгіршому випадку, де це множина ребер і це множина вершин графа. У випадку часові рамки набувають вигляду , для випадкових графів час виконання майже лінійний. Алгоритм винайшли Джон Гопкрофт and Річард Карп. Як і в попередніх методах для парування як-от Угорський алгоритм і роботі , алгоритм Гопкрофта—Карпа багаторазово збільшує часткове парування через знаходження шляху розширення. Однак, замість пошуку одного шляху розширення, алгоритм шукає найбільшу множину найкоротших шляхів розширення. У результаті, потрібно лише ітерацій. Цей принцип використовували для розробки складніших алгоритмів для недвочасткового парування з таким самим часом виконання як у алгоритму Гопкрофта—Карпа. (uk) Алгоритм Хопкрофта — Карпа — алгоритм, принимающий на вход двудольный граф и возвращающий максимальное по мощности паросочетание, то есть наибольшее множество рёбер, таких что никакие два не имеют общую вершину. Асимптотика времени работы алгоритма составляет в худшем случае (здесь — множество рёбер графа, а — множество его вершин). В случае плотных графов время работы ограничивается , а для случайного графа алгоритм работает почти за линейное время. Алгоритм был создан Джоном Хопкрофтом и Ричардом Карпом в 1973 году. Как и ранее созданные алгоритмы (такие как венгерский алгоритм и алгоритм из работы Эдмондса, алгоритм Хопкрофта — Карпа в цикле увеличивает паросочетание, находя увеличивающие пути (цепи, рёбра которых попеременно принадлежат паросочетанию и не принадлежат ему, причём первая и последняя вершина не принадлежат паросочетанию; выполнив чередование паросочетания вдоль цепи, то есть убрав из паросочетания рёбра, бывшие в цепи, и добавив те, которых в нём не было, можно получить большее паросочетание). Вместо того чтобы находить один увеличивающий путь, алгоритм находит максимальное множество кратчайших увеличивающих путей. В результате требуется лишь итераций. Та же идея используется в более сложных алгоритмах для поиска паросочетаний в недвудольных графах с тем же асимптотическим временем работы, как у алгоритма Хопкрофта — Карпа. (ru) 霍普克洛夫特－卡普算法（Hopcroft Karp算法）是用來解決二分圖最大匹配問題的一種演算法。 在匈牙利算法中，我们每次寻找一条增广路来增加匹配集合M。可以证明，每次找增广路的复杂度是，一共需要增广次，因此总时间复杂度为。为了降低时间复杂度，在霍普克洛夫特－卡普算法中，我们在增加匹配集合M时，每次寻找多条增广路。可以证明，这样迭代次数最多为，所以，时间复杂度就降到了。 该算法由John E.Hopcroft和Richard M.Karp于1973年提出，故称霍普克洛夫特－卡普算法。 program Project1; const maxn=1000; var dx,dy,mx,my,q:array[1..maxn]of longint; adj:array[1..maxn,0..maxn]of longint; n,m,e,i,j,ans,ff,rr:longint; function bfs:boolean; var i,u,j:longint; begin bfs:=false; fillchar(q,sizeof(q),0); rr:=1; ff:=1; for i:=1 to n do if mx[i]=-1 then begin q[ff]:=i; inc(ff); end; for i:=1 to n do dx[i]:=0; for i:=1 to m do dy[i]:=0; while rr<ff do begin u:=q[rr]; inc(rr); for j:=1 to adj[u][0]do begin i:=adj[u][j]; if dy[i]=0 then begin dy[i]:=dx[u]+1; if my[i]=-1 then bfs:=true else begin dx[my[i]]:=dy[i]+1; q[ff]:=my[i]; inc(ff); end; end; end; end; end; function dfs(x:longint):boolean; var i,j:longint; begin for j:=1 to adj[x][0]do begin i:=adj[x][j]; if dy[i]=dx[x]+1 then begin dy[i]:=0; if(my[i]=-1)or dfs(my[i]) then begin mx[x]:=i; my[i]:=x; exit(true); end; end; end; exit(false); end; begin readln(n,m,e); for i:=1 to e do begin readln(ff,rr); inc(adj[ff][0]); adj[ff][adj[ff][0]]:=rr; end; for i:=1 to n do mx[i]:=-1; for i:=1 to m do my[i]:=-1; ans:=0; while bfs do for i:=1 to n do if(mx[i]=-1)and(dfs(i)) then inc(ans); writeln(ans); end. (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/HopcroftKarpExample.png?width=300 |
| dbo:wikiPageExternalLink | https://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf%7Cdoi=10.1007/11685654_10%7Clocation=Berlin |
| dbo:wikiPageID | 5944391 (xsd:integer) |
| dbo:wikiPageLength | 25147 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116634919 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Dense_graph dbr:Algorithm dbr:Algorithmica dbr:Augmenting_path dbr:Depth-first_search dbc:Matching_(graph_theory) dbr:Maximum_cardinality_matching dbr:Maximum_flow_problem dbr:Graph_(data_structure) dbr:Logarithm dbr:Computer_science dbc:Graph_algorithms dbr:Breadth-first_search dbr:Dinic's_algorithm dbr:Edmonds–Karp_algorithm dbr:Ford–Fulkerson_algorithm dbr:Hungarian_algorithm dbr:Bipartite_graph dbr:Assignment_problem dbr:Push-relabel_maximum_flow_algorithm dbr:Symmetric_difference dbr:Pseudocode dbr:Random_graph dbr:Average_case_analysis dbr:Worst_case dbr:Sparse_graph dbr:File:HopcroftKarpExample.png dbr:Weighted_graphs |
| dbp:author1Link | John Hopcroft (en) |
| dbp:author2Link | Richard Karp (en) |
| dbp:authorlink | Alexander V. Karzanov (en) |
| dbp:class | Graph algorithm (en) |
| dbp:data | dbr:Graph_(data_structure) |
| dbp:first | John (en) Alexander (en) Richard (en) |
| dbp:last | Karp (en) Hopcroft (en) Karzanov (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_book dbt:Harvtxt dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Harvnb dbt:Harvs dbt:Infobox_algorithm |
| dbp:year | 1973 (xsd:integer) |
| dct:subject | dbc:Matching_(graph_theory) dbc:Graph_algorithms |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي (G(U,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف. هذه المشكلة NP-كاملة. خوارزمية هوبكروفت و كارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف. إن هذه المشكلة تحظى باهتمام عملي كبير، تم طرحها في خمسينيات القرن العشرين وتبقى اليوم ذات أهمية كبيرة على سبيل المثال في ميدان التعلّم العميق وما يعرف بمشكلة تخصيص المهام في الأنظمة متعددة الروبوتات (أو أ سراب الروبوتات). (ar) Der Algorithmus von Hopcroft und Karp (1973 von John E. Hopcroft und Richard M. Karp entwickelt) dient in der Graphentheorie zur Bestimmung eines Matchings mit maximaler Kardinalität in einem bipartiten Graphen. Er geht aus von dem Matching, die keine Kanten enthält, und konstruiert dazu alternierende Pfade zwischen noch ungepaarten Knoten. Jeder solche Pfad liefert eine Vergrößerung (Augmentierung) des Matchings um eine Kante. (de) In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of as many edges as possible with the property that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability. (en) En informatique, l'algorithme de Hopcroft-Karp est un algorithme qui prend en entrée un graphe biparti et qui produit en sortie un couplage de cardinalité maximum, c'est-à-dire un ensemble d'arêtes aussi grand que possible avec la propriété que deux arêtes ne partagent jamais une extrémité. L'algorithme a une complexité en temps en dans le pire des cas, où est l'ensemble des arêtes et est l'ensemble des sommets du graphe, et il est supposé que . Dans le cas de graphes denses, la borne devient , et pour des graphes aléatoires creux, le temps est pratiquement linéaire (en ). (fr) Em ciência da computação, o algoritmo de Hopcroft–Karp é um algoritmo que recebe como entrada um grafo bipartido e produz como saída um máximo de cardinalidade de acoplamento – um conjunto de quantas arestas forem possíveis com a propriedade de que não há duas bordas compartilhando um ponto na extremidade. Ele roda em tempo no pior caso, onde é o conjunto de arestas do grafo, e é o conjunto de vértices do grafo. No caso de grafos densos o tempo limite torna-se e para grafos aleatórios ele é executado em tempo quase linear. (pt) Алгоритм Хопкрофта — Карпа — алгоритм, принимающий на вход двудольный граф и возвращающий максимальное по мощности паросочетание, то есть наибольшее множество рёбер, таких что никакие два не имеют общую вершину. Асимптотика времени работы алгоритма составляет в худшем случае (здесь — множество рёбер графа, а — множество его вершин). В случае плотных графов время работы ограничивается , а для случайного графа алгоритм работает почти за линейное время. (ru) 霍普克洛夫特－卡普算法（Hopcroft Karp算法）是用來解決二分圖最大匹配問題的一種演算法。 在匈牙利算法中，我们每次寻找一条增广路来增加匹配集合M。可以证明，每次找增广路的复杂度是，一共需要增广次，因此总时间复杂度为。为了降低时间复杂度，在霍普克洛夫特－卡普算法中，我们在增加匹配集合M时，每次寻找多条增广路。可以证明，这样迭代次数最多为，所以，时间复杂度就降到了。 该算法由John E.Hopcroft和Richard M.Karp于1973年提出，故称霍普克洛夫特－卡普算法。 (zh) В інформатиці, алгоритм Гопкрофта—Карпа отримує на вході двочастковий граф і видає на виході парування найбільшої потужності – множину, що містить якнайбільше ребер з властивістю, що жодна двійка ребер не має спільної вершини. Виконується за час у найгіршому випадку, де це множина ребер і це множина вершин графа. У випадку часові рамки набувають вигляду , для випадкових графів час виконання майже лінійний. (uk) |
| rdfs:label | خوارزمية هوبكروفت-كارب (ar) Algorithmus von Hopcroft und Karp (de) Algorithme de Hopcroft-Karp (fr) Hopcroft–Karp algorithm (en) Algoritmo de Hopcroft–Karp (pt) Алгоритм Хопкрофта — Карпа (ru) 霍普克洛夫特－卡普算法 (zh) Алгоритм Гопкрофта — Карпа (uk) |
| owl:sameAs | freebase:Hopcroft–Karp algorithm wikidata:Hopcroft–Karp algorithm dbpedia-ar:Hopcroft–Karp algorithm dbpedia-de:Hopcroft–Karp algorithm dbpedia-fa:Hopcroft–Karp algorithm dbpedia-fr:Hopcroft–Karp algorithm http://hy.dbpedia.org/resource/Հապքրոֆթ-Կարպ_ալգորիթմ dbpedia-pt:Hopcroft–Karp algorithm dbpedia-ru:Hopcroft–Karp algorithm dbpedia-sr:Hopcroft–Karp algorithm dbpedia-th:Hopcroft–Karp algorithm dbpedia-uk:Hopcroft–Karp algorithm dbpedia-zh:Hopcroft–Karp algorithm https://global.dbpedia.org/id/WUaC |
| prov:wasDerivedFrom | wikipedia-en:Hopcroft–Karp_algorithm?oldid=1116634919&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/HopcroftKarpExample.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Hopcroft–Karp_algorithm |
| is dbo:knownFor of | dbr:Richard_M._Karp |
| is dbo:wikiPageRedirects of | dbr:Hopcroft-Karp-Karzanov_algorithm dbr:Hopcroft–Karp–Karzanov_algorithm dbr:Hopcroft-Karp_algorithm dbr:Hopcroft-Karp dbr:Hopcroft_Karp |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Hopcroft-Karp-Karzanov_algorithm dbr:Hopcroft–Karp–Karzanov_algorithm dbr:Richard_M._Karp dbr:Kőnig's_theorem_(graph_theory) dbr:♯P-completeness_of_01-permanent dbr:Maximum_cardinality_matching dbr:Timeline_of_algorithms dbr:Alexander_V._Karzanov dbr:Hopcroft-Karp_algorithm dbr:3-dimensional_matching dbr:Dinic's_algorithm dbr:Graph_theory dbr:Hall_violator dbr:John_Hopcroft dbr:Bipartite_graph dbr:Network_controllability dbr:Syntactic_pattern_recognition dbr:Hopcroft-Karp dbr:Hopcroft_Karp |
| is dbp:knownFor of | dbr:Richard_M._Karp |
| is foaf:primaryTopic of | wikipedia-en:Hopcroft–Karp_algorithm |
