Задача о назначениях. Как решать?

[B@R5uk]

Что-то такое ощущение, что я веду беседу со своим вымышленным собеседником. Он сидит такой на против меня молча и укоризненно-вопросительно смотрит, мол "Что ты сегодня такого наворотил? И зачем? Что сделал, чтобы разобраться с ранее возникшими вопросами и ошибками?" А я сижу и в письменной форме излагаю ему свои мысли и действия.

Неужели никому не интересна задача о назначениях? Или может я обсуждаю какие-то неприличные моменты касательно неё? Или я ковыряюсь с чем-то на столько тривиальным, что никто даже не обронит пару слов с рекомендациями? Ну уж точно дело не в том, что на форуме нет специалистов! Один, в любом случае, проходил и даже кодом и статьёй поделился, за что ему большое СПАСИБО. Жаль, что я пока хочу довести до логического конца классический Венгерский алгоритм, а то, что я прочёл в статьях о предложенном методе масштабирования стоимости, пока не оставило в памяти никакого конкретного понимания.

Мда... В любом случае, беседа с воображаемым собеседником способствует моему продвижению по крутому и извилистому горному пути к вершинам знаний. Только извиняюсь наперёд, если обсуждение превращается в мой личный блог по программированию.

B@R5uk в сообщении #1499526 писал(а):

Осталось убедится, что нигде нет ошибок и загнать код в программу для боевого тестирования для сравнения с остальными реализациями. Я сильно огорчусь, если этот новый метод не выйдет в лидеры.

Ура! Новый метод таки смог! Тестирующая программа. Результаты тестирований:

Используется синтаксис Text

==============================================================================================
          Random   Work       Data   __________________  Test Time (ms) / STD  _______________
            Seed   Size       Size       Array       Sorted Set   Priority Queue   Binary Heap
----------------------------------------------------------------------------------------------
   1610115425944     10   10000000   165.17  0.56   550.72  1.18   872.95  2.14   208.99  0.48
   1610115475256     10   10000000   164.90  0.35   561.82  1.47   855.30  1.42   208.40  0.35
   1610115517789     10   10000000   165.04  0.61   556.11  1.75   872.74  2.28   210.82  0.93
   1610115568275     10   10000000   164.86  0.52   556.17  1.59   857.04  1.92   208.36  0.47
   1610117989610     10   10000000   165.64  0.96   548.77  1.19   876.22  1.23   208.22  0.32
   1610118037186     10   10000000   166.23  0.36   554.65  2.51   870.98  1.26   210.52  0.71
   1610118078595     10   10000000   167.41  0.22   574.61  5.26   878.34  1.12   216.45  1.68

   1610116669439     15   10000000   204.60  0.38   593.17  1.70   677.24  3.41   226.62  0.67
   1610116724400     15   10000000   204.46  0.61   607.75  0.61   678.78  1.61   228.09  0.67
   1610116761923     15   10000000   199.47  0.60   595.69  1.11   681.58  1.86   228.34  0.50
   1610117822051     15   10000000   203.89  0.24   591.53  2.11   676.74  1.59   228.63  1.07
   1610117863730     15   10000000   204.03  0.44   602.82  2.76   672.82  1.88   227.58  0.53
   1610117903452     15   10000000   203.36  0.65   601.32  1.32   669.88  1.38   226.97  0.23
   1610117945930     15   10000000   204.19  0.32   602.41  1.21   675.95  1.98   227.38  1.17

   1610115618048     20   10000000   232.76  0.62   633.09  2.19   618.80  1.16   234.42  2.54
   1610115666885     20   10000000   235.57  0.60   627.64  2.87   620.94  2.25   231.95  0.85
   1610115720466     20   10000000   232.74  0.10   628.90  1.59   615.28  1.40   235.13  1.16
   1610118134569     20   10000000   232.01  0.50   634.51  1.59   618.28  1.21   234.37  0.71
   1610118176941     20   10000000   230.99  0.23   622.72  3.16   614.15  1.23   233.65  0.36
   1610118217097     20   10000000   233.09  0.69   623.19  1.69   621.32  0.87   234.84  0.42
   1610118915725     20   10000000   235.33  0.47   621.84  1.93   622.23  1.62   234.24  0.34

   1610116283300     30   10000000   257.23  0.48   660.04  2.75   570.27  1.19   246.63  0.43
   1610116323734     30   10000000   256.90  0.78   658.19  1.23   578.35  1.20   246.48  0.71
   1610116527870     30   10000000   259.80  2.85   654.62  1.42   581.29  1.66   246.28  0.68
   1610116621151     30   10000000   255.79  0.25   656.09  2.22   575.70  2.15   246.20  0.77
   1610118269309     30   10000000   257.69  0.43   651.54  2.58   577.40  1.94   246.76  0.99
   1610118573721     30   10000000   264.04  1.08   656.98  2.38   578.37  4.05   245.43  0.31
   1610118615442     30   10000000   256.87  0.33   657.64  2.50   581.05  2.20   245.25  0.59

   1610115778411     50    5000000   169.14  0.09   356.47  5.55   289.88  5.99   131.92  0.42
   1610115803175     50    5000000   166.59  0.18   343.09  1.07   283.66  3.44   131.74  0.57
   1610115826656     50    5000000   168.16  0.62   345.07  1.58   284.29  3.11   132.24  0.69
   1610118670955     50   10000000   333.53  0.20   685.63  1.16   554.18  1.54   262.17  0.68
   1610118775068     50   10000000   334.80  0.87   698.01  1.81   562.21  1.46   262.98  0.67
   1610118815402     50   10000000   338.20  0.66   697.75  3.51   563.09  0.93   262.70  1.32
   1610118859010     50   10000000   332.81  0.41   697.79  3.02   556.10  1.43   261.68  0.73

   1610117703915     75    5000000   227.37  0.30   365.05  0.80   290.06  4.08   142.19  0.42
   1610117731932     75    5000000   228.15  0.39   366.51  0.93   281.26  1.16   142.08  0.33
   1610117757698     75    5000000   228.33  0.56   361.14  1.71   281.21  0.76   141.83  0.27
   1610117783814     75    5000000   218.81  0.27   360.00  0.92   278.70  1.61   142.90  0.57
   1610118967564     75   10000000   456.71  0.44   723.24  1.11   569.35  1.00   283.69  0.67
   1610119012737     75   10000000   447.21  2.73   705.58  1.49   547.31  1.42   276.99  0.60
   1610119057192     75   10000000   448.42  0.21   720.64  2.45   560.51  1.47   282.77  0.89

   1610115852414    100    5000000   279.24  0.51   371.00  1.90   288.30  1.01   143.38  0.49
   1610115898876    100    5000000   282.18  0.44   372.58  0.95   291.00  2.83   143.45  0.72
   1610115924820    100    5000000   273.66  0.51   369.85  2.03   288.03  0.85   143.11  0.40
   1610117579738    100    5000000   275.47  0.34   366.78  1.58   285.72  0.62   143.01  0.72
   1610117613602    100    5000000   272.56  0.51   370.57  1.18   288.42  1.45   142.76  0.21
   1610117639800    100    5000000   273.02  0.17   369.64  1.47   286.79  0.79   142.44  0.28
   1610117668904    100    5000000   286.73  0.43   370.87  0.76   287.24  2.40   142.52  0.42

   1610116812045    150    5000000   397.91  0.33   389.02  1.23   295.30  1.47   153.10  0.54
   1610116848950    150    5000000   389.50  0.42   397.36  1.71   300.05  4.40   152.14  0.41
   1610116880731    150    5000000   389.59  1.50   394.71  0.62   303.18  2.40   151.90  0.38
   1610116914250    150    5000000   397.32  0.43   392.69  0.83   300.24  3.91   152.50  0.27
   1610116944449    150    5000000   389.26  0.60   392.85  0.73   303.71  1.94   152.55  0.68
   1610119119701    150    5000000   390.40  0.85   390.13  1.13   295.60  1.03   153.14  0.45
   1610119149878    150    5000000   389.78  0.36   392.48  1.42   302.14  3.55   151.98  0.50

   1610115980373    200    5000000   517.33  0.37   415.23  1.00   306.10  3.07   161.57  0.34
   1610116014257    200    5000000   516.24  0.56   422.75  1.71   308.67  2.52   161.43  0.41
   1610116047558    200    5000000   516.41  0.29   417.88  1.33   304.92  2.41   161.82  0.92
   1610117370735    200    5000000   518.51  1.85   416.10  1.77   304.30  0.78   161.08  0.30
   1610117411138    200    5000000   516.10  0.42   422.30  1.95   307.25  1.68   161.68  0.62
   1610117443848    200    5000000   514.88  0.37   421.76  0.84   308.77  3.01   161.75  0.76
   1610117479737    200    5000000   516.73  0.85   418.80  1.23   303.43  1.86   160.89  0.34

   1610116095794    300    5000000   828.02  0.44   444.28  0.70   321.03  1.17   169.41  0.81
   1610116161906    300    5000000   825.52  0.56   435.91  0.99   318.66  1.68   169.08  0.25
   1610116201100    300    5000000   826.01  0.30   435.84  0.85   320.81  1.03   170.46  0.37
   1610117038876    300    5000000   789.45  0.27   441.11  1.63   314.21  0.52   169.88  0.39
   1610117080394    300    5000000   782.95  0.28   439.12  1.12   318.17  1.74   168.90  0.65
   1610117124819    300    5000000   828.32  0.93   435.95  1.02   316.46  1.76   169.20  0.70
   1610117165056    300    5000000   827.98  0.37   439.60  0.90   318.72  1.53   168.39  0.38
