网站开发宣传图片,做企业官网的步骤,网站设计制作价格怎么算,wordpress 下 刷文章指派问题概述#xff1a;实际中#xff0c;会遇到这样的问题#xff0c;有n项不同的任务#xff0c;需要n个人分别完成其中的1项#xff0c;每个人完成任务的时间不一样。于是就有一个问题#xff0c;如何分配任务使得花费时间最少。通俗来讲#xff0c;就是n*n矩阵中实际中会遇到这样的问题有n项不同的任务需要n个人分别完成其中的1项每个人完成任务的时间不一样。于是就有一个问题如何分配任务使得花费时间最少。通俗来讲就是n*n矩阵中选取n个元素每行每列各有1个元素使得和最小。如下图 指派问题性质指派问题的最优解有这样一个性质若从矩阵的一行(列)各元素中分别减去该行(列)的最小元素得到归约矩阵其最优解和原矩阵的最优解相同匈牙利法 12797989666717121491514661041071091.行归约每行元素减去该行的最小元素502022300001057298004063652.列归约每列元素减去该列的最小元素502022300001057298004063653.试指派(1)找到未被画线的含0元素最少的行列即遍历所有未被画线的0元素看下该0元素所在的行列一共有多少个0最终选取最少个数的那个0元素。(2)找到该行列中未被画线的0元素这就是一个独立0元素。对该0元素所在行和列画线。50202230000105729800406365502022300001057298004063655020223000010572980040636550202230000105729800406365(3)暂时不看被线覆盖的元素重复(1)(2)直到没有线可以画。(4)根据(2)找到的0元素个数判断找到n个独立0元素则Success小于n个则Fail.本例子中n5可以看到第一次试指派之后独立0元素有4个不符合4.画盖0线目标做最少的直线数覆盖所有0元素直线数就是独立0元素的个数。注意这跟3的线不同不能用贪心法去画线比如1 0 01 1 01 0 1若先画横的则得画3条线实际只需2条若先画竖的将矩阵转置后同理。步骤3得出的独立0元素的位置50202230000105729800406365(1)对没有独立0元素的行打勾、(2)对打勾的行所含0元素的列打勾(3)对所有打勾的列中所含独立0元素的行打勾(4)重复(2)(3)直到没有不能再打勾(5)对打勾的列和没有打勾的行画画线这就是最小盖0线。5020223000010572√9800406365√√5020223000010572√9800406365√√5.更新矩阵(1)对没有被线划到的数中找到最小的数。(2)对没有被线划到的数中减去最小的数。(3)对被2条线划到的数中加上最小的数。702024300008350118004041436.重复3-5直到成功。0100000100000010001010000sum 76964 32 匈牙利算法Hungarian Algorithm分配问题假设有N个人N个任务每个任务可以分配给任意不同的人不同的人对不同的任务需要花费的代价也不相同那么如何分配才能使花费总代价最少。假设现在有三个任务三个人每个人完成每个任务的代价矩阵如下代价可以是时间或者金钱等怎么才能找到一个分配方法使得任务花费代价最小呢匈牙利算法就是用来解决分配问题的一种方法它基于理论如果代价矩阵的某一行或某一列同时加或减某个数则这个新的代价矩阵的最优分配任然是原代价矩阵的最优分配。算法步骤假设矩阵为NxN方阵 1.对于矩阵的每一行减去其中最小的元素 2.对于矩阵的每一列减去其中最小的元素 3.用最少的水平线或垂直线覆盖矩阵中所有的0 4.如果线的数量等于N则找到了最优分配算法结束否则进入步骤5 5.找到没有被任何线覆盖的最小元素每个没被线覆盖的行减去这个元素个被线覆盖的列加上这个元素返回步骤3继续拿上面的例子演示 1.每一行减去其最小元素得到 2.每一列减去其最小元素得到 3.用最少的水平线或者垂直线覆盖所有的0得到 4.线的数量为2小于3进入第五步 5.现在没被覆盖的最小元素是5没被覆盖的行第一和第二行减去5得到 6.被覆盖的列第一列加上5得到 7.回到步骤3用最少的线覆盖所有0 8.线的数量3算法结束很显然第一个任务给第二人第二个任务给第一人第三个任务给第三人总代价最小000 9.所以原矩阵最小代价为40202585
