算法设计的两个例子

标签（空格分隔）： 算法知识文档

---

例1:调度问题

问题:

有n项任务,每项任务加工时间已知.从0时刻开始陆续安排到一台机器上加工.每个任务的完成时间是从0时刻到任务加工截至的时间.

求:

总完成时间(所有任务完成时间之和)最短的安排方案.

实例:

任务集: $S = lbrace 1,2,3,4,5 rbrace$
加工时间: $t_{1} = 3, t_{2} = 8, t_{3} = 5, t_{4} = 10, t_{5} = 15$

分析:

我们需要计算的是所有任务完成时间之和.因为只有一台机器,所以做第i项任务需等待第i-1项任务做完,我们所要求解的是如何安排做这些任务的顺序使得总时间最小.比如,如果按照实例所给出的5个任务顺序的进行加工,需要的总时间计算如下:

$$t_{sum} = t_{1} + (t_{1}+t_{2}) + (t_{1}+t_{2}+t_{3}) + (t_{1}+t_{2}+t_{3}+t_{4}) + (t_{1}+t_{2}+t_{3}+t_{4}+t_{5})$$

求得: $t_{sum} = 3*5 + 8*4 + 5*3 + 10*2+ 15*1 = 97$

贪心算法的解:

算法描述: 优先选择加工时间短的任务先完成
算法: 按照加工时间从小到大排列$(3, 5, 8, 10, 15)$
解: 任务加工顺序 $(1, 3, 2, 4, 5)$

总完成时间: $t_{sum} = 3*5 + 5*4 + 8*3 + 10*2+ 15*1 = 94$
当前总时间是最小的,后面会给出证明.我们先进行问题的建模.

问题建模

输入:
任务集合: $S = lbrace 1,2,3,...,n rbrace$
第j项任务加工时间: $t_{j} in Z^{+}, j = 1,2,3,..,n$

输出:
调度$I$ ($S$的排列) $i_{1},i_{2},i_{3},...,i_{n}$

目标函数:
I的完成时间, $T_{sum}(I) = sum_{k=1} ^ n(n-k+1)*t_{i_{k}}$

解:$I^*$使得目标函数的值达到最小

$$T_{sum}(I^*) = min lbrace T_{sum}(I)|I是S的排列 rbrace$$

证明贪心算法的正确性:

设计策略:
加工时间短任务的先做

算法:
根据加工时间从小到大排序,依次进行加工

算法的正确性:
对所有输入样例都得到最优解

证明:
加入调度$f$第 $i,j, j = i+1$ 项任务逆序,即$t_{i} > t{j}$
交换任务顺序$j,i, j = i-1$得到新的调度$g$中有$t_{j} < t_{i}$
带入目标函数公式不难知道:

$$A = B-1$$
$$T_{sum}(g)-T_{sum}(f) = (A*t_{i}+B*t{j})-(A*t_{j}+B*t_{i}) = t_{j}-t_{i} < 0$$
可知,减少一个逆序便能减少时间,将任务时间按从小到大排序得到 $I^*$,当前序列中没有相邻的逆序对, $T_{sum}(I^*)$就是最优解.

$$begin{array}{|rrrrrrrr|} hline & color{red}{CODE:}& hline end{array}$$

/************************************************
@author: hejun
算法复杂度:O(NlogN)
简单的任务调度问题,还没有经过oj题目的验证
************************************************/
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define MAX_N 100005 // 最大任务总数
int t[MAX_N]; // 第i项任务需要的时间
int n; // 有n项任务

 // 贪心算法解决
void solve(){
    LL ans = 0;
    sort(t, t+n); // 按照任务需要完成的时间从小到大排序
    for(int i = 0; i < n; i++) ans += (n-i)*t[i]; // 计算最优解
    printf("%lldn", ans); // 输出最优解
}

int main(){
    freopen("in.txt", "r", stdin);
    int i;
    while(~scanf("%d", &n) && n){ // 输入有n项任务
        for(i = 0; i < n; i++) scanf("%d", &t[i]); // 输入第i项任务需要的时间
        solve(); // 贪心算法解决
    }
    return 0;
}

运行实例:
输入:
5
3 8 5 10 15
输出:
94

例2:投资问题

问题:

$m$元钱,投资$n$个项目.效益函数$f_{i}(x)$,表示第$i$个项目投资$x$元的效益, $i = 1, 2, 3, ... , n.$求如何分配每个项目的钱使得总效益最大?

实例:

5万元,投资给4个项目,效益函数:

$x$	$f_{1}(x)$	$f_{2}(x)$	$f_{3}(x)$	$f_{4}(x)$
0	0	0	0	0
1	11	0	2	20
2	12	5	10	21
3	13	10	30	22
4	14	15	32	23
5	15	20	40	24

问题建模:

输入:
$n, m, f_{i}(x), i = 1,2,3,..,n, x = 1,2,...,m$

解:
$n$维向量$<x_{1},x_{2},...,x_{n}>, x_{i}是第i个投资第i个项目的钱,使得满足下面的条件$
目标函数:

$$max sum_{i=1}^nf_{i}(x_{i})$$
约束条件: $$sum_{i=1}^nx_{i} = m, x_{i} in N$$

蛮力算法:

描述:
枚举所有可能的解 <x1,x2,...,xn> < x 1 , x 2 , . . . , x n > <script type="math/tex" id="MathJax-Element-104"> </script>满足 $x_{1}+x_{2}+...+x_{n} = m$然后求解当前解的效益总值,得到最大的效益值对应的解向量.

实际计算:
对于当前实例:
$x_{1}+x_{2}+x_{3}+x_{4} = 5$
$s_{1} = <0,0,0,5> v(s_{1}) = 24$
$s_{2} = <0,0,1,4> v(s_{2}) = 25$
$s_{3} = <0,0,2,3> v(s_{3}) = 32$
…
$s_{56} = <5,0,0,0> v(s_{56}) = 15$

解:
$s = <1,0,3,1> v(s) = 11+0+30+20 = 61$

算法效率分析:
方程$x_{1}+$x_{2}+ … +$x_{n} = m$的非负整数解 <x1,x2,...,xn> < x 1 , x 2 , . . . , x n > <script type="math/tex" id="MathJax-Element-114"> </script>的个数估计:
可行解表示成0,1序列:m个1,n-1个0
$1...1 0 1...1 0 1...1$
$n = 4, m = 7$
可行解 <1,2,3,1> < 1 , 2 , 3 , 1 > <script type="math/tex" id="MathJax-Element-117"><1, 2, 3, 1></script>可以表示成序列: $1011011101$
所以这样的序列个数就是在 $m+n-1个数字中选择m个1$
序列个数是输入规模的指数函数:

$$C_{m+n-1} ^ m = frac {(m+n-1)!} {(n-1)!m!} = Omega((1+epsilon)^{m+n-1})$$

小结:

问题求解的关键:

• 建模: 对输入参数和解给出形式化或者半形式化的描述
• 设计算法:采用什么算法设计技术,正确性–是否对所有的实例都得到正确的解
• 分析算法–效率

最后

以上就是疯狂硬币为你收集整理的算法设计的两个例子算法设计的两个例子的全部内容，希望文章能够帮你解决算法设计的两个例子算法设计的两个例子所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。