==============================================================================================
 

Уже на размере рабочего массива в 20 элементов метод с двоичной кучей обгоняет наивный линейный поиск. Он так же стабильно в 2,5 раза быстрее упорядоченного множества. Про очередь с приоритетом я вообще молчу, потому что её быстродейтвие на малых размерах рабочего массива нереально деградирует. Надо бы установить Матлаб и сделать красивый и наглядный график по этим результатам.

Основной тонкостью в реализации было сделать так, чтобы все четыре метода делали одно и тоже. Разумеется, каждый из них выполняет задачу по-своему, но результат должен быть один. Дело в том, что иногда бывает так, что в рабочем массиве оказывается несколько одинаковых минимальных величин; и тестируемые методы, вообще говоря, имеют разные подходы к таким случаям. Линейный поиск выдаёт первый минимальный элемент, если их несколько. Множество вообще не допускает одинаковых элементов, так что здесь без доработки вообще работать не будет. Очередь в случае нескольких минимумов выдаёт случайный, двоичная куча — аналогично. По этой причине во всех структурах с логарифмическим временем надо добавить дополнительную сортировку элементов по индексам. Для конечной задачи о назначениях этого делать, разумеется, не нужно, но в тестирующей программе требуется действовать последовательно: каждый метод в одинаковых условиях должен выдавать одну и ту же ячейку массива.

Кроме того, конечная реализация с двоичной кучей получилась весьма громоздкой. Нужно подумать над тем, как её можно укоротить и оптимизировать. Надо будет удалить дополнительную сортировку по индексу, но одного этого всё равно ещё мало. Надо подумать, нельзя ли избавиться от каких-нибудь переменных:

Используется синтаксис Java

    @SuppressWarnings("unused")
    private static long testHeap () {
        int k, l, dataIndex, heapSize, valueIndex, value, auxIndex, nextAuxIndex, heapIndex;
        int bestValue, bestIndex, nextValue, childAuxIndex, childHeapIndex, childValue;
        long result;
        boolean flag;
        boolean [] usedFlags;
        int [] auxMinima, auxIndices, binaryHeap;
        
        dataIndex  = 0;
        result     = 0;
        usedFlags  = new boolean [workSize];
        auxMinima  = new int     [workSize];
        auxIndices = new int     [workSize];
        binaryHeap = new int     [workSize];
        auxIndex   = 0;
        
        while (dataSize > dataIndex) {
            
            Arrays .fill (usedFlags, false);
            Arrays .fill (auxMinima, Integer .MAX_VALUE);
            Arrays .fill (auxIndices, -1);
            heapSize = 0;
            
            for (k = 0; workSize > k; ++k) {
                
                for (l = 0; packSize > l && dataSize > dataIndex; ++l, ++dataIndex) {
                    valueIndex = testData_Indices [dataIndex];
                    if (usedFlags [valueIndex]) {
                        continue;
                    }
                    value = testData_Values  [dataIndex];
                    flag = true;
                    if (-1 == auxIndices [valueIndex]) {
                        auxIndex = heapSize;
                        ++heapSize;
                        flag = false;
                    } else if (auxMinima [valueIndex] > value) {
                        auxIndex = auxIndices [valueIndex];
                        flag = false;
                    }
                    if (flag) {
                        continue;
                    }
                    auxMinima [valueIndex] = value;
                    while (0 < auxIndex) {
                        nextAuxIndex = (auxIndex - 1) / 2;
                        heapIndex = binaryHeap [nextAuxIndex];
                        nextValue = auxMinima [heapIndex];
                        if (value > nextValue || value == nextValue && valueIndex >= heapIndex) {
                            break;
                        }
                        binaryHeap [auxIndex] = heapIndex;
                        auxIndices [heapIndex] = auxIndex;
                        auxIndex = nextAuxIndex;
                    }
                    binaryHeap [auxIndex] = valueIndex;
                    auxIndices [valueIndex] = auxIndex;
                }
                
                if (debug && advanced) {
                    displayArray (auxIndices);
                }
                
                if (0 == heapSize) {
                    break;
                }
                
                bestIndex = binaryHeap [0];
                bestValue = auxMinima [bestIndex];
                auxIndices [bestIndex] = -1;
                --heapSize;
                valueIndex = binaryHeap [heapSize];
                value = auxMinima [valueIndex];
                auxIndex = 0;
                //binaryHeap [0] = valueIndex;
                
                while (true) {
                    nextValue = value;
                    heapIndex = valueIndex;
                    nextAuxIndex = auxIndex;
                    childAuxIndex = 2 * auxIndex + 1;
                    if (heapSize > childAuxIndex) {
                        childHeapIndex = binaryHeap [childAuxIndex];
                        childValue = auxMinima [childHeapIndex];
                        if (nextValue > childValue || nextValue == childValue && heapIndex > childHeapIndex) {
                            nextValue = childValue;
                            heapIndex = childHeapIndex;
                            nextAuxIndex = childAuxIndex;
                        }
                    }
                    ++childAuxIndex;
                    if (heapSize > childAuxIndex) {
                        childHeapIndex = binaryHeap [childAuxIndex];
                        childValue = auxMinima [childHeapIndex];
                        if (nextValue > childValue || nextValue == childValue && heapIndex > childHeapIndex) {
                            heapIndex = childHeapIndex;
                            nextAuxIndex = childAuxIndex;
                        }
                    }
                    if (auxIndex == nextAuxIndex) {
                        break;
                    }
                    binaryHeap [auxIndex] = heapIndex;
                    auxIndices [heapIndex] = auxIndex;
                    auxIndex = nextAuxIndex;
                }
                binaryHeap [auxIndex] = valueIndex;
                auxIndices [valueIndex] = auxIndex;
                
                result += bestValue;
                usedFlags [bestIndex] = true;
                
                if (debug) {
                    if (advanced) {
                        displayArray (auxMinima, usedFlags);
                        displayArray (auxIndices);
                    }
                    System .out .println (dataIndex + "  " + bestIndex + "  " + bestValue + "  " + result);
                }
            }
        }
        
        return result;
    }
 

[mihaild]

B@R5uk в сообщении #1499791 писал(а):

Неужели никому не интересна задача о назначениях? Или может я обсуждаю какие-то неприличные моменты касательно неё? Или я ковыряюсь с чем-то на столько тривиальным, что никто даже не обронит пару слов с рекомендациями?

Для меня пока происходящее выглядит как будто вы сами потихоньку разбираетесь и пишете, что происходит. Если есть какие-то конкретные вопросы - спрашивайте.

(Оффтоп)

Код на джаве читать очень не хочется, я её как раз на каникулах начал учить, и уже успел возненавидеть.

[B@R5uk]

mihaild в сообщении #1499794 писал(а):

Если есть какие-то конкретные вопросы - спрашивайте.

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

[B@R5uk]

Графическое представление полученных мной экспериментальных данных (на процессоре с частотой ядра 3,00 МГц и кэшем 64КБ):



Надо бы подумать, как двоичную кучу можно прикрутить к алгоритму Дейкстры.

[B@R5uk]

Простенькая статья о представлении графов в памяти компьютера. Она совсем тривиальная и не полностью раскрывает тему, но ключевые идеи упомянуты.

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

[mihaild]

(в алгоритм не вникал, так что ниже могут быть глупости; если это так - скажите)

B@R5uk в сообщении #1499795 писал(а):

Из первоочередных сейчас стоят оптимизация кода двоичной кучи

Я, возможно, слепой, но где у вас удаление чего-то из кучи? Вижу только добавление.
В любом случае, лучше в куче держать сразу сравниваемые значения - бегать по куче массивов это долго.
Вообще очень странно, что очередь с приоритетом сильно медленнее кучи, они по идее должны делать примерно одно и то же.

B@R5uk в сообщении #1499795 писал(а):

Я так понимаю, что желательно чтобы это представление хранилось в виде двух-нескольких массивов, чтобы процессор прокешировал их и затем шустро обсчитал, верно?

Кеширование идет фрагментами по 64 байта, плюс есть префетч. Желательно, чтобы обращения к памяти были прямыми и шли к последовательным кускам.
Так как нам в данном случае нужно (если я правильно понимаю) нужно перебирать ребра из вершины, то эффективнее всего хранить все ребра подряд, отсортированные по исходящей вершине, и отдельно - число ребер у каждой вершины и индекс первого ребра.
Но скорее всего это не будет сильно быстрее, чем просто двумерный массив с ребрами.

[B@R5uk]

mihaild в сообщении #1500049 писал(а):

Я, возможно, слепой, но где у вас удаление чего-то из кучи? Вижу только добавление.

