Обсуждение:Венгерский алгоритм решения задачи о назначениях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «''Почему максимальное паросочетание ищется за n^2? Так точно можно?'' : Тут есть проблема: мак...»)
 
(Общий метод: новая тема)
 
(не показано 5 промежуточных версий 3 участников)
Строка 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)
 +
 +
''Возможно, есть смысл переместить информацию о том, что мы храним для построения дополняющей цепи, к моменту, где об этом построении говорится. И написать, как производится замена с использованием этой информации (кратко).''
 +
: Процесс замены я немного пояснил, но информацию о способе хранения дополняющей цепи, мне кажется, лучше оставить там, где она есть сейчас, иначе читающим эту статью будет довольно сложно вникнуть в процесс построения дерева цепей (а он является ключевым для этого алгоритма, так как остальные идеи уже разобраны выше, в общем методе). Остальные недочеты исправил. --[[Участник:Sementry|Мейнстер Д.]] 12:24, 17 января 2012 (MSK)
 +
 +
== Анализ времени работы общего метода ==
 +
 +
Действительно, данный метод может работать даже не за <tex> O(n^4) </tex>, а медленнее, более того, мне вообще непонятно, как оценить время его работы точнее, чем это сделано сейчас. Думаю, можно оставить текущую оценку, так как дальше в статье все равно разбирается алгоритм за <tex> O(n^3) </tex>, а этот вариант полезен скорее для понимания алгоритма, чем для практики. --[[Участник:Sementry|Мейнстер Д.]] 13:49, 10 марта 2012 (GST)
 +
 +
После применения операции могут исчезать нули на ребрах между <tex>X_c</tex> и <tex>Y_c</tex>. Из-за этого оценка <tex>O(n^5)</tex> перестает быть очевидной. Я не знаю, верна ли она на самом деле, но можно просто показать, что алгоритм завершается (в той же статье есть доказательство). --[[Участник:Igor buzhinsky|Игорь Бужинский]] 23:58, 11 марта 2012 (GST)
 +
 +
== Важно! Недоказанное утверждение в описании общего метода ==
 +
 +
В описании общего метода не установлено никаких ограничений на алгоритм поиска максимального паросочетания. Соответственно, мы НЕ можем с уверенностью сказать, что для любого способа поиска максимального паросочетания на любой итерации алгоритма, у нас не будет добавляться ребро, которое было удалено на прошлой итерации, подразумевавшееся ненужным для увеличения паросочетания. И, как следствие, алгоритм теоретически может зациклится. Это серьезное упущение в доказательстве, которое даже ставит под сомнение корректность алгоритма. В связи с чем, прошу автора статьи срочно принять нужные меры.
 +
 +
== Общий метод ==
 +
 +
Утверждение о том, что добавляется 0 неверно. Контрпример:
 +
012
 +
000
 +
034
 +
 +
В нем Xc это вторая строка, а Yc первый столбец. После указанных в статье преобразований таблица будет иметь вид:
 +
001
 +
100
 +
023
 +
 +
То есть количество нулей не изменилось.

Текущая версия на 18:54, 3 мая 2021

Почему максимальное паросочетание ищется за 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)

Возможно, есть смысл переместить информацию о том, что мы храним для построения дополняющей цепи, к моменту, где об этом построении говорится. И написать, как производится замена с использованием этой информации (кратко).

Процесс замены я немного пояснил, но информацию о способе хранения дополняющей цепи, мне кажется, лучше оставить там, где она есть сейчас, иначе читающим эту статью будет довольно сложно вникнуть в процесс построения дерева цепей (а он является ключевым для этого алгоритма, так как остальные идеи уже разобраны выше, в общем методе). Остальные недочеты исправил. --Мейнстер Д. 12:24, 17 января 2012 (MSK)

Анализ времени работы общего метода

Действительно, данный метод может работать даже не за [math] O(n^4) [/math], а медленнее, более того, мне вообще непонятно, как оценить время его работы точнее, чем это сделано сейчас. Думаю, можно оставить текущую оценку, так как дальше в статье все равно разбирается алгоритм за [math] O(n^3) [/math], а этот вариант полезен скорее для понимания алгоритма, чем для практики. --Мейнстер Д. 13:49, 10 марта 2012 (GST)

После применения операции могут исчезать нули на ребрах между [math]X_c[/math] и [math]Y_c[/math]. Из-за этого оценка [math]O(n^5)[/math] перестает быть очевидной. Я не знаю, верна ли она на самом деле, но можно просто показать, что алгоритм завершается (в той же статье есть доказательство). --Игорь Бужинский 23:58, 11 марта 2012 (GST)

Важно! Недоказанное утверждение в описании общего метода

В описании общего метода не установлено никаких ограничений на алгоритм поиска максимального паросочетания. Соответственно, мы НЕ можем с уверенностью сказать, что для любого способа поиска максимального паросочетания на любой итерации алгоритма, у нас не будет добавляться ребро, которое было удалено на прошлой итерации, подразумевавшееся ненужным для увеличения паросочетания. И, как следствие, алгоритм теоретически может зациклится. Это серьезное упущение в доказательстве, которое даже ставит под сомнение корректность алгоритма. В связи с чем, прошу автора статьи срочно принять нужные меры.

Общий метод

Утверждение о том, что добавляется 0 неверно. Контрпример: 012 000 034

В нем Xc это вторая строка, а Yc первый столбец. После указанных в статье преобразований таблица будет иметь вид: 001 100 023

То есть количество нулей не изменилось.