MMM全链接聚类算法实现

使用时，仅需修改TODO下描述的字段即可，其他无需改动。

#include <bits/stdc++.h>
// TODO: 根据需求分别修改任务数、每个模块内最大任务数、模块数、步进长度
#define TASK_NUM        (8)
#define MAX_TASK_NUM    (4)
#define MODULE_NUM      (2)
#define GRANULARITY     (0.5)

using namespace std;

void MMMSAA();
void MMMCAA();
void MMMAAA();
void MMMSAArepeat();
void MMMCAArepeat();
void MMMAAArepeat();
void MMMinit();
void printDE();
void getFinalCost();

struct DEitem
{
    double c;
    int k;
    vector<set<int>> Kc;
};

double g_costThres = 0.0;
double g_costThresDefault = 0.0;
int g_k = 0;
vector<set<int>> g_Kc;
vector<DEitem> DE;

// TODO: 根据需求修改通讯代价矩阵
double g_commMatrix[TASK_NUM][TASK_NUM] =
{
    {0, 0, 0.5, 0, 0.5, 0, 0, 0,},
    {0, 0, 0.5, 0.5, 0, 0, 0, 0,},
    {0.5, 0.5, 0, 0.5, 1, 0.5, 0, 0,},
    {0, 0.5, 0.5, 0, 0, 1, 0, 0,},
    {0.5, 0, 1, 0, 0, 0.5, 1, 0,},
    {0, 0, 0.5, 1, 0.5, 0, 0.5, 0.5,},
    {0, 0, 0, 0, 1, 0.5, 0, 0.5,},
    {0, 0, 0, 0, 0, 0.5, 0.5, 0,},
};

void MMMinit()
{
    double maxElement = -1;
    for (int i = 0; i < TASK_NUM; ++i)
    {
        for (int j = 0; j < TASK_NUM; ++j)
        {
            if (g_commMatrix[i][j] > maxElement)
            {
                maxElement = g_commMatrix[i][j];
            }
        }
    }
    g_costThres = maxElement + 1;
    g_costThresDefault = g_costThres;
    g_k = TASK_NUM;
    g_Kc.clear();
    g_Kc.resize(TASK_NUM);
    for (int i = 0; i < TASK_NUM; ++i)
    {
        g_Kc[i].insert(i);
    }
}

void getFinalCost()
{
    vector<set<int>> K1 = DE[DE.size() - 1].Kc;
    double finalCost = 0;
    for (int i = 0; i < K1.size(); i++) // ki
    {
        for (int j = i + 1; j < K1.size(); j++) // kj
        {
            for (int ti : g_Kc[i]) // ti
            {
                for (int tj : g_Kc[j]) // tj
                {
                    finalCost += g_commMatrix[ti][tj];
                }
            }
        }
    }
    cout << "finalCost:" << finalCost << endl;
    cout << "--------------" << endl;
}

void MMMSAArepeat()
{
    do
    {
        for (int i = 0; i < g_Kc.size(); i++) // ki
        {
            for (int j = i + 1; j < g_Kc.size(); j++) // kj
            {
                double larc = -1;
                for (int ti : g_Kc[i]) // ti
                {
                    for (int tj : g_Kc[j]) // tj
                    {
                        if (g_commMatrix[ti][tj] >= larc)
                        {
                            larc = g_commMatrix[ti][tj];
                        }
                    }
                }
                if (larc >= g_costThres)
                {
                    set<int> mergedSet;
                    mergedSet.insert(g_Kc[i].begin(), g_Kc[i].end());
                    mergedSet.insert(g_Kc[j].begin(), g_Kc[j].end());
                    if (mergedSet.size() <= MAX_TASK_NUM)
                    {
                        g_Kc.push_back(mergedSet);
                        g_Kc.erase(g_Kc.begin() + i);
                        g_Kc.erase(g_Kc.begin() + j - 1);
                    }
                }
            }
        }
        g_k = g_Kc.size();
        DE.push_back({g_costThres, g_k, g_Kc});
        g_costThres = g_costThres - GRANULARITY;
    } while (g_costThres != 0 && g_k != MODULE_NUM);
    if (g_costThres == 0 && g_k > MODULE_NUM)
    {
        cout << "Need MMMSAA for K1" << endl;
        g_costThres = g_costThresDefault;
        g_k = DE[DE.size() - 1].k;
        MMMSAArepeat();
    }
}