Оно законспирировано. После проверки if (0 == heapSize) { break; } идёт код, который как раз отвечает за удаление головы очереди. Для этого он:
1) уменьшает размер очереди-дерева (--heapSize;)
2) копирует (виртуально) элемент дерева с максимальным (в массиве, хранящим очередь) индексом на место головы дерева (элемент с нулевым индексом) и
3) осуществляет "утопление" скопированного элемента от головы бинарного дерева в сторону листьев, чтобы восстановить свойство "кучевости" бинарного дерева.
Утопление — это всё, что внутри цикла while (true) {...} и непосредственно перед ним.

mihaild в сообщении #1500049 писал(а):

В любом случае, лучше в куче держать сразу сравниваемые значения - бегать по куче массивов это долго.

Вы имеете в виду, что можно обойтись меньшим числом массивов? Или что значения надо хранить не параллельно с рабочим массивом, а параллельно с массивом, хранящим дерево? Просто без двух взаимообратных массивов с индексами не обойтись, иначе придётся добавлять ещё один вложенный цикл поиска нужного индекса: один из этих массивов позволяет сразу найти элемент рабочего массива по ассоциированному с ним элементу очереди, а другой — наоборот, элемент очереди по ассоциированному с ним элементу рабочего массива.

mihaild в сообщении #1500049 писал(а):

Вообще очень странно, что очередь с приоритетом сильно медленнее кучи, они по идее должны делать примерно одно и то же.

Дело в том, что стандартная очередь с приоритетом PriorityQueue не содержит операции обновления заданного элемента, который уже содержится в ней. Вместо этого приходится просто помещать в очередь новое значение, а старое при этом не удаляется. По мере извлечения элементов из очереди проверяется их актуальность, и только тогда старые значения отбрасываются. Это приводит к замусориванию очереди и неконтролируемому её росту. Как следствие, быстродействие сильно деградирует.

Моя же реализация с двоичной кучей позволяет апдейтить значения элементов очереди, перемещая их ближе к голове, когда соответствующие значения рабочего массива уменьшаются. Никакого замусоривания, и минимальный элемент искать не надо: им является корень дерева — элемент с индексом 0 в хранящем дерево массиве.

mihaild в сообщении #1500049 писал(а):

Кеширование идет фрагментами по 64 байта, плюс есть префетч. Желательно, чтобы обращения к памяти были прямыми и шли к последовательным кускам.

Спасибо! Выделенный момент понял. Про остальное было бы здорово почитать что-нибудь доступное. Например, почему именно 64 байта, разве это не зависит от процессора? И как работает упреждающая выборка? Вообще, с этими новыми процессорами столько заморочек, что даже руки опускаются...

mihaild в сообщении #1500049 писал(а):

Так как нам в данном случае нужно (если я правильно понимаю) перебирать ребра из вершины

Верно. Каждая строка таблицы весов соответствует левой вершине двудольного графа. И на каждой внутренней итерации Венгерского алгоритма просматриваются и обрабатываются все рёбра, которые ведут из этой вершины.

mihaild в сообщении #1500049 писал(а):

то эффективнее всего хранить все ребра подряд, отсортированные по исходящей вершине, и отдельно - число ребер у каждой вершины и индекс первого ребра.

Спасибо за рекомендацию. По второй ссылке этот подход называется "Прямое звёздное представление" (Forward Star representation). Буду думать как через него всё реализовать. Единственное, в моём случае граф сильно разреженный, и число рёбер, выходящих из вершины, не больше пяти. Поэтому последовательные чтения будут идти весьма короткими порциями, так как сами вершины на среднем цикле Венгерского алгоритма перебираются случайным образом (в зависимости от того, какой путь короче).

[mihaild]

B@R5uk в сообщении #1500074 писал(а):

Или что значения надо хранить не параллельно с рабочим массивом, а параллельно с массивом, хранящим дерево?

Так, я, видимо, не очень понял логику работы с кучей. И в любом случае, если вы хотите её оптимизировать, скорее всего удобнее будет вынести её в отдельный класс.
Если я правильно понял, то в auxMinima у вас хранятся значения, индексы к которым хранятся в binaryHeap, так что по сути значения читаются как auxMinima[binaryHeap[i]]. Если возможно - то эффективнее значения хранить в binaryHeap, так что читаться они будут как binaryHeap[i].value - одно чтение из памяти вместо двух (по крайней мере так было бы в плюсах; так как в джаве это будет странным объектом, то не удивлюсь, если там еще непредсказуемое количество разыменований указателей появится).

B@R5uk в сообщении #1500074 писал(а):

Про остальное было бы здорово почитать что-нибудь доступное.

What every programmer should know about memory - не то чтобы очень доступное, но ничего такого же уровня я не знаю.

B@R5uk в сообщении #1500074 писал(а):

почему именно 64 байта, разве это не зависит от процессора?

Зависит, но почти у всех встречающихся на практике 64 байта.

B@R5uk в сообщении #1500074 писал(а):

И как работает упреждающая выборка?

Данные загружаются из памяти в кеш до того, как они реально нужны (а процессор в это время что-то делает с уже загруженными данными). Для этого есть специальные инструкции, а так же какая-то автоматизация (самая простая - вместе с нужной линией загружается соседняя).

B@R5uk в сообщении #1500074 писал(а):

Единственное, в моём случае граф сильно разреженный, и число рёбер, выходящих из вершины, не больше пяти.

Тогда может оказаться эффективным просто завести массив из $5\cdot n$ элементов, ребра из $i$-й вершины хранятся в элементах с $5\cdot i$-го по $5\cdot i + 4$-й, если ребер меньше $5$ - как-то помечаются как несуществующие.

Вообще двоичная куча плохо дружит с кешем. Есть cache oblivious кучи, но я про них, кроме факта их существования, ничего не знаю.

[B@R5uk]

mihaild в сообщении #1500089 писал(а):

What every programmer should know about memory - не то чтобы очень доступное, но ничего такого же уровня я не знаю.

Потрясающая статья! Всё описывается достаточно подробно и доходчиво, в то же время без лишних разглагольствований и по существу. Наличие электрических схем в объяснении, мне, как радиолюбителю, весьма импонирует. Большое СПАСИБО за наводку!

mihaild в сообщении #1500089 писал(а):

Так, я, видимо, не очень понял логику работы с кучей.

У меня алгоритм из вики. Только я добавил ассоциированный массив, вручную раскрыл рекурсию и операции свопа двух ячеек заменил на обычное смещение с присваиванием в конце. Это возможно, потому что при обмене содержимым двух ячеек массива одна и та же величина постоянно содержится в одной из меняемых ячеек. Что при удалении элемента, что при добавлении.

mihaild в сообщении #1500089 писал(а):

И в любом случае, если вы хотите её оптимизировать, скорее всего удобнее будет вынести её в отдельный класс.

Да. Это разделит данные и методы по смыслу, что внесёт ясность в алгоритм в общем. На быстродействие повлиять не должно.

Файл ArrayMinimumClass.java:

Используется синтаксис Java

import java.util.*;

public class ArrayMinimumClass {
    
    private boolean [] inUse;
    private int [] values, heapReverse, indicesHeap;
    private int heapSize;
    
    public ArrayMinimumClass (int size) {
        inUse       = new boolean [size];
        values      = new int     [size];
        heapReverse = new int     [size];
        indicesHeap = new int     [size];
    }
    
    public void init () {
        Arrays .fill (inUse, false);
        heapSize = 0;
    }
    
    public boolean update (int valueIndex, int value) {
        int heapIndex, nextHeapIndex, nextValueIndex;
        
        if (inUse [valueIndex]) {
            if (values [valueIndex] > value) {
                heapIndex = heapReverse [valueIndex];
            } else {
                return false;
            }
        } else {
            inUse [valueIndex] = true;
            heapIndex = heapSize;
            ++heapSize;
        }
        values [valueIndex] = value;
        
        while (0 < heapIndex) {
            nextHeapIndex = (heapIndex - 1) / 2;
            nextValueIndex = indicesHeap [nextHeapIndex];
            if (value > values [nextValueIndex]) {
                break;
            }
            heapReverse [nextValueIndex] = heapIndex;
            indicesHeap [heapIndex] = nextValueIndex;
            heapIndex = nextHeapIndex;
        }
        heapReverse [valueIndex] = heapIndex;
        indicesHeap [heapIndex] = valueIndex;
        
        return true;
    }
    
    public boolean isInUse (int valueIndex) {
        return inUse [valueIndex];
    }
    
    public int getValue (int valueIndex) {
        return values [valueIndex];
    }
    
    public boolean isEmpty () {
        return 0 == heapSize;
    }
    
    public int getMinimum () {
        return values [indicesHeap [0]];
    }
    
    public int getMinimumIndex () {
        return indicesHeap [0];
    }
    
