SamJ's blog

作业：最小生成树和多机调度

algorithm
Word count: 1.7kReading time: 8 min
2019/09/20 Share

最小生成树和作业调度

最小生成树：对于一个连通图（图中任意两点相通）G = (V, E)，且E中的每条边上有权值。如果G的一个子图G‘ 是一棵包含G的所有顶点的树，称G’为G的生成树。在G的所有生成树中，各边的权值之和最小的生成树称为G的最小生成树。

应用举例 ：设计一片区域的通信网络时，节点表示城市，边上的权值表示在两个城市之间建立通信线路需要的费用，则最小生成树就是在该区域建立通信网络的最经济方案。

Kruscal算法

  • 设一个集合A是某棵最小生成树的子集，在Kruscal算法中，A集合是一个森林，即把每个节点都当作可能的最小生成树的子集。
  • 找到一条边，该边的权值最小且该边所连接的两个节点不在同一棵树中，将这条边所连接的两棵树合并，直到A集合中只剩下一颗树。

简单地说，就是在所有剩余的边中找到权值最小的边，若把它加入不会构成环就将其加入，如果构成环就舍弃，直到找完所有的边。

例子：

origin kruscal1 kruscal2

时间复杂度O(ElogE)， 主要花费在对边按权值大小进行排序上 。

Prim算法

  • Prim算法中的A总是构成一棵树。
  • 该算法每次在连接集合A和A之外的节点的边中选取权值最小的边加入到A集合，直到A集合包含了所有的节点。
prim1 prim2

时间复杂度取决于寻找下一个待插入节点的方式，若使用最小堆实现的优先级队列则其时间复杂度可以是O(ElogV)。

代码实现：

graph.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED
#include <vector>
#include <list>

class Edge{
public:
    Edge(int idFrom, int idTo, int weight)
    : _idFrom(idFrom)
    , _idTo(idTo)
    , _weight(weight)
    {}
    void printEdge();
    bool operator<(const Edge & );
    int getIdFrom() const { return _idFrom; }
    int getIdTo() const { return _idTo; }
    int getWeight() const { return _weight; }
private:
    int _idFrom;
    int _idTo;
    int _weight;
};

class Graph{
public:
    Graph();
    void printGraph();
    void mstKruscal();
    void mstPrim();
    void printKruscal();
    void printPrim();
    friend void findCanReach(int*, int*, int, std::vector<Edge>&, Graph *);
    ~Graph();
private:
    std::vector<int> _nodes;    //存放所有节点
    std::vector<Edge> _edges;   //存放所有边
    std::vector<Edge> _kruscalEdges;    //kruscal算法的结果
    std::list<Edge> _primEdges;       //prim算法的结果
};


#endif // GRAPH_H_INCLUDED

graph.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include "graph.h"
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

void Edge::printEdge()
{
    cout << _idFrom << "---" << _idTo << " " << _weight << endl;
}

bool Edge::operator<(const Edge & rhs)
{
    return this->_weight < rhs.getWeight();
}

Graph::Graph()
{
    cout << "please input nodes' id:" << endl;
    int id, idFrom, idTo, weight;
    while(cin >> id, id != 0)
    {
        _nodes.push_back(id);
    }
    cout << "please input edges:" << endl;
    while(cin >> idFrom, idFrom != 0)
    {
        cin >> idTo >> weight;
        _edges.push_back(Edge(idFrom, idTo, weight));
    }
}

void Graph::printGraph()
{
    for(auto e : _edges)
    {
        e.printEdge();
    }
}

void Graph::printKruscal()
{
    for(auto e : _kruscalEdges)
    {
        e.printEdge();
    }
}

void Graph::printPrim()
{
    for(auto e : _primEdges)
    {
        e.printEdge();
    }
}

bool isNotInOneTree(int id1, int id2, vector<vector<int>> & forest)
{
    int i1 = 0, i2 = 0;
    for(unsigned int i = 0; i < forest.size(); ++i)
    {
        if(find(forest[i].begin(), forest[i].end(), id1) != forest[i].end())
            i1 = i;
        if(find(forest[i].begin(), forest[i].end(), id2) != forest[i].end())
            i2 = i;
    }
    if(i1 != i2)                        
    {
        for(unsigned int i = 0; i < forest[i2].size(); ++i)
        {
            forest[i1].push_back(forest[i2][i]);
        }
        forest[i2].clear();
        return true;
    }
    return false;
}

void Graph::mstKruscal()
{
    sort(_edges.begin(), _edges.end());
    auto it = _edges.begin();
    vector<vector<int>> forest(_nodes.size());
    for(unsigned int i = 0; i < _nodes.size(); ++i)
    {
        forest[i].push_back(_nodes[i]);
    }                                                      
    while(it != _edges.end())
    {
        if(isNotInOneTree(it->getIdFrom(), it->getIdTo(), forest))
            _kruscalEdges.push_back(*it);
        ++it;
    }
}

bool isInSet(int id, vector<int> sets)
{
    if(find(sets.begin(), sets.end(), id) != sets.end())
        return true;
    else
        return false;
}