void MMMCAArepeat()
{
    do
    {
        for (int i = 0; i < g_Kc.size(); i++) // ki
        {
            for (int j = i + 1; j < g_Kc.size(); j++) // kj
            {
                double smac = 9999;
                for (int ti : g_Kc[i]) // ti
                {
                    for (int tj : g_Kc[j]) // tj
                    {
                        if (g_commMatrix[ti][tj] <= smac)
                        {
                            smac = g_commMatrix[ti][tj];
                        }
                    }
                }
                if (smac >= g_costThres)
                {
                    set<int> mergedSet;
                    mergedSet.insert(g_Kc[i].begin(), g_Kc[i].end());
                    mergedSet.insert(g_Kc[j].begin(), g_Kc[j].end());
                    if (mergedSet.size() <= MAX_TASK_NUM)
                    {
                        g_Kc.push_back(mergedSet);
                        g_Kc.erase(g_Kc.begin() + i);
                        g_Kc.erase(g_Kc.begin() + j - 1);
                    }
                }
            }
        }
        g_k = g_Kc.size();
        DE.push_back({g_costThres, g_k, g_Kc});
        g_costThres = g_costThres - GRANULARITY;
    } while (g_costThres != 0 && g_k != MODULE_NUM);
    if (g_costThres == 0 && g_k > MODULE_NUM)
    {
        cout << "Need MMMSAA for K1" << endl;
        g_costThres = g_costThresDefault;
        g_k = DE[DE.size()-1].k;
        MMMSAArepeat();
    }
}

void MMMAAArepeat()
{
    do
    {
        for (int i = 0; i < g_Kc.size(); i++) // ki
        {
            for (int j = i + 1; j < g_Kc.size(); j++) // kj
            {
                double sumc = 0.0;
                int num = 0;
                for (int ti : g_Kc[i]) // ti
                {
                    for (int tj : g_Kc[j]) // tj
                    {
                        sumc += g_commMatrix[ti][tj];
                        num++;
                    }
                }
                double avgc = sumc / num;
                if (avgc >= g_costThres)
                {
                    set<int> mergedSet;
                    mergedSet.insert(g_Kc[i].begin(), g_Kc[i].end());
                    mergedSet.insert(g_Kc[j].begin(), g_Kc[j].end());
                    if (mergedSet.size() <= MAX_TASK_NUM)
                    {
                        g_Kc.push_back(mergedSet);
                        g_Kc.erase(g_Kc.begin() + i);
                        g_Kc.erase(g_Kc.begin() + j - 1);
                    }
                }
            }
        }
        g_k = g_Kc.size();
        DE.push_back({g_costThres, g_k, g_Kc});
        g_costThres = g_costThres - GRANULARITY;
    } while (g_costThres != 0 && g_k != MODULE_NUM);
    if (g_costThres == 0 && g_k > MODULE_NUM)
    {
        cout << "Need MMMSAA for K1" << endl;
        g_costThres = g_costThresDefault;
        g_k = DE[DE.size() - 1].k;
        MMMSAArepeat();
    }
}

void printDE()
{
    for (const auto &item : DE)
    {
        cout << "c: " << item.c << ", k: " << item.k << "  Kc: ";
        for (const auto &set : item.Kc)
        {
            cout << "{";
            for (int elem : set)
            {
                std::cout << elem + 1 << ",";
            }
            cout << "}, ";
        }
        cout << endl;
        cout << "--------------" << endl;
    }
}
void MMMSAA()
{
    cout << "MMMSAA Start!" << endl;
    MMMinit();
    MMMSAArepeat();
    printDE();
    getFinalCost();
    cout << "MMMSAA End!" << endl;
}

void MMMCAA()
{
    cout << "MMMCAA Start!" << endl;
    MMMinit();
    MMMCAArepeat();
    printDE();
    getFinalCost();
    cout << "MMMCAA End!" << endl;
}

void MMMAAA()
{
    cout << "MMMAAA Start!" << endl;
    MMMinit();
    MMMAAArepeat();
    printDE();
    getFinalCost();
    cout << "MMMAAA End!" << endl;
}

int main()
{
    MMMSAA();
    MMMCAA();
    MMMAAA();
    return 0;
}