    public void remove () {
        int valueIndex, value, heapIndex, nextValue, nextValueIndex, nextHeapIndex;
        int childIndex, childValueIndex, childValue;
        
        //inUse [indicesHeap [0]] = false;
        --heapSize;
        valueIndex = indicesHeap [heapSize];
        value = values [valueIndex];
        heapIndex = 0;
        
        while (true) {
            nextValueIndex = valueIndex;
            nextValue = value;
            nextHeapIndex = heapIndex;
            childIndex = 2 * heapIndex + 1;
            if (heapSize > childIndex) {
                childValueIndex = indicesHeap [childIndex];
                childValue = values [childValueIndex];
                if (nextValue > childValue) {
                    nextValue = childValue;
                    nextValueIndex = childValueIndex;
                    nextHeapIndex  = childIndex;
                }
            } else {
                break;
            }
            ++childIndex;
            if (heapSize > childIndex) {
                childValueIndex = indicesHeap [childIndex];
                if (nextValue > values [childValueIndex]) {
                    nextValueIndex = childValueIndex;
                    nextHeapIndex  = childIndex;
                }
            }
            if (heapIndex == nextHeapIndex) {
                break;
            }
            heapReverse [nextValueIndex] = heapIndex;
            indicesHeap [heapIndex] = nextValueIndex;
            heapIndex = nextHeapIndex;
        }
        heapReverse [valueIndex] = heapIndex;
        indicesHeap [heapIndex] = valueIndex;
    }
    
    public void displayHeapIndices () {
        for (int k = 0; inUse .length > k; ++k) {
            if (inUse [k]) {
                System .out .println (String .format ("%4d ", heapReverse [k]));
            } else {
                System .out .println ("   - ");
            }
        }
    }
    
    public void displayValues () {
        for (int k = 0; inUse .length > k; ++k) {
            if (inUse [k]) {
                System .out .println (String .format ("%4d ", values [k]));
            } else {
                System .out .println ("   - ");
            }
        }
    }
}
 

mihaild в сообщении #1500089 писал(а):

...по сути значения читаются как auxMinima[binaryHeap[i]]. Если возможно - то эффективнее значения хранить в binaryHeap, так что читаться они будут как binaryHeap[i].value - одно чтение из памяти вместо двух...

Из-за ассоциативности с массивом работа с кучей (во время добавления и удаления элемента) производится так, что индексы i и binaryHeap[i] используются параллельно. (Пары переменных heapIndex с valueIndex, nextHeapIndex с nextValueIndex и childIndex с childValueIndex, соответственно, в коде выше). Поэтому как раз во время обработки кучи всё равно, где хранятся значения: ассоциативно с кучей, либо же ассоциативно с массивом. В одном случае для доступа к значению будет использовать один индекс, в другом — другой. Совсем другое дело, когда производится доступ к массиву по индексу. А это происходит чаще, чем изменение кучи (на сколько чаще затрудняюсь утверждать). В моей текущей реализации такое обращение производится через одну разиндексацию. Если значения хранить ассоциативно с кучей, то их потребуется две. Я, кстати, долго думал над этим вопросом: "как лучше хранить значения, в куче, либо же в массиве?" В итоге понял, что лучше таки в массиве, чтобы доступ по индексу был быстрый.

Тут ещё есть другая забавная проблема. Иногда бывает очень трудно дать переменным говорящие имена так, чтобы они с одной стороны отражали смысл хранящихся в них значений, а с другой — не превращались в мини-рассказ на несколько строчек. Этот случай как раз такой. В коде выше я в очередной раз кардинально переименовал всех участников вычислений, поэтому некоторые переменные имеют похожие или одинаковые названия с переменными двух предыдущих вариантов этого кода, но содержат другие или даже прямо противоположные по смыслу значения. Тем не менее, считаю, что последний вариант самый осмысленный.

Остальной код Венгерского алгоритма остался пока тем же самым:

Используется синтаксис Java

import java.util.*;

public class Study_Hungarian_5 {
    
//    private static final long seed = 1610632274999L;
    private static final long seed = System .currentTimeMillis ();
    private static final Random rng = new Random (seed);
    
    private static final int width    = 12;
    private static final int rndCount = 3;
    private static final int minCount = 1;
    private static final int height   = 10;
    private static final int maxValue = 50;
    private static int [] [] weights;
    
    private static int [] assignment, matchings, wayBack;
    private static int [] rowsPotentials, columnsPotentials;
    private static ArrayMinimumClass auxMinima;
    
    private static boolean [] usedColumns, usedRows;
    
    private static int currentRow, nextColumn;
    
    public static void main (String [] args) {
        
        System .out .println ("Seed " + seed);
        printSeparator ();
        makeRandomTest ();
        diplayWeights ();
        findAssignment ();
        printSeparator ();
        diplayWeights ();
    }
    
    private static void makeRandomTest () {
        int k, l, index;
        int [] countByColumn;
        
        weights    = new int [height] [width];
        assignment = new int [height];
        matchings  = new int          [width];
        Arrays .fill (assignment, -1);
        Arrays .fill (matchings,  -1);
        
        for (k = 0; height > k; ++k) {
            Arrays .fill (weights [k], Integer .MAX_VALUE);
        }
        
        countByColumn = new int [width];
        
        for (k = 0; height > k; ++k) {
            for (l = 0; rndCount > l; ) {
                index = rng .nextInt (width);
                if (Integer .MAX_VALUE != weights [k] [index]) {
                    continue;
                }
                weights [k] [index] = rng .nextInt (maxValue);
                ++countByColumn [index];
                ++l;
            }
            for (l = 0; minCount > l; ++l) {
                index = findMinCountIndex (countByColumn);
                weights [k] [index] = rng .nextInt (maxValue);
                ++countByColumn [index];
            }
        }
    }
    
    private static int findMinCountIndex (int [] countByColumn) {
        int k, count, bestCount, bestIndex;
        
        bestCount = Integer .MAX_VALUE;
        bestIndex = -1;
        
        for (k = 0; width > k; ++k) {
            count = countByColumn [k];
            if (bestCount > count) {
                bestCount = count;
                bestIndex = k;
            }
        }
        
        return bestIndex;
    }
    
    @SuppressWarnings("unused")
    private static void findAssignment () {
        int delta, value, rowIndex, columnIndex, currentColumn;
        
        if (height > width) {
            throw new IllegalArgumentException ("\n\nData height must be less than or equal data width.\n");
        }
        
        rowsPotentials    = new int     [height];
        columnsPotentials = new int     [width];
        wayBack           = new int     [width];
        usedRows          = new boolean [height];
        usedColumns       = new boolean [width];
        auxMinima = new ArrayMinimumClass (width);
        
        printSeparator ();
        diplayData ();
        
        for (rowIndex = 0; height > rowIndex; ++rowIndex) {
            
            //      Initialization of new iteration
            
            Arrays .fill (usedColumns, false);
            Arrays .fill (usedRows,    false);
            auxMinima .init ();
            currentRow = rowIndex;
            delta = 0;
            
            //      Looking for shortest augmenting path starting with current row
            
            do {
                usedRows [currentRow] = true;
                
                //      Updating list of lengths of searched paths, marking way back
                
                for (columnIndex = 0; width > columnIndex; ++columnIndex) {
                    if (usedColumns [columnIndex]) {
                        continue;
                    }
                    value = weights         [currentRow] [columnIndex];
                    if (Integer .MAX_VALUE == value) {
                        continue;
                    }
                    value += delta;
                    value -= rowsPotentials [currentRow]
                           + columnsPotentials           [columnIndex];
                    if (auxMinima .update (columnIndex, value)) {
                        wayBack   [columnIndex] = currentRow;
                    }
                }
                
                //      Looking for the best unused column and associated path length
                
                if (auxMinima .isEmpty ()) {
                    throw new IllegalArgumentException ("\n\nNo assignment is possible.\n");
                }
                
                nextColumn = auxMinima .getMinimumIndex ();
                delta      = auxMinima .getMinimum ();
                auxMinima .remove ();
                
                diplayStep ();
                
                usedColumns            [nextColumn] = true;
                currentRow = matchings [nextColumn];
                
                //      If the best column is not free, then continue iterations
                
            } while (-1 != currentRow);
            
            //      Recalculating potentials
            
            for (currentRow = 0; rowIndex > currentRow; ++currentRow) {
                if (!usedRows [currentRow]) {
                    continue;
                }
                rowsPotentials [currentRow] +=
                        delta - auxMinima .getValue (assignment [currentRow]);
            }
            
            rowsPotentials [rowIndex] += delta;
            
            for (columnIndex = 0; width > columnIndex; ++columnIndex) {
                if (!usedColumns [columnIndex]) {
                    continue;
                }
                columnsPotentials [columnIndex] -=
                        delta - auxMinima .getValue (columnIndex);
            }
            
            //      Restoring new assignment
            
            do {
                currentRow = wayBack [nextColumn];
                matchings [nextColumn] = currentRow;
                currentColumn = assignment [currentRow];
                assignment [currentRow] = nextColumn;
                nextColumn = currentColumn;
            } while (rowIndex != currentRow);
            
            printSeparator ();
            diplayData ();
        }
    }
    
    private static void diplayWeights () {
        int k, l, m, value;
        
        System .out .println ();
        for (k = 0; height > k; ++k) {
            m = assignment [k];
            for (l = 0; width > l; ++l) {
                value = weights [k] [l];
                if (Integer .MAX_VALUE == value) {
                    if (m == l) {
                        System .out .print (" ####");
                    } else {
                        System .out .print ("   - ");
                    }
                } else {
                    if (m == l) {
                        System .out .print (String .format ("%4s]", "[" + value));
                    } else {
                        System .out .print (String .format ("%4d ", value));
                    }
                }
            }
            System .out .println ();
        }
        System .out .println ();
    }
    
