精华内容
下载资源
问答
  • 任务分配问题

    2018-09-09 15:14:04
    任务分配问题(组合问题中的分支限界法)
  • 任务分配问题算法

    千次阅读 2020-04-15 15:28:47
    任务分配问题算法代码简化至34行 问题:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。 源代码: import ...

    任务分配问题算法代码简化至34行
    问题:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。

    源代码:

    import java.util.Arrays;
    public class Assignment {
    	static int arr[][]= {{9,2,7,8},{6,4,3,7},{5,8,1,8},{7,6,9,4}};
    	static int min=arr[0][0]+arr[1][0]+arr[2][0]+arr[3][0];
    	public static void main(String args[]) {
    		int solve[]= {0,1,2,3};
    		assignment(solve,0);		
    	}
    	static void assignment(int solve[],int i) {
    		if(i==arr.length) {
    			int temp=check(solve);
    			if(temp<min) {
    				min=temp;
    				System.out.println("Min: "+min+"  Solve: "+Arrays.toString(solve));
    			}			
    		}							
    		for(int j=i;j<arr.length;j++) {
    			swap(solve,i,j);
    			assignment(solve,i+1);
    			swap(solve,i,j);
    		}	
    	}
    	static int check(int solve[]) {
    		int sum=0;
    		for(int i=0;i<solve.length;i++)
    			sum+=arr[i][solve[i]];
    		return sum;
    	}
    	static void swap(int solve[],int i,int j) {
    		int t=solve[i];
    		solve[i]=solve[j];
    		solve[j]=t;
    	}
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • ACM 任务分配问题

    千次阅读 2018-07-19 08:52:50
    任务分配问题 Problem Description 现有 n 件任务和无限多台的机器,任务可以在机器上得到处理。每件任务的开始时间为 si,完成时间为 ei,[si, ei]为处理任务的时间范围。2 个任务重叠是指 2 个任务的时间范围有...

    任务分配问题

    Problem Description

    现有 n 件任务和无限多台的机器,任务可以在机器上得到处理。每件任务的开始时间为 si,完成时间为 ei,[si, ei]为处理任务的时间范围。2 个任务重叠是指 2 个任务的时间范围有重叠。例如,[1, 4]与[2, 4]重叠,[1, 4]与[4, 7]重叠。一个可行的任务分配是指在分配中没有 2 件重叠的任务分配给同一台机器。
    对于给定的 n 件任务,编程计算使用机器数最少的可行分配方案。

    Input

    第1行只有一个整数n(n<=1000,表示任务的总数。接下来有n行,每行2个整数si,ei分别表示任务的开始时间和完成时间,其中0<=si<=ei<10000.

    Output

    计算出的最少使用的机器数。

    Sample Input

    3
    1 4 
    2 5
    5 7
    

    Sample Output

    2

    Author

    tianzuwei

    思考:用N个任务,很多的机器,每一个任务有一个开始和结束的时间[si, ei],任务的完成时间是固定的,也是会有重叠的部分,也就是在3点的时候,可能有[1,4],[2,4]两个任务需要同时完成,现在问完成这么多的任务最少需要多少的机器。假如给每一个任务都分配一个机器的话,那么至多也就是需要N个机器,但是很明显的地方在于一台机器可以完成[1,3], [4,6] 等多个不重叠的任务,所以完成N个任务的最少机器,就是在某一个时间点上面任务重叠最多的所需要的机器。

    程序大致解析: 以数组下标作为时间点,数组具体值作为重叠任务数,初始值为0,每输入一个任务,就在该任务完成的时间上面所有的时间节点+1,最后遍历所得的数组,找出最大的元素即所求。具体见下:

    ​
    #include<bits/stdc++.h>
    #define maxx 10001
    using namespace std;
    int num[maxx];
    int main()
    {
        //freopen("in.txt","r",stdin);
        int n, i, mx, x, y, t;
        while(cin >> n)
        {
            t = 0;
            memset(num, 0 ,sizeof(num));
            for(i = 0; i < n; i++)
            {
                cin >> x >> y;
                for(x; x <= y; x++)
                num[x]++;
                if(t <= y) t = y;
            }
            mx = 0;
            for(i = 0; i <= t; i++)
            if(mx < num[i]) mx = num[i];
            cout << mx << endl;
        }
        fclose(stdin);
        
        return 0;
    }
    
    ​

    补充:后面学习当中,发现更加好的算法,上面的算法时间复杂度为O(n^2),可以用差分数组的思想,优化到O(n)的时间复杂度。见下面代码:

    #include<bits/stdc++.h>
    using namespace std;
    #define INF 0x3f3f3f3f
    const int N = 100000 + 10;
    int m, q;
    int a[N], d[N], sum[N];
    int main() 
    {
    	//freopen("in.txt", "r", stdin);
        int n;
        while (scanf("%d", &n) != EOF) 
    	{
            memset(a, 0, sizeof(a));//初始化都为0
            int l, r;
            memset(d, 0, sizeof(d));
            d[1] = a[1];//特殊处理第一个数
            for (int i = 0; i < n; i++) 
    		{
                scanf("%d%d", &l, &r);
                d[l] += 1;
                d[r+1] -= 1;
            }
            memset(sum, 0, sizeof(sum));
            for (int i = 1; i <= n; ++i) 
    		{
                sum[i] = sum[i-1] + d[i]; //求d[i]前缀和, 也就是修改后的a[i]
            }
            int maxn = 0;
            for (int i = 1; i <= n; ++i)
    		{
              if(maxn < sum[i]) maxn = sum[i];
            }
            cout << maxn << endl;
        }
    fclose(stdin);
        return 0;
    }

     

    展开全文
  • 用于解决任务分配问题 蚁群.zip
  • 实验四:矩阵算法一、实验目的问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。假设N=5,每个人...

    实验四:矩阵算法

    一、实验目的

    问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。假设N=5,每个人工作和报酬之间的关系如下表所示,求解该问题的最优解

    表1.1 任务分配

    work1work2work3work4work5

    person19075 75 80 60

    person23585 556548

    person31259590105100

    person4451109510598

    person57664578890

    二、实验要求

    (1)做好实验预习

    (2)独立完成实验

    (3)撰写实验报告

    三、实验题目

    本实验由于要求较少,只是寻求最优解,因此采用简单的方法。

    四、实验环境

    本文的编程环境为Ubantu16.04。

    本文的编程语言为Python3.7。

    五、实验分析与设计思路

    本实验采用的是矩阵的方式进行计算,但是其中包含了列表的计算方法,矩阵的相乘。

    主要采用的程序:

    np.array([])生成一个想要的数组 包括列向量,和行向量。

    b=numpy.array([b]).T 行向量转成列向量。

    a.dot(b) 向量的乘法。

    a*b只是对应相乘不是矩阵的乘法。

    a[[1,2],:]=a[[2,1],:] 矩阵的一二两行对调。

    左乘单位行向量再乘以已知矩阵再乘以变换矩阵再乘以单位列向量。

    六,程序源码

    #本实验要求计算利润的最小值杠杠简单

    #本次实验打算采用矩阵的方式,不懂勿扰

    #np.array([])生成一个想要的数组 包括列向量,和行向量

    #b=numpy.array([b]).T 行向量转成列向量

    #a.dot(b) 向量的乘法

    #a*b只是对应相乘不是矩阵的乘法

    #a[[1,2],:]=a[[2,1],:] 矩阵的一二两行对调

    #左乘单位行向量再乘以已知矩阵再乘以变换矩阵再乘以单位列向量

    #========================================================================

    #智能优化算法---计算工作分配方案(原创)

    #作者:Vince

    #版本号:1.0

    #创作日期:2018.10.31

    #如需转载,请电联.

    #耗时:4h

    #=========================================================================

    import random

    import math

    import numpy as np

    import copy

    import numpy as np

    import matplotlib.pyplot as plt

    class Min(object):

    def __init__(self,newList = [],n=5):

    self.newList = newList #初始列表工作的选择

    self.diag = np.identity(5) #生成一个五维单位矩阵

    self.dhxl = np.array([1,1,1,1,1]) #单位行向量

    self.dlxl = np.array([[1],[1],[1],[1],[1]])#单位列向量

    self.value = 0#每一次的报酬

    self.bestvalue = 100000 #每一次初始种群的最佳报酬

    self.bestchoice = np.identity(5) #每一次的初始种群的最佳方案

    self.empty = [[-1,-1]] #禁忌表

    self.n=n #人数或工作的量

    self.num = (((self.n-1)+1)*4/2) #计算循环次数

    self.bestdiag=np.identity(5)

    def Pso(self):

    self.empty = [[-1,-1]]

    self.diag = self.bestdiag

    self.value = self.bestvalue

    i = 0

    while i < 10:

    index1 = random.randint(0,4) #生成初始种群需要互换的两行

    index2 = random.randint(0,4)

    if (index1,index2)!=self.empty[-1] and (index2,index1)!=self.empty[-1] and index1!=index2:#比对禁忌表中是否存在

    self.empty.append((index1,index2))#将互换两行的行号放入禁忌表

    self.diag[[index1,index2],:] = self.diag[[index2,index1],:]#将两行互换

    self.value = self.Cul(self.diag)#计算报酬

    if self.value < self.bestvalue:#

    self.bestvalue = self.value

    self.bestdiag = self.diag

    self.bestchoice = self.newList*self.bestdiag

    i += 1

    # print(self.empty)

    def Cul(self,diag):

    diag = self.newList*diag

    diag = self.dhxl.dot(diag)

    value = diag.dot(self.dlxl)

    return value

    def getValue(self):#返回局部最佳值

    return self.bestvalue

    def getchoice(self):#返回局部最佳方案

    return self.bestchoice

    def main(turn):

    newList = np.array([[90,75,75,80,60],[35,85,55,65,48],[125,95,90,105,100],[45,110,95,105,98],[76,64,57,88,90]])

    num = 5

    tbv = []

    tbc = []

    i=0

    min = Min(newList,num)

    while i

    min.Pso()

    value = min.getValue()

    tbv.append(value)

    choice = min.getchoice()

    tbc.append(choice)

    print('这是第%d次选择'%(i+1))

    print('报酬的最小值:%d'%value)

    print('最佳选择为:')

    print(str(choice))

    i += 1

    # print('\n')

    nb=copy.deepcopy(tbv)

    nb.sort() #将所有的局部最佳值进行排序

    i = 0

    while i

    if tbv[i][0] == nb[0][0]:

    break

    i += 1

    print('全局报酬最优解:%d'%tbv[i])

    print('最佳选择为:')

    print(str(tbc[i]))

    return tbv[i][0]

    # main(10)

    def psoPlot():

    x = []

    y = []

    i=1

    while i< 50:

    tc = main(i)

    #x轴 y轴

    x.append(i)

    y.append(tc)

    print(i)

    i += 1

    #创建绘图对象,figsize参数可以指定绘图对象的宽度和高度,单位为英寸,一英寸=80px

    plt.figure(figsize=(8,8))

    #在当前绘图对象进行绘图(两个参数是x,y轴的数据)

    plt.plot(x, y, linewidth = '1', label = "test",color='#054E9F', linestyle=':', marker='|')

    plt.xlabel("time(s)") #X轴标签

    plt.ylabel("value(m)") #Y轴标签

    plt.title("A simple plot") #标题

    #保存图象

    # plt.savefig("easyplot.png")

    plt.legend()

    plt.show()

    psoPlot()

    七,运行结果

    25ade66fa071f73a40fbe58d234ffd2f.png

    八,程序原图

    a5b8a3741c795d79e45178c4ebf73fcf.png

    展开全文
  • C++编写的任务分配问题,运用分支界限法,C++实现匈牙利算法,包含程序解决问题及源代码,可以运行。
  • 针对目前产品开发任务分配问题研究存在的不足, 给出了任务分配问题的数学描述和约束条件, 提出了任 务分配模型中的相关矩阵, 并采用权重因子和极差变换法建立了多目标优化的目标函数. 针对任务分配过程的动态 ...
  • 多因素任务分配问题的实质是如何进行节点—目标分配,使系统达到最大综合任务效能,可将该问题转化为指派问题进行求解。通过应用实验实现和验证了多因素任务分配模型,实验结果表明该模型适合于小规模的多因素任务...
  • 自适应遗传算法在多无人机任务分配问题中的应用
  • 任务分配问题·dfs

    2021-04-06 16:57:36
    任务分配问题题目信息输入输出测试用例解答方法一·dfs方法二·匈牙利算法 题目信息 只有一组测试用例。 输入 第一行是操作员的人数n(4=<n<=13),接下来的n行里每行有n个数,分别表示第i名操作员完成第i项任务...

    题目信息

    只有一组测试用例。

    输入

    第一行是操作员的人数n(4=<n<=13),接下来的n行里每行有n个数,分别表示第i名操作员完成第i项任务的时间。

    输出

    完成所有任务的最短时间。

    测试用例

    4
    3 8 4 12
    9 12 13 5
    8 7 9 3
    12 7 6 8
    
    21
    

    解答

    方法一·dfs

    #include<iostream>
    #include<algorithm>
    
    #define MAXN 15
    #define MAXINT 0x7fffffff
    
    using namespace std;
    
    int N;
    int workers[MAXN][MAXN];
    bool flag[MAXN];//任务标记
    int ans = MAXINT;
    int MIN[MAXN];//每列用时最小
    
    void dfs(int k, int time)
    {//k代表到第几个员工,time是当前总用时
        if (k >= N + 1)
        {//到达搜索终点,更新得到答案
            ans = min(ans, time);
            return;
        }
        if (time > ans)
        {//剪枝1,如果当前所用时间已经大于了之前计算的最小值
            return;
        }
    
        for (int i = 1; i <= N; i++)//枚举任务
        {
            if (!flag[i])
            {
                //剪枝2,若没选中的任务列最小值之和比mins大,那就直接剪掉了
                int minsum = time + workers[k][i];
                for (int j = 1; j <= N; j++)
                {
                    if (!flag[j] && j != i)
                    {
                        minsum += MIN[j];
                    }
                }
                if (minsum < ans)
                {
                    flag[i] = true;//表示这个任务做过了
                    dfs(k + 1, time + workers[k][i]);
                    flag[i] = false;//去掉这个任务做过的标记
                }
            }
        }
    }
    
    int main()
    {
        cin >> N;
        for (int i = 1; i <= N; i++)
        {
            MIN[i] = MAXINT;
            for (int j = 1; j <= N; j++)
            {
                cin >> workers[i][j];
            }
        }
    
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (workers[i][j] < MIN[j])
                {
                    MIN[j] = workers[i][j]; //找到每一列的最小值
                }
            }
        }
    
        dfs(1, 0);
    
        cout << ans << endl;
        return 0;
    }
    

    方法二·匈牙利算法

    展开全文
  • LAPJV算法的Go实现,解决任务分配问题
  • 求解任务分配问题的带有推荐功能的蚁群算法
  • 针对空中群的作战任务分配问题,首先对战场环境进行了假设。 然后分别分析了战场的两个多属性主体,群飞机和攻击目标。第二,在综合考虑隐身和反隐身,攻击和反击的基础上,多车通过分析SA承担侦察,攻击和评估任务...
  • 蛮力法解决任务分配问题

    千次阅读 2018-10-08 10:54:17
    问题描述:假设有n个任务需要分配给n个人执行,每个任务只分配给一个人,每个人只分配一个任务,且第j个任务分配给第i个人的成本是C[i, j](1≤i , j≤n),任务分配问题要求找出总成本最小的分配方案。 可以用一...
  • 任务分配问题(匈牙利算法)

    千次阅读 2018-10-20 14:30:03
    【算法题】任务分配问题---匈牙利算法 一、问题描述 问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数...
  • 立了极大极小任务分配问题的混合整数线性规划模型,提出一种矩阵作业解答。并与穷举解及混合整数线性规划解 的计算复杂度进行了比较.理论分析和数值试验表明矩阵作业法对两类任务分配问题。极大极小和总体极小任务...
  • mmc生产任务分配问题

    千次阅读 2013-08-07 04:42:11
    mmc生产任务分配问题,本题目简单。
  • C/C++分支限界法-任务分配问题

    千次阅读 2020-05-19 11:38:42
    问题描述:任务分配问题要求把n个任务分配给n个人,每个人完成每项任务的成本不同,要求分配总成本最小的分配方案。 例: 任务分配矩阵如下 1.取每行最小值作为目标函数下界,即down=2+3+1+4=10; 用贪心算法选取...
  • 看了学姐写的任务分配问题---匈牙利算法,感觉很不错,自己转过来!一、问题描述问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,290
精华内容 2,516
关键字:

任务分配问题