typedef struct Handle
{
    Handle(int id)
    :_id(id)
    {}

    bool operator()(Edge e)
    {
        return e.getIdFrom() == _id;
    }
    int _id;
}Handle_t;

void findCanReach(int *prim, int *notInPrim, int primCnt, vector<Edge>& canReach, Graph *G)
{
    int i, j = 0;
    while(j < primCnt)
    {
        auto it = G->_edges.begin();
        while(it != G->_edges.end())
        {
            it = find_if(it, G->_edges.end(), Handle_t(prim[j]));
            if(it == G->_edges.end())
                break;
            int exCnt = 0;
            for(i = 0; i < G->_nodes.size(); ++i)
            {
                if(it->getIdTo() == prim[i] || it->getIdFrom() == prim[i])
                {
                    ++exCnt;
                }
            }
            if(exCnt <= 1)
            {
                canReach.push_back(*it);
            }
            ++it;
        }
        ++j;
    }
}

void Graph::mstPrim()
{
    unsigned int i;
    int primCnt = 1;
    vector<Edge>::iterator it;
    int *prim = (int *)calloc(_nodes.size(), sizeof(int));                      //已经加入到prim的节点
    int *notInPrim = (int *)calloc(_nodes.size(), sizeof(int));;                 //没在prim中的节点
    vector<Edge> canReach;              //可以到达的节点经过的边的结合
    prim[0] = _nodes[0];
    for(i = 1; i < _nodes.size(); ++i)
    {
        notInPrim[i] = _nodes[i];
    }                                   //初始化两个集合
    while(primCnt < _nodes.size())
    {
        findCanReach(prim, notInPrim, primCnt, canReach, this);      //获取当前可到达节点
        sort(canReach.begin(), canReach.end());
        _primEdges.push_back(canReach.front());
        prim[primCnt] = canReach.front().getIdTo();
        ++primCnt;
        canReach.clear();
    }
    free(prim);
    free(notInPrim);
}

Graph::~Graph()
{
    cout << "program done" << endl;
}

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "graph.h"
#include <iostream>

using namespace std;

int main()
{
    Graph g;
    //g.printGraph();
    cout << "kruscal------------" << endl;
    g.mstKruscal();
    g.printKruscal();
    cout << "prim---------------" << endl;
    g.mstPrim();
    g.printPrim();
    return 0;
}
mstresult

多机调度

多机调度问题要求给出一种方案，使所给的n个作业在尽可能短的时间内由m台机器处理完成。

该问题是一个NP完全问题，但使用贪心的策略可以得到性能较好的算法。

  • 当n<= m 时，将机器i的[0, ti]分配给作业i即可。
  • 当n>m时，先将n个作业所需要的处理时间从大到小排序， 然后按此顺序将作业分配给空闲的处理机（总工作时间最短的）。

例子： 书上的例子，有7个任务，编号从1到7，处理时间为{2, 14, 4, 16, 6, 5, 3}。

分配情况可以是下图：

taskDistribut

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MACHINENUM 3
#define TASKNUM 7

typedef struct Task
{
    int taskId;
    int taskTime;
}Task_t;

typedef struct Machine
{
    int machineId;
    int totalTime;
}Machine_t;

int compare(const void *p1, const void *p2)
{
    Task_t *t1 = (Task_t*)p1;
    Task_t *t2 = (Task_t*)p2;
    return t2->taskTime - t1->taskTime;
}

void swap(Machine_t *m1, Machine_t *m2)
{
    Machine_t temp;
    memcpy(&temp, m1, sizeof(Machine_t));
    memcpy(m1, m2, sizeof(Machine_t));
    memcpy(m2, &temp, sizeof(Machine_t));
}

void greedy(Task_t *tasks)
{
    Machine_t machines[MACHINENUM];
    int i, usedTime = 0;
    for(i = 0; i < MACHINENUM; ++i)
    {
        machines[i].machineId = i +1;
        machines[i].totalTime = 0;
    }
    for(i = 0; i < TASKNUM; ++i)
    {
        printf("task %d is distributed to machine %d\n", tasks[i].taskId, machines[0].machineId);
        machines[0].totalTime += tasks[i].taskTime;
        minHeap(machines, 0);
    }
    for(i = 0; i < MACHINENUM; ++i)
    {
        if(machines[i].totalTime > usedTime)
            usedTime = machines[i].totalTime;
    }
    printf("total used time : %d\n", usedTime);
}

int main()
{
    Task_t tasks[TASKNUM];
    int i;
    int time;
    for(i = 0; i < TASKNUM; ++i)
    {
        tasks[i].taskId = i + 1;
        scanf("%d", &time);
        tasks[i].taskTime = time;
    }
    qsort(tasks, TASKNUM, sizeof(Task_t), compare);
    greedy(tasks);
    return 0;
}

运行结果：

taskResult

blog：https://samjjjj.github.io/

CATALOG
  1. 1. 最小生成树和作业调度
    1. 1.1. Kruscal算法
    2. 1.2. Prim算法
    3. 1.3. 多机调度
Total : 27
2021
2019
C++ paper hexo algorithm algorithm,c++ linux, C japanese,anime