    private static void diplayData () {
        int k, l, m, value;
        
        System .out .println ();
        for (k = 0; height > k; ++k) {
            System .out .print ("#" + k + ((10 > k) ? " " : ""));
            m = assignment [k];
            for (l = 0; width > l; ++l) {
                value = weights [k] [l];
                if (Integer .MAX_VALUE != value) {
                    value -= rowsPotentials [k] + columnsPotentials [l];
                }
                printValue (value, m == l);
            }
            System .out .print ("  ~ ");
            System .out .print (String .format ("%4d ", rowsPotentials [k]));
            System .out .println ();
        }
        System .out .print ("   ");
        for (l = 0; width > l; ++l) {
            System .out .print ("   | ");
        }
        System .out .print ("\n   ");
        for (l = 0; width > l; ++l) {
            System .out .print (String .format ("%4d ", columnsPotentials [l]));
        }
        System .out .println ();
        System .out .println ();
    }
    
    private static void diplayStep () {
        int k;
        
        System .out .print ("#" + currentRow + " row:\n   ");
        for (k = 0; width > k; ++k) {
            if (usedColumns [k]) {
                System .out .print ("   + ");
                continue;
            }
            if (!auxMinima .isInUse (k)) {
                System .out .print ("   - ");
                continue;
            }
            printValue (auxMinima .getValue (k), nextColumn == k);
        }
        System .out .print ("\n   ");
        for (k = 0; width > k; ++k) {
            if (usedColumns [k]) {
                System .out .print ("   + ");
                continue;
            }
            if (!auxMinima .isInUse (k)) {
                System .out .print ("   - ");
                continue;
            }
            printValue (wayBack [k], false);
        }
        System .out .println ();
    }
    
    private static void printValue (int value, boolean flag) {
        if (Integer .MAX_VALUE == value) {
            if (flag) {
                System .out .print (" ####");
            } else {
                System .out .print ("   - ");
            }
        } else {
            if (flag) {
                System .out .print (String .format ("%4s]", "[" + value));
            } else {
                System .out .print (String .format ("%4d ", value));
            }
        }
    }
    
    private static void printSeparator () {
        System .out .println ();
        System .out .println ("================================================================================");
    }
}
 

Думаю, в первую очередь надо переработать циклы пересчёта потенциалов. В цикле поиска кратчайшего пути надо не просто помечать задействованные строки и столбцы, а помещать их в список. А при пересчёте — не проходить по всем элементам, проверяя были ли они задействованы, а сразу брать элементы из списков. Количество действий гарантированно сократится, хоть и не уменьшит степень трудоёмкости алгоритма в целом. Затем уже можно будет заняться видом, в котором представляются входные переменные алгоритма.

[B@R5uk]

B@R5uk в сообщении #1501062 писал(а):

Думаю, в первую очередь надо переработать циклы пересчёта потенциалов.

Реализовал:

Используется синтаксис Java

import java.util.*;

public class Study_Hungarian_6 {
    
//    private static final long seed = 1610632274999L;
    private static final long seed = System .currentTimeMillis ();
    private static final Random rng = new Random (seed);
    
    private static final int width    = 12;
    private static final int rndCount = 3;
    private static final int minCount = 1;
    private static final int height   = 10;
    private static final int maxValue = 50;
    private static int [] [] weights;
    
    private static int [] assignment, matchings, wayBack;
    private static int [] rowsPotentials, columnsPotentials;
    private static ArrayMinimumClass auxMinima;
    
    private static boolean [] usedColumns;
    
    private static int workRow, nextColumn;
    
    public static void main (String [] args) {
        
        System .out .println ("Seed " + seed);
        printSeparator ();
        makeRandomTest ();
        diplayWeights ();
        findAssignment ();
        printSeparator ();
        diplayWeights ();
    }
    
    private static void makeRandomTest () {
        int k, l, index;
        int [] countByColumn;
        
        weights    = new int [height] [width];
        assignment = new int [height];
        matchings  = new int          [width];
        Arrays .fill (assignment, -1);
        Arrays .fill (matchings,  -1);
        
        for (k = 0; height > k; ++k) {
            Arrays .fill (weights [k], Integer .MAX_VALUE);
        }
        
        countByColumn = new int [width];
        
        for (k = 0; height > k; ++k) {
            for (l = 0; rndCount > l; ) {
                index = rng .nextInt (width);
                if (Integer .MAX_VALUE != weights [k] [index]) {
                    continue;
                }
                weights [k] [index] = rng .nextInt (maxValue);
                ++countByColumn [index];
                ++l;
            }
            for (l = 0; minCount > l; ++l) {
                index = findMinCountIndex (countByColumn);
                weights [k] [index] = rng .nextInt (maxValue);
                ++countByColumn [index];
            }
        }
    }
    
    private static int findMinCountIndex (int [] countByColumn) {
        int k, count, bestCount, bestIndex;
        
        bestCount = Integer .MAX_VALUE;
        bestIndex = -1;
        
        for (k = 0; width > k; ++k) {
            count = countByColumn [k];
            if (bestCount > count) {
                bestCount = count;
                bestIndex = k;
            }
        }
        
        return bestIndex;
    }
    
    @SuppressWarnings("unused")
    private static void findAssignment () {
        int delta, value, addedRow, workColumn, usedRowsCount, rowIndex;
        int [] usedRowsList;
        
        if (height > width) {
            throw new IllegalArgumentException ("\n\nData height must be less than or equal data width.\n");
        }
        
        usedRowsList      = new int     [height];
        rowsPotentials    = new int     [height];
        columnsPotentials = new int     [width];
        wayBack           = new int     [width];
        usedColumns       = new boolean [width];
        auxMinima = new ArrayMinimumClass (width);
        
        printSeparator ();
        diplayData ();
        
        //      Adding rows one by one into partial solution
        
        for (addedRow = 0; height > addedRow; ++addedRow) {
            
            //      Initialization of a new iteration
            
            Arrays .fill (usedColumns, false);
            auxMinima .init ();
            workRow = addedRow;
            usedRowsCount = 0;
            delta = 0;
            
            //      Looking for a shortest augmenting path starting with the row being added
            
            do {
                usedRowsList [usedRowsCount] = workRow;
                ++usedRowsCount;
                
                //      Updating list of lengths of searched paths, marking way back from column to row
                
                for (workColumn = 0; width > workColumn; ++workColumn) {
                    if (usedColumns [workColumn]) {
                        continue;
                    }
                    value = weights         [workRow] [workColumn];
                    if (Integer .MAX_VALUE == value) {
                        continue;
                    }
                    value -= rowsPotentials [workRow]
                           + columnsPotentials        [workColumn];
                    value += delta;
                    if (auxMinima .update (workColumn, value)) {
                        wayBack [workColumn] = workRow;
                    }
                }
                
                //      Looking for the best unused column and associated path length
                
                if (auxMinima .isEmpty ()) {
                    throw new IllegalArgumentException ("\n\nNo assignment is possible.\n");
                }
                
                nextColumn = auxMinima .getMinimumIndex ();
                delta      = auxMinima .getValue (nextColumn);
                auxMinima .remove ();
                
                diplayStep ();
                
                usedColumns         [nextColumn] = true;
                workRow = matchings [nextColumn];
                
                //      If the best column is not free, then continue iterations
                
            } while (-1 != workRow);
            
            //      Recalculating potentials
            
            rowsPotentials [addedRow] += delta;
            columnsPotentials [nextColumn] -=
                    delta - auxMinima .getValue (nextColumn);
            
            for (rowIndex = 1; usedRowsCount > rowIndex; ++rowIndex) {
                workRow = usedRowsList [rowIndex];
                workColumn = assignment [workRow];
                value = delta - auxMinima .getValue (workColumn);
                rowsPotentials    [workRow]    += value;
                columnsPotentials [workColumn] -= value;
            }
            
            //      Restoring new partial assignment
            
            do {
                workRow = wayBack [nextColumn];
                matchings [nextColumn] = workRow;
                workColumn = assignment [workRow];
                assignment [workRow] = nextColumn;
                nextColumn = workColumn;
            } while (addedRow != workRow);
            
            printSeparator ();
            diplayData ();
        }
    }
    
    private static void diplayWeights () {
        int k, l, m, value;
        
        System .out .println ();
        for (k = 0; height > k; ++k) {
            m = assignment [k];
            for (l = 0; width > l; ++l) {
                value = weights [k] [l];
                if (Integer .MAX_VALUE == value) {
                    if (m == l) {
                        System .out .print (" ####");
                    } else {
                        System .out .print ("   - ");
                    }
                } else {
                    if (m == l) {
                        System .out .print (String .format ("%4s]", "[" + value));
                    } else {
                        System .out .print (String .format ("%4d ", value));
                    }
                }
            }
            System .out .println ();
        }
        System .out .println ();
    }
    
