| dbo:abstract
|
- هذه الخوارزمية تطبق على مشكلة الاقتران الأمثل المتمثل بمصفوفة الحدوث R و عناصرها rij ≥ 0 . تبحث الخوارزمية عن عناصر rij ليس لها أي صف مشترك (لا سطر مشترك و لا عمود مشترك) و مجموعها المتراكم له أكبر قيمة ممكنة. صممت هذه الخوارزمية سنة 1955 من طرف هارولد كوهن. (ar)
- L'algorisme hongarès és un algorisme d'optimització el qual resol problemes d'assignació en temps . La primera versió coneguda del mètode Hongarès, va ser inventat i publicat per Harold W. Kuhn el 1955. Va ser revisat per James Munkres el 1957, i ha estat conegut des de llavors com l'algorisme hongarès, l'algorisme de l'assignació de Munkres, o l'algorisme de Kuhn-Munkres. L'algorisme desenvolupat per Kuhn està basat en els primers treballs d'altres dos matemàtics hongaresos: Dénes Kőnig i Jenő Egerváry, d'on prové el seu nom. El gran avantatge del mètode de Kuhn és que és fortament polinòmic, cosa que redueix la seva complexitat computacional. L'algorisme hongarès construeix una solució del problema primal partint d'una solució no admissible (que correspon a una solució admissible del dual) fent-la a poc a poc més admissible. El 2006 es va descobrir que matemàtic Carl Gustav Jacob Jacobi va solucionar aquest problema en el segle xix, i que la solució es va publicar com a obra pòstuma el 1890 en llatí. (ca)
- Die Ungarische Methode, auch Kuhn-Munkres-Algorithmus genannt, ist ein Algorithmus zum Lösen gewichteter Zuordnungsprobleme auf bipartiten Graphen. Diese Problemklasse kann als Spezialfall der Linearen Optimierung formuliert werden, die ungarische Methode ist dann eine angepasste primal-duale Lösungsmethode. Die originale Implementierung hatte eine Komplexität von , durch geeignete Datenstrukturen und optimierte Unterroutinen konnte diese auf gesenkt werden. Die Ungarische Methode wurde 1955 von Harold W. Kuhn unter Einbeziehung vorheriger Ideen der ungarischen Mathematiker Dénes Kőnig und Jenő Egerváry entwickelt und von James Munkres 1957, einer Analyse der Laufzeit folgend, verbessert. (de)
- The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was , however Edmonds and Karp, and independently Tomizawa noticed that it can be modified to achieve an running time. One of the most popular variants is the Jonker–Volgenant algorithm. Ford and Fulkerson extended the method to general maximum flow problems in form of the Ford–Fulkerson algorithm. In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin. (en)
- L'algorithme hongrois ou méthode hongroise, aussi appelé algorithme de Kuhn-Munkres, est un algorithme d'optimisation combinatoire, qui résout le problème d'affectation en temps polynomial. C'est donc un algorithme qui permet de trouver un couplage parfait de poids optimum (minimum ou maximum) dans un graphe biparti dont les arêtes sont valuées. (fr)
- El algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicado por Harold W. Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres. El algoritmo desarrollado por Kuhn está basado fundamentalmente en los primeros trabajos de otros dos matemáticos Húngaros: Dénes Kőnig y Jenő Egerváry. La gran ventaja del método de Kuhn es que es fertemente polinómico (ver Complejidad computacional para más detalles). El algoritmo húngaro construye una solución del problema primal partiendo de una solución no admisible (que corresponde a una solución admisible del dual) haciéndola poco a poco más admisible. (es)
- Metode Hongaria adalah algoritme optimasi kombinatorial yang menyelesaikan masalah berdasarkan pembagian kerja dalam waktu polinomial. Algoritme ini mudah dimengerti dan diterapkan untuk menyelesaikan soal yang berupa penugasan dengan cara menemukan pemasangan sempurna. Pada dasarnya, proses algorima ini melibatkan perubahan biaya di dalam array sampai beberapa menjadi nol. Meski begitu, hal ini tidak mempengaruhi hasil optimasi dengan metode ini. (in)
- In matematica, il metodo ungherese, o algoritmo ungherese, è un metodo di che risolve in tempo polinomiale il problema dell'assegnamento. Il metodo è stato sviluppato da Harold Kuhn nel 1955, anticipando i successivi metodi primali-duali, ed è chiamato "ungherese" in quanto basato su lavori di Dénes König e . Nel 2006 fu scoperto un lavoro di Carl Jacobi, risalente al XIX secolo, che risolve il medesimo problema.La complessità dell'algoritmo era di , ma si è dimostrato che modificando leggermente l'algoritmo si può arrivare ad ottenere una complessità computazionale pari a . (it)
- Het Hongaars algoritme is een combinatorisch optimalisatiealgoritme dat een toewijzingsprobleem oplost in een tijd van orde . De eerste versie, bekend als de Hongaarse methode, werd bedacht en gepubliceerd door Harold Kuhn in 1955. Deze versie werd bewerkt door in 1957 en wordt sindsdien het Hongaars algoritme, het Munkres toewijzingsalgoritme of het Kuhn-Munkres algoritme genoemd. Het algoritme ontwikkeld door Kuhn was in grote mate gebaseerd op het werk van twee andere Hongaarse wiskundigen: en . (nl)
- Metoda węgierska – algorytm pozwalający rozwiązać problem przypisania w czasie wielomianowym. Została ona dopracowana oraz opublikowana przez w roku 1955. Została ona nazwana „metodą węgierską” z uwagi na fakt, że została ona wyprowadzona na podstawie wcześniejszych prac dwóch węgierskich matematyków: i . W roku 1957 profesor matematyki zauważył, że algorytm węgierski jest silnie wielomianowy. Od tamtej pory metoda węgierska jest również znana jako algorytm Kuhna-Munkersa. (pl)
- Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время (см. исследование операций). Он был разработан и опубликован Гарольдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и ). в 1957 году заметил, что алгоритм является (строго) полиномиальным. С этого времени алгоритм известен также как алгоритм Куна — Манкреса или алгоритм Манкреса решения задачи о назначениях. Временная сложность оригинального алгоритма была , однако и Карп (а также Томидзава независимо от них) показали, что его можно модифицировать так, чтобы достичь времени выполнения . Модифицированный венгерский алгоритм получил название алгоритм Хопкрофта-Карпа. Форд и Фалкерсон распространили метод на общие транспортные задачи. В 2006 году было обнаружено, что Якоби нашёл решение задачи о назначениях в XIX веке, которое было опубликовано на латыни в посмертном сборнике трудов 1890 года. (ru)
- Угорський алгоритм — алгоритм комбінаторної оптимізації, що розв'язує задачу про призначення за поліноміальний час і який передує пізнішому симплекс-методу (пряма і двоїста задачі). Алгоритм був вперше запроваджений в 1955 році у його статті «Угорський метод для задачі про призначення» на основі праць угорських математиків Денеша Кьоніга та (що і дало назву методу). В 1957 році переглянув алгоритм і дійшов висновку, що він є (строго) поліноміальним. З того часу алгоритм більш відомий як алгоритм Куна-Манкреса або задача про призначення Макреса. Часова складність оригінального алгоритму була O(n4), проте та Річард Карп, а також незалежно від них Томізава, відмітили, що він може бути модифікований для отримання часу виконання O(n3). та розширили метод до загальних транспортних задач. У 2006 році було відкрито, що Карл Густав Якобі розв'язав задачу про призначення в 19 сторіччі, а його розв'язок було опубліковано посмертно в 1890 році латинською мовою. (uk)
- 匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的。美国数学家于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家和的工作之上创建起来的。 詹姆士·芒克勒斯在1957年回顾了该算法，并发现它的时间复杂度为（强）多项式时间。 此后该算法被称为Kuhn–Munkres算法或Munkres分配算法。原始算法的时间复杂度为，但与卡普发现可以修改算法达到运行时间，富泽也独立发现了这一点。和将该方法推广到了一般运输问题。2006年发现卡爾·雅可比在19世纪就解决了指派问题，该解法在他死后在1890年以拉丁文发表。 (zh)
|
| rdfs:comment
|
- هذه الخوارزمية تطبق على مشكلة الاقتران الأمثل المتمثل بمصفوفة الحدوث R و عناصرها rij ≥ 0 . تبحث الخوارزمية عن عناصر rij ليس لها أي صف مشترك (لا سطر مشترك و لا عمود مشترك) و مجموعها المتراكم له أكبر قيمة ممكنة. صممت هذه الخوارزمية سنة 1955 من طرف هارولد كوهن. (ar)
- L'algorithme hongrois ou méthode hongroise, aussi appelé algorithme de Kuhn-Munkres, est un algorithme d'optimisation combinatoire, qui résout le problème d'affectation en temps polynomial. C'est donc un algorithme qui permet de trouver un couplage parfait de poids optimum (minimum ou maximum) dans un graphe biparti dont les arêtes sont valuées. (fr)
- Metode Hongaria adalah algoritme optimasi kombinatorial yang menyelesaikan masalah berdasarkan pembagian kerja dalam waktu polinomial. Algoritme ini mudah dimengerti dan diterapkan untuk menyelesaikan soal yang berupa penugasan dengan cara menemukan pemasangan sempurna. Pada dasarnya, proses algorima ini melibatkan perubahan biaya di dalam array sampai beberapa menjadi nol. Meski begitu, hal ini tidak mempengaruhi hasil optimasi dengan metode ini. (in)
- In matematica, il metodo ungherese, o algoritmo ungherese, è un metodo di che risolve in tempo polinomiale il problema dell'assegnamento. Il metodo è stato sviluppato da Harold Kuhn nel 1955, anticipando i successivi metodi primali-duali, ed è chiamato "ungherese" in quanto basato su lavori di Dénes König e . Nel 2006 fu scoperto un lavoro di Carl Jacobi, risalente al XIX secolo, che risolve il medesimo problema.La complessità dell'algoritmo era di , ma si è dimostrato che modificando leggermente l'algoritmo si può arrivare ad ottenere una complessità computazionale pari a . (it)
- Het Hongaars algoritme is een combinatorisch optimalisatiealgoritme dat een toewijzingsprobleem oplost in een tijd van orde . De eerste versie, bekend als de Hongaarse methode, werd bedacht en gepubliceerd door Harold Kuhn in 1955. Deze versie werd bewerkt door in 1957 en wordt sindsdien het Hongaars algoritme, het Munkres toewijzingsalgoritme of het Kuhn-Munkres algoritme genoemd. Het algoritme ontwikkeld door Kuhn was in grote mate gebaseerd op het werk van twee andere Hongaarse wiskundigen: en . (nl)
- Metoda węgierska – algorytm pozwalający rozwiązać problem przypisania w czasie wielomianowym. Została ona dopracowana oraz opublikowana przez w roku 1955. Została ona nazwana „metodą węgierską” z uwagi na fakt, że została ona wyprowadzona na podstawie wcześniejszych prac dwóch węgierskich matematyków: i . W roku 1957 profesor matematyki zauważył, że algorytm węgierski jest silnie wielomianowy. Od tamtej pory metoda węgierska jest również znana jako algorytm Kuhna-Munkersa. (pl)
- 匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的。美国数学家于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家和的工作之上创建起来的。 詹姆士·芒克勒斯在1957年回顾了该算法，并发现它的时间复杂度为（强）多项式时间。 此后该算法被称为Kuhn–Munkres算法或Munkres分配算法。原始算法的时间复杂度为，但与卡普发现可以修改算法达到运行时间，富泽也独立发现了这一点。和将该方法推广到了一般运输问题。2006年发现卡爾·雅可比在19世纪就解决了指派问题，该解法在他死后在1890年以拉丁文发表。 (zh)
- L'algorisme hongarès és un algorisme d'optimització el qual resol problemes d'assignació en temps . La primera versió coneguda del mètode Hongarès, va ser inventat i publicat per Harold W. Kuhn el 1955. Va ser revisat per James Munkres el 1957, i ha estat conegut des de llavors com l'algorisme hongarès, l'algorisme de l'assignació de Munkres, o l'algorisme de Kuhn-Munkres. L'algorisme desenvolupat per Kuhn està basat en els primers treballs d'altres dos matemàtics hongaresos: Dénes Kőnig i Jenő Egerváry, d'on prové el seu nom. El gran avantatge del mètode de Kuhn és que és fortament polinòmic, cosa que redueix la seva complexitat computacional. L'algorisme hongarès construeix una solució del problema primal partint d'una solució no admissible (que correspon a una solució admissible del dua (ca)
- Die Ungarische Methode, auch Kuhn-Munkres-Algorithmus genannt, ist ein Algorithmus zum Lösen gewichteter Zuordnungsprobleme auf bipartiten Graphen. Diese Problemklasse kann als Spezialfall der Linearen Optimierung formuliert werden, die ungarische Methode ist dann eine angepasste primal-duale Lösungsmethode. Die originale Implementierung hatte eine Komplexität von , durch geeignete Datenstrukturen und optimierte Unterroutinen konnte diese auf gesenkt werden. (de)
- El algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicado por Harold W. Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres. El algoritmo húngaro construye una solución del problema primal partiendo de una solución no admisible (que corresponde a una solución admisible del dual) haciéndola poco a poco más admisible. (es)
- The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. (en)
- Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время (см. исследование операций). Он был разработан и опубликован Гарольдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и ). (ru)
- Угорський алгоритм — алгоритм комбінаторної оптимізації, що розв'язує задачу про призначення за поліноміальний час і який передує пізнішому симплекс-методу (пряма і двоїста задачі). Алгоритм був вперше запроваджений в 1955 році у його статті «Угорський метод для задачі про призначення» на основі праць угорських математиків Денеша Кьоніга та (що і дало назву методу). (uk)
|
