При поиске максимума вторая редукция по строкам, по сути, не нужна. Хоть и алгоритм подразумевает ее присутствие, но на деле ею можно пренебречь.
В статью я ее добавил чтобы можно было ссылаться на случай, если кто-либо будет решать задачу на минимум, ну и чтобы алгоритм был, так сказать, полноценным.
Спасибо большое! :)
Непонятно почему результат получился именно таким?
Алгоритм считается решенным тогда, когда задействованы все строки и столбцы (ну или как я везде упоминал, найдены уникальные нули).
Быстро набросал картинки для понимания. В этом случае — задача не решена еще, необходимо либо дальше продолжать алгоритм, либо по второму кругу считать: А в этом случае — решение задачи найдено:
Всегда в алгоритме все внимание уделяется нулям. Если бы в первом случае вместо шести был ноль, тогда задача тоже считалась бы решенной. Потом мы индексы нулей (во втором случае где решение задачи найдено — это [2;1],[5;3],[1;4],[4;5];[3;2]) подставляем в самую-самую исходную матрицу, которая у нас была дана изначально с условием задачи. Визуально видим какой исполнитель делает какую работу, и с помощью индексов считаем оптимальное значение. (Упс, помарочка вышла. Везде где писал «шестая строка»/«шестой столбец» конечно же имел ввиду «пятая строка»/«пятый столбец»)
Если помог разобраться — это супер! Если же нет, с радостью подскажу неясные моменты.
1. Исходный вид матрицы который используется в задачах Коммивояжера практически идентичен тому, который используется в задачах о назначениях. Суть даже одна:
Если же в задачах о назначениях имена строк/столбцов матрицы содержат работы/работников, то в Коммивояжере и строки и столбцы содержат города (населенные пункты), а сама матрица заполняется либо расстояниями между городами, либо стоимостью.
В задачах Коммивояжера матрица должна быть так же закрытого типа, и так же, чтобы были «уникальные» значения которые не повторяются в строках-столбце.
Наверно, единственное отличие — что на главной диагонали матрицы задач Коммивояжера стоят бесконечности.
2. Вот на этот вопрос затрудняюсь ответить. Могу конечно предположить, что задача Коммивояжера тем точна, что во время расчетов мы размер матрицы постепенно уменьшаем, и те значения которые уже найдены мы во внимания не берем. Лишь в конце все складываем в единую картину.
А в Венгерском методе мы решение получаем сразу, и пока задача не решена полностью, мы не можем быть уверены в конечном результате. К примеру, если 4 из 5 нулей найдены, а последний нет, это не будет означать что на новом шаге все «уникальные» нули не изменят свой индекс.
Потому что каждый шаг алгоритма двигает нас к тому, чтобы получить нули, и чем больше будет нулей, тем быстрее будет найден результат. Если на первом «круге» не вышло найти оптимальное значение, то выйдет на втором, если же и тут решение не будет найдено, можно продолжать алгоритм столько раз, сколько нам потребуется. При этом, каждый раз начиная алгоритм с начала, предыдущие расчеты не сбрасываются, а значит, нулей будет еще больше, что в конечном итоге приведет к решению задачи.
Само же решение, по сути, уже дано изначально, мы лишь делаем необходимые операции для того, чтобы можно было это понять. Нас не интересует какие числа будут в ходе вычислений, все равно в конце мы найденное решение подставляем в исходную матрицу. Легче приводить все числа к нулю, и то, которое быстрее это сделает, и которое будет уникальным в строке-столбце и будет являться если не разгадкой, то направлением к этой же разгадке.
Я согласен, что запись в одну строку и дополнительные библиотеки повысят «уровень» кода, но я старался предоставить алгоритм максимально легко, чтобы и читался он без напряга, и чтобы каждый шаг сопровождался комментарием.
Наивный Байес, по своей сути очень легкий и достаточно популярный алгоритм. Если его по-умному собрать (анализ по словосочетаниям, падежи и пр.), то он дает достаточно хорошие результаты. Из этого я и сделал вывод, что пусть он и устарел, но все еще остается актуальным.
Спасибо большое автору за труд!
В статью я ее добавил чтобы можно было ссылаться на случай, если кто-либо будет решать задачу на минимум, ну и чтобы алгоритм был, так сказать, полноценным.
Непонятно почему результат получился именно таким?
Алгоритм считается решенным тогда, когда задействованы все строки и столбцы (ну или как я везде упоминал, найдены уникальные нули).
Быстро набросал картинки для понимания.
В этом случае — задача не решена еще, необходимо либо дальше продолжать алгоритм, либо по второму кругу считать:
А в этом случае — решение задачи найдено:
Всегда в алгоритме все внимание уделяется нулям. Если бы в первом случае вместо шести был ноль, тогда задача тоже считалась бы решенной. Потом мы индексы нулей (во втором случае где решение задачи найдено — это [2;1],[5;3],[1;4],[4;5];[3;2]) подставляем в самую-самую исходную матрицу, которая у нас была дана изначально с условием задачи. Визуально видим какой исполнитель делает какую работу, и с помощью индексов считаем оптимальное значение.
(Упс, помарочка вышла. Везде где писал «шестая строка»/«шестой столбец» конечно же имел ввиду «пятая строка»/«пятый столбец»)
Если помог разобраться — это супер! Если же нет, с радостью подскажу неясные моменты.
2. Вот на этот вопрос затрудняюсь ответить. Могу конечно предположить, что задача Коммивояжера тем точна, что во время расчетов мы размер матрицы постепенно уменьшаем, и те значения которые уже найдены мы во внимания не берем. Лишь в конце все складываем в единую картину.
А в Венгерском методе мы решение получаем сразу, и пока задача не решена полностью, мы не можем быть уверены в конечном результате. К примеру, если 4 из 5 нулей найдены, а последний нет, это не будет означать что на новом шаге все «уникальные» нули не изменят свой индекс.
Потому что каждый шаг алгоритма двигает нас к тому, чтобы получить нули, и чем больше будет нулей, тем быстрее будет найден результат. Если на первом «круге» не вышло найти оптимальное значение, то выйдет на втором, если же и тут решение не будет найдено, можно продолжать алгоритм столько раз, сколько нам потребуется. При этом, каждый раз начиная алгоритм с начала, предыдущие расчеты не сбрасываются, а значит, нулей будет еще больше, что в конечном итоге приведет к решению задачи.
Само же решение, по сути, уже дано изначально, мы лишь делаем необходимые операции для того, чтобы можно было это понять. Нас не интересует какие числа будут в ходе вычислений, все равно в конце мы найденное решение подставляем в исходную матрицу. Легче приводить все числа к нулю, и то, которое быстрее это сделает, и которое будет уникальным в строке-столбце и будет являться если не разгадкой, то направлением к этой же разгадке.
Спасибо большое автору за статью!