    private static void diplayData () {
        int k, l, m, value;
        
        System .out .println ();
        for (k = 0; height > k; ++k) {
            System .out .print ("#" + k + ((10 > k) ? " " : ""));
            m = assignment [k];
            for (l = 0; width > l; ++l) {
                value = weights [k] [l];
                if (Integer .MAX_VALUE != value) {
                    value -= rowsPotentials [k] + columnsPotentials [l];
                }
                printValue (value, m == l);
            }
            System .out .print ("  ~ ");
            System .out .print (String .format ("%4d ", rowsPotentials [k]));
            System .out .println ();
        }
        System .out .print ("   ");
        for (l = 0; width > l; ++l) {
            System .out .print ("   | ");
        }
        System .out .print ("\n   ");
        for (l = 0; width > l; ++l) {
            System .out .print (String .format ("%4d ", columnsPotentials [l]));
        }
        System .out .println ();
        System .out .println ();
    }
    
    private static void diplayStep () {
        int k;
        
        System .out .print ("#" + workRow + " row:\n   ");
        for (k = 0; width > k; ++k) {
            if (usedColumns [k]) {
                System .out .print ("   + ");
                continue;
            }
            if (!auxMinima .isInUse (k)) {
                System .out .print ("   - ");
                continue;
            }
            printValue (auxMinima .getValue (k), nextColumn == k);
        }
        System .out .print ("\n   ");
        for (k = 0; width > k; ++k) {
            if (usedColumns [k]) {
                System .out .print ("   + ");
                continue;
            }
            if (!auxMinima .isInUse (k)) {
                System .out .print ("   - ");
                continue;
            }
            printValue (wayBack [k], false);
        }
        System .out .println ();
    }
    
    private static void printValue (int value, boolean flag) {
        if (Integer .MAX_VALUE == value) {
            if (flag) {
                System .out .print (" ####");
            } else {
                System .out .print ("   - ");
            }
        } else {
            if (flag) {
                System .out .print (String .format ("%4s]", "[" + value));
            } else {
                System .out .print (String .format ("%4d ", value));
            }
        }
    }
    
    private static void printSeparator () {
        System .out .println ();
        System .out .println ("================================================================================");
    }
}
 

Удалил массив флагов usedRows, но добавил массив индексов usedRowsList и счётчик usedRowsCount к нему. Оказалось, что все задействованные в поиска кратчайшего удлиняющего пути строки и столбцы (кроме первой строки и последнего столбца) образуют пары, принадлежащие текущему паросочетанию. При этом потенциалы столбцов и строк в паре изменяются на одну и ту же величину, из-за чего их можно (и нужно) обрабатывать вместе. Это не удивительно, так как паросочетания проходят по жёстким рёбрам, для которых сумма потенциалов равна весу ребра. Поэтому, изменяя потенциал строки, которой назначен столбец, необходимо изменить потенциал этого столбца на противоположную величину, иначе ребро перестанет быть жёстким (или, ещё хуже, потенциалы перестанут быть корректными). Как следствие, пересчёт потенциалов удалось реализовать одним красивым циклом:

Используется синтаксис Java

            //      Recalculating potentials
            
            rowsPotentials [addedRow] += delta;
            columnsPotentials [nextColumn] -=
                    delta - auxMinima .getValue (nextColumn);
            
            for (rowIndex = 1; usedRowsCount > rowIndex; ++rowIndex) {
                workRow = usedRowsList [rowIndex];
                workColumn = assignment [workRow];
                value = delta - auxMinima .getValue (workColumn);
                rowsPotentials    [workRow]    += value;
                columnsPotentials [workColumn] -= value;
            }
 

При этом первая обрабатываемая строка не имеет парного столбца, поскольку только добавляется в решение. А последний столбец является свободным, то есть не назначенным никакой строке. Так что их потенциалы обсчитываются отдельно перед циклом, а сам цикл начинается с индекса 1, а не 0. Надо заметить, что эта оптимизация делает обращение к строкам и столбцам совершенно непредсказуемым. Поэтому, не смотря на то, что с ней выполняется гарантированно меньше действий, чем в предыдущем варианте кода (и порой в разы меньше), ускорение работы получается только если все обрабатываемые данные имеют небольшой размер и поместились в кэш процессора. На ОЧЕНЬ больших задачах возможно и замедление — надо тестить. Кроме того, эта часть кода не влияет на общую временную сложность алгоритма.

Так же чутка переименовал переменные, чтобы они лучше отражали смысл хранящихся в них значений. Осталось переделать всё под forward star representation входных данных.

[B@R5uk]

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

Файл Study_Hungarian_7.java:

Используется синтаксис Java

import java.util.*;

public class Study_Hungarian_7 {
    
    //private static final long seed = 1610904187059L;
    private static final long seed = System .currentTimeMillis ();
    private static final Random rng = new Random (seed);
  
    public static void main(String[] args) {
        int [] [] weights;
        int [] solution;
        ForwardStarGraphClass problem;
        
        System .out .println ("Seed " + seed);
        //weights = makeRandomTest (10, 12, 0, 3, 1, 50);
        weights = makeRandomTest (14, 16, 10, 3, 2, 100);
        problem = convertToForwardStar (weights);
        displaySolution (problem, null);
        solution = HungarianAlgorithm .findAssignment (problem);
        displaySolution (problem, solution);
        //System .out .println (Arrays .toString (solution));
        //System .out .println (Arrays .toString (problem .firstColumnIndixes));
        //System .out .println (Arrays .toString (problem .columns));
        //System .out .println (Arrays .toString (problem .weights));
    }
    
    private static int [] [] makeRandomTest (int height, int width,
                                    int areaCount, int rndCount, int minCount, int maxValue) {
        int k, l, index;
        int [] countByColumn;
        int [] [] weights;
        
        weights = new int [height] [width];
        
        for (k = 0; height > k; ++k) {
            Arrays .fill (weights [k], Integer .MAX_VALUE);
        }
        
        countByColumn = new int [width];
        
        for (index = 0; areaCount > index; ++index) {
            k = rng .nextInt (height);
            l = rng .nextInt (width);
            weights [k] [l] = rng .nextInt (maxValue);
            ++countByColumn [l];
        }
        
        for (k = 0; height > k; ++k) {
            for (l = 0; rndCount > l; ) {
                index = rng .nextInt (width);
                if (Integer .MAX_VALUE != weights [k] [index]) {
                    continue;
                }
                weights [k] [index] = rng .nextInt (maxValue);
                ++countByColumn [index];
                ++l;
            }
            for (l = 0; minCount > l; ++l) {
                index = findMinCountIndex (countByColumn);
                weights [k] [index] = rng .nextInt (maxValue);
                ++countByColumn [index];
            }
        }
        
        return weights;
    }
    
    private static int findMinCountIndex (int [] countByColumn) {
        int k, count, bestCount, bestIndex;
        
        bestCount = Integer .MAX_VALUE;
        bestIndex = -1;
        
        for (k = 0; countByColumn .length > k; ++k) {
            count = countByColumn [k];
            if (bestCount > count) {
                bestCount = count;
                bestIndex = k;
            }
        }
        
        return bestIndex;
    }
    
    private static ForwardStarGraphClass convertToForwardStar (int [] [] weights) {
        int k, l, count;
        ForwardStarGraphClass result = new ForwardStarGraphClass ();
        
        result .height = weights .length;
        result .width = weights [0] .length;
        result .firstColumnIndixes = new int [result .height + 1];
        
        count = 0;
        for (k = 0; result .height > k; ++k) {
            for (l = 0; result .width > l; ++l) {
                if (Integer .MAX_VALUE != weights [k] [l]) {
                    ++count;
                }
            }
        }
        
        result .columns = new int [count];
        result .weights = new int [count];
        
        count = 0;
        for (k = 0; result .height > k; ++k) {
            result .firstColumnIndixes [k] = count;
            for (l = 0; result .width > l; ++l) {
                if (Integer .MAX_VALUE != weights [k] [l]) {
                    result .columns [count] = l;
                    result .weights [count] = weights [k] [l];
                    ++count;
                }
            }
        }
        result .firstColumnIndixes [result .height] = count;
        
        return result;
    }
    
    private static void displaySolution (ForwardStarGraphClass problem, int [] solution) {
        int count, row, column, value, sum, limit;
        boolean flag = null != solution;
        
        System .out .println ();
        count = 0;
        row = 0;
        column = 0;
        sum = 0;
        value = problem .weights [count];
        limit = problem .firstColumnIndixes [row + 1];
        while (true) {
            if (limit > count && column == problem .columns [count]) {
                if (flag && column == solution [row]) {
                    sum += value;
                    System .out .print (String .format ("%4s]", "[" + value));
                } else {
                    System .out .print (String .format ("%4d ", value));
                }
                ++count;
                if (problem .weights .length > count) {
                    value = problem .weights [count];
                }
            } else {
                if (flag && column == solution [row]) {
                    System .out .print (" ####");
                } else {
                    System .out .print ("   - ");
                }
            }
            ++column;
            if (problem .width <= column) {
                ++row;
                System .out .println ();
                if (problem .height <= row) {
                    break;
                }
                column = 0;
                limit = problem .firstColumnIndixes [row + 1];
            }
        }
        System .out .println ();
        
        if (flag) {
            System .out .println ("Sum = " + sum);
            System .out .println ();
        }
    }
}
 

