Обсуждение:Венгерский алгоритм решения задачи о назначениях — различия между версиями
Sementry (обсуждение | вклад) (Новая страница: «''Почему максимальное паросочетание ищется за n^2? Так точно можно?'' : Тут есть проблема: мак...») |
|||
| Строка 4: | Строка 4: | ||
''В Асанове есть только часть описанного в конспекте.'' | ''В Асанове есть только часть описанного в конспекте.'' | ||
: При написании конспекта я пользовался также Википедией и визуализатором, недостающую в литературе информацию можно найти по указанным ссылкам. --[[Участник:Sementry|Мейнстер Д.]] 09:05, 7 января 2012 (MSK) | : При написании конспекта я пользовался также Википедией и визуализатором, недостающую в литературе информацию можно найти по указанным ссылкам. --[[Участник:Sementry|Мейнстер Д.]] 09:05, 7 января 2012 (MSK) | ||
| + | |||
| + | |||
| + | Нужно сделать описание алгоритма за O(n^3). Понимание алгоритма это усложнит, не спорю (описание за O(n^4), кстати, вы выбрали удивительно простое). Но этот вариант нам рассказывал Станкевич, и он же будет спрашивать его на экзамене. Попытайтесь сформулировать алгоритм проще, чем это сделано, например, в статье Даниила Шведа, стараясь больше описывать идею, а не реализацию. Возможно, я очень многого хочу, но что получится, то получится. | ||
| + | |||
| + | Алгоритм за O(n^4) тогда приводить не нужно, можете сделать ссылку внизу, например, [http://acm.mipt.ru/twiki/bin/view/Algorithms/HungarianAlgorithm сюда]. | ||
| + | |||
| + | С литературой попозже разберемся. Может, так и оставим. | ||
| + | |||
| + | Конспект большой, и даже если вы не успеете его полностью сдать до экзамена, баллы за него у вас будут. --[[Участник:Igor buzhinsky|Игорь Бужинский]] 23:52, 7 января 2012 (MSK) | ||
Версия 23:52, 7 января 2012
Почему максимальное паросочетание ищется за n^2? Так точно можно?
- Тут есть проблема: максимальное паросочетание ищется все-таки за O(n^3), и то, что я описал, работает за O(n^4). Я могу также описать версию, которая работает за O(n^3), но, по-моему, это сильно усложнит понимание алгоритма и загромоздит статью. --Мейнстер Д. 09:05, 7 января 2012 (MSK)
В Асанове есть только часть описанного в конспекте.
- При написании конспекта я пользовался также Википедией и визуализатором, недостающую в литературе информацию можно найти по указанным ссылкам. --Мейнстер Д. 09:05, 7 января 2012 (MSK)
Нужно сделать описание алгоритма за O(n^3). Понимание алгоритма это усложнит, не спорю (описание за O(n^4), кстати, вы выбрали удивительно простое). Но этот вариант нам рассказывал Станкевич, и он же будет спрашивать его на экзамене. Попытайтесь сформулировать алгоритм проще, чем это сделано, например, в статье Даниила Шведа, стараясь больше описывать идею, а не реализацию. Возможно, я очень многого хочу, но что получится, то получится.
Алгоритм за O(n^4) тогда приводить не нужно, можете сделать ссылку внизу, например, сюда.
С литературой попозже разберемся. Может, так и оставим.
Конспект большой, и даже если вы не успеете его полностью сдать до экзамена, баллы за него у вас будут. --Игорь Бужинский 23:52, 7 января 2012 (MSK)