Файл ForwardStarGraphClass.java:

Используется синтаксис Java

public class ForwardStarGraphClass {
    
    int height, width;
    int [] firstColumnIndixes;
    int [] columns, weights;
}
 

Файл HungarianAlgorithm.java:

Используется синтаксис Java

import java.util.*;

public class HungarianAlgorithm {
    
    public static int [] findAssignment (ForwardStarGraphClass problem) {
        int delta, value, addedRow, workRow, indexLimit, columnIndex, workColumn, nextColumn, usedRowsCount, rowIndex;
        int [] rowsPotentials, columnsPotentials;
        int [] assignment, matchings, wayBack, usedRowsList;
        boolean [] usedColumns;
        ArrayMinimumClass auxMinima;
        
        if (problem .height > problem .width) {
            throw new IllegalArgumentException ("\n\nData height must be less than or equal data width.\n");
        }
        
        usedRowsList      = new int     [problem .height];
        rowsPotentials    = new int     [problem .height];
        assignment        = new int     [problem .height];
        matchings         = new int     [problem .width];
        columnsPotentials = new int     [problem .width];
        wayBack           = new int     [problem .width];
        usedColumns       = new boolean [problem .width];
        Arrays .fill (matchings,  -1);
        auxMinima = new ArrayMinimumClass (problem .width);
        
        //      Adding rows one by one into partial solution
        
        for (addedRow = 0; problem .height > addedRow; ++addedRow) {
            
            //      Initialization of a new iteration
            
            Arrays .fill (usedColumns, false);
            auxMinima .init ();
            workRow = addedRow;
            usedRowsCount = 0;
            delta = 0;
            
            //      Looking for a shortest augmenting path starting with the row being added
            
            do {
                usedRowsList [usedRowsCount] = workRow;
                ++usedRowsCount;
                
                //      Updating list of lengths of searched paths, marking way back from column to row
                
                columnIndex = problem .firstColumnIndixes [workRow];
                indexLimit  = problem .firstColumnIndixes [workRow + 1];
                for (; indexLimit > columnIndex; ++columnIndex) {
                    workColumn = problem .columns [columnIndex];
                    if (usedColumns [workColumn]) {
                        continue;
                    }
                    value = problem .weights [columnIndex]
                          - rowsPotentials [workRow] - columnsPotentials [workColumn]
                          + delta;
                    if (auxMinima .update (workColumn, value)) {
                        wayBack [workColumn] = workRow;
                    }
                }
                
                //      Looking for the best unused column and associated path length
                
                if (auxMinima .isEmpty ()) {
                    return null;
                }
                
                nextColumn = auxMinima .getMinimumIndex ();
                delta      = auxMinima .getValue (nextColumn);
                auxMinima .remove ();
                
                usedColumns         [nextColumn] = true;
                workRow = matchings [nextColumn];
                
                //      If the best column is not free, then continue iterations
                
            } while (-1 != workRow);
            
            //      Recalculating potentials
            
            rowsPotentials [addedRow] += delta;
            columnsPotentials [nextColumn] -=
                    delta - auxMinima .getValue (nextColumn);
            
            for (rowIndex = 1; usedRowsCount > rowIndex; ++rowIndex) {
                workRow = usedRowsList [rowIndex];
                workColumn = assignment [workRow];
                value = delta - auxMinima .getValue (workColumn);
                rowsPotentials    [workRow]    += value;
                columnsPotentials [workColumn] -= value;
            }
            
            //      Restoring new partial assignment
            
            do {
                workRow = wayBack [nextColumn];
                matchings [nextColumn] = workRow;
                workColumn = assignment [workRow];
                assignment [workRow] = nextColumn;
                nextColumn = workColumn;
            } while (addedRow != workRow);
        }
        
        return assignment;
    }
}
 

Файл ArrayMinimumClass.java остался тем же, что и раньше.

Результаты работы:

Используется синтаксис Text

Seed 1610905845175

  47    -    -   23   52   89   53    -    -    -    -    -    -    -    -   62 
  40    -    -    -    -   74    -    -   73   80    -   75    -    -    -    - 
   -   32    -    -    -   21   25    -    -    -    -    -    -   40   83    - 
   -    -    5   54    5    -    -   38    -    -    -    -    -    -   78    - 
   -    -    -    -   77    -    -    -   34    -    -   60   72   42    -   86 
  48   25   17    -    -    -    -    -    -    -   29    -    -    -    -   27 
   -    -    -   90    -    -   25   83    -   79    -    -   84    -    -    - 
   9    -    -   49    -    -    -    -    2    -    -   41    -    -   10    - 
   -    8    -    -    -   77    -    -    -   97   47    -   58   66    -    - 
   -    -    6    -   92    -    -    -    6    -    -    -    -    9   52    - 
  17    -   71    -    8    -   80   63    -    -   36    7    -    -    -    - 
   -   59    -    -    -    -    -    8    -   36   78    -   16    -    -   38 
   -   10   88   85    -    -    -   13    -    -   66    -    -    -   52   85 
   -    -    -    -    -   38   61    -   85   89   88   45    -    -    -    - 


  47    -    -  [23]  52   89   53    -    -    -    -    -    -    -    -   62 
 [40]   -    -    -    -   74    -    -   73   80    -   75    -    -    -    - 
   -   32    -    -    -  [21]  25    -    -    -    -    -    -   40   83    - 
   -    -   [5]  54    5    -    -   38    -    -    -    -    -    -   78    - 
   -    -    -    -   77    -    -    -  [34]   -    -   60   72   42    -   86 
  48   25   17    -    -    -    -    -    -    -   29    -    -    -    -  [27]
   -    -    -   90    -    -  [25]  83    -   79    -    -   84    -    -    - 
   9    -    -   49    -    -    -    -    2    -    -   41    -    -  [10]   - 
   -   [8]   -    -    -   77    -    -    -   97   47    -   58   66    -    - 
   -    -    6    -   92    -    -    -    6    -    -    -    -   [9]  52    - 
  17    -   71    -   [8]   -   80   63    -    -   36    7    -    -    -    - 
   -   59    -    -    -    -    -    8    -   36   78    -  [16]   -    -   38 
   -   10   88   85    -    -    -  [13]   -    -   66    -    -    -   52   85 
   -    -    -    -    -   38   61    -   85   89   88  [45]   -    -    -    - 

Sum = 284
 

[B@R5uk]

В связи с решаемой в соседней теме задаче у меня возник вот такой вопрос.

Если цена назначения в задаче о назначениях является не просто числом, а композитной величиной из двух положительных целых чисел, которые складываются как обычно, а при сравнении сначала сравнивается первые величины пар, а затем (если первые равны) — вторые, то будет ли венгерка работать, если просто в лоб заменить арифметику и сравнения? Или же всё сломается, так как потенциалы должны удовлетворять определённым требованиям? И если сломается, то как действовать, чтобы всё-таки найти назначение с минимальной суммарной композитной величиной?

[zykov]

B@R5uk в сообщении #1539444 писал(а):

композитной величиной из двух положительных целых чисел

Возьмите большое число, которое точно больше всех вторых, умножте первое на это больше и прибавьте второе. Тогда цена будет "просто числом".

[B@R5uk]

zykov в сообщении #1539511 писал(а):

Возьмите большое число, которое точно больше всех вторых

Лучше взять в качестве множителя число, которое большее потенциально возможной суммы всех вторых чисел. Другими словами трактовать вторую компоненту композитной величины как младший разряд, неспособный к переполнению. Спасибо, это убедительное рассуждение. Как следствие, с венгеркой ничего дополнительного мутить не надо, достаточно лишь грамотно реализовать арифметику и сравнения этой композитной величины.

Численный эксперимент, вроде, не противоречит сказанному, хотя он, конечно, ещё не доказательство. Вообще, мне надо было с самого начала запилить брутфорсер, который в лоб за факториальное время находит оптимальное решение задачи о назначениях. Тогда бы по мере освоения венгерки у меня под рукой всегда бы было с чем сравнивать результаты, что очень полезно. Видимо, навскидку я тогда не сообразил как такой брутфорсер реализовать, а потом было не до него. Когда сейчас взялся за этот вопрос всерьёз, оказалось, что перебрать все возможные размещения из n по k — это разрешимая, но не совсем тривиальная задача.

Файл Study_Hungarian_Double.java

Используется синтаксис Java

import java.util.*;

public class Study_Hungarian_Double {
    
    //private static final long seed = 1637406442175L;
    private static final long seed = System .currentTimeMillis ();
    private static final Random rng = new Random (seed);

    private static final int width     = 7;
    private static final int height    = 5;
    private static final int maxValue1 = 5;
    private static final int maxValue2 = 30;
    
    private static int [] [] weights1, weights2;
    private static int [] assignment;

    public static void main (String [] args) {
        System .out .println ("Seed " + seed);
        weights1 = makeRandomTest (rng, width, height, maxValue1);
        weights2 = makeRandomTest (rng, width, height, maxValue2);
        
        assignment = Bruteforcer .getAssignment (weights1, weights2);
        diplay (weights1, weights2, assignment, "'");
        
        HungarianMethod .init (width, height);
        assignment = HungarianMethod .getAssignment (weights1, weights2);
        diplay (weights1, weights2, assignment, "'");
    }
    
    private static int [] [] makeRandomTest (Random rng, int width, int height, int maxValue) {
        int k, l;
        int [] [] result = new int [height] [width];
        for (k = 0; height > k; ++k) {
            for (l = 0; width > l; ++l) {
                result [k] [l] = rng .nextInt (maxValue);
            }
        }
        return result;
    }
    
    private static void diplay (int [] [] weights1, int [] [] weights2, int [] assignment, String separator) {
        int k, l, m, width, value1, value2, sum1 = 0, sum2 = 0;
        
        width  = weights1 [0] .length;
        System .out .println ();
        for (k = 0; weights1 .length > k; ++k) {
            m = assignment [k];
            for (l = 0; width > l; ++l) {
                value1 = weights1 [k] [l];
                value2 = weights2 [k] [l];
                if (Integer .MAX_VALUE == value1) {
                    if (m == l) {
                        System .out .print (" ######");
                    } else {
                        System .out .print ("     - ");
                    }
                } else {
                    if (m == l) {
                        sum1 += value1;
                        sum2 += value2;
                        System .out .print (String .format ("%6s]", "[" + value1 + separator + value2));
                    } else {
                        System .out .print (String .format ("%6s ", value1 + separator + value2));
                    }
                }
            }
            System .out .println ();
        }
        System .out .println ("\nSum: " + sum1 + separator + sum2 + "\n");
    }
}

Файл DoubleComp.java

Используется синтаксис Java

public class DoubleComp {
    public static boolean isGreater (int a1, int a2, int b1, int b2) {
        return a1 > b1 || a1 == b1 && a2 > b2; 
    }
}

Файл Bruteforcer.java

Используется синтаксис Java

import java.util.*;

public class Bruteforcer {
    
    public static final int INFINITY = Integer .MAX_VALUE;
    
    public static int [] getAssignment (int [] [] weights1, int [] [] weights2) {
        int k, width, height, value1, value2, sum1, sum2, bestSum1 = INFINITY, bestSum2 = INFINITY;
        int [] test, result = null;
        
        height = weights1     .length;
        width  = weights1 [0] .length;
        if (height > width) {
            throw new RuntimeException ("\n\nHeight must not exceed width.\n");
        }
        test = getFirstAllocation (height, width);
        
        outerLoop:
        do {
            sum1 = 0;
            sum2 = 0;
            for (k = 0; height > k; ++k) {
                value1 = weights1 [k] [test [k]];
                if (INFINITY == value1) {
                    continue outerLoop;
                }
                value2 = weights2 [k] [test [k]];
                sum1 += value1;
                sum2 += value2;
            }
            if (DoubleComp .isGreater (bestSum1, bestSum2, sum1, sum2)) {
                bestSum1 = sum1;
                bestSum2 = sum2;
                result = Arrays .copyOf (test, height);
            }
        } while (getNextAllocation (test, height));
        
        return result;
    }
    
    private static int [] getFirstAllocation (int size, int limit) {
        int k, l;
        int [] result = new int [limit];
        for (k = 0; size > k; ++k) {
            result [k] = k;
        }
        for (l = limit - 1; limit > k; ++k, --l) {
            result [k] = l;
        }
        return result;
    }
    
    private static boolean getNextAllocation (int [] result, int size) {
        int k = result .length - 1, l, temp;
        do {
            if (0 == k) {
                return false;
            }
            l = k;
            --k;
        } while (result [k] > result [l]);
        temp = result [k];
        l = result .length;
        do {
            --l;
        } while (temp > result [l]);
        result [k] = result [l];
        result [l] = temp;
        l = result .length;
        while (true) {
            ++k;
            --l;
            if (k >= l) {
                break;
            }
            temp = result [k];
            result [k] = result [l];
            result [l] = temp;
        }
        for (k = size, l = result .length - 1; k < l; ++k, --l) {
            temp = result [k];
            result [k] = result [l];
            result [l] = temp;
        }
        return true;
    }
}

Файл HungarianMethod.java

Используется синтаксис Java

import java.util.*;

public class HungarianMethod {
    
    public static final int INFINITY = Integer .MAX_VALUE;
    
    private static final int NO_MATCH = -1;
    
    private static int width, height;
    private static int [] rowPotentials1, colPotentials1, auxMinima1;
    private static int [] rowPotentials2, colPotentials2, auxMinima2;
    private static int [] matchings, wayBack, usedRowsList;
    private static boolean [] usedCols;
    
    public static void init (int argWidth, int argHeight) {
        if (height > width) {
            throw new RuntimeException ("\n\nHeight must not exceed width.\n");
        }
        width  = argWidth;
        height = argHeight;
        usedRowsList   = new int [height];
        rowPotentials1 = new int [height];
        rowPotentials2 = new int [height];
        colPotentials1 = new int [width];
        colPotentials2 = new int [width];
        auxMinima1     = new int [width];
        auxMinima2     = new int [width];
        matchings      = new int [width];
        wayBack        = new int [width];
        usedCols       = new boolean [width];
    }
    
    public static int [] getAssignment (int [] [] weights1, int [] [] weights2) {
        int addedRow, workRow, usedRowsCount, colIndex, nextColumn = 0, rowIndex, workCol;
        int delta1, delta2, value1, value2;
        int [] assignment = new int [height];
        
        Arrays .fill (rowPotentials1, 0);
        Arrays .fill (rowPotentials2, 0);
        Arrays .fill (colPotentials1, 0);
        Arrays .fill (colPotentials2, 0);
        Arrays .fill (matchings, NO_MATCH);
        
        //      Adding rows one by one into partial solution
        for (addedRow = 0; height > addedRow; ++addedRow) {
            //      Initializing new iteration
            Arrays .fill (auxMinima1, INFINITY);
            Arrays .fill (auxMinima2, INFINITY);
            Arrays .fill (usedCols, false);
            usedRowsCount = 0;
            delta1 = 0;
            delta2 = 0;
            //      Looking for a shortest augmenting path starting with the row being added
            workRow = addedRow;
            do {
                usedRowsList [usedRowsCount] = workRow;
                ++usedRowsCount;
                //      Calculating and updating list of lengths of searched paths, marking way back
                for (colIndex = 0; width > colIndex; ++colIndex) {
                    if (usedCols [colIndex]) {
                        continue;
                    }
                    value1 = weights1 [workRow] [colIndex];
                    if (INFINITY == value1) {
                        continue;
                    }
                    value2 = weights2 [workRow] [colIndex];
                    value1 += delta1;
                    value2 += delta2;
                    value1 -= rowPotentials1 [workRow] + colPotentials1 [colIndex];
                    value2 -= rowPotentials2 [workRow] + colPotentials2 [colIndex];
                    if (DoubleComp .isGreater (auxMinima1 [colIndex], auxMinima2 [colIndex], value1, value2)) {
                        auxMinima1 [colIndex] = value1;
                        auxMinima2 [colIndex] = value2;
                        wayBack    [colIndex] = workRow;
                    }
                }
                //      Searching for minimum value column
                delta1 = INFINITY;
                delta2 = INFINITY;
                for (colIndex = 0; width > colIndex; ++colIndex) {
                    if (usedCols [colIndex]) {
                        continue;
                    }
                    value1 = auxMinima1 [colIndex];
                    value2 = auxMinima2 [colIndex];
                    if (DoubleComp .isGreater (delta1, delta2, value1, value2)) {
                        delta1 = value1;
                        delta2 = value2;
                        nextColumn = colIndex;
                    }
                }
                //      Checking if assignment is possible at all
                if (INFINITY == delta1) {
                    return null;
                }
                usedCols [nextColumn] = true;
                workRow = matchings [nextColumn];
                //      Continue to search augmenting path until the minimum value column is free 
            } while (NO_MATCH != workRow);
            
            //      Recalculating potentials
            rowPotentials1 [addedRow]   += delta1;
            rowPotentials2 [addedRow]   += delta2;
            colPotentials1 [nextColumn] -= delta1 - auxMinima1 [nextColumn];
            colPotentials2 [nextColumn] -= delta2 - auxMinima2 [nextColumn];
            for (rowIndex = 1; usedRowsCount > rowIndex; ++rowIndex) {
                workRow = usedRowsList [rowIndex];
                workCol = assignment [workRow];
                value1 = delta1 - auxMinima1 [workCol];
                value2 = delta2 - auxMinima2 [workCol];
                rowPotentials1 [workRow] += value1;
                rowPotentials2 [workRow] += value2;
                colPotentials1 [workCol] -= value1;
                colPotentials2 [workCol] -= value2;
            }
            //      Tracing back new partial assignment
            do {
                workRow = wayBack [nextColumn];
                matchings [nextColumn] = workRow;
                workCol = assignment [workRow];
                assignment [workRow] = nextColumn;
                nextColumn = workCol;
            } while (addedRow != workRow);
        }
        
        return assignment;
    }
}