当前位置: 首页>前端>正文

python cplex怎么排除局部最优解 python最优解问题

1、问题描述:设有n个任务由k个可并行工作的机器来完成,完成任务i需要时间为ti。试设计一个算法找出完成这个任务的最佳调度,使完成全部任务的时间最早。

2、算法设计:对任意给定的整数n和k,以及完成任务i需要的时间为ti(i=1~n)。计算完成这n个任务的最佳调度。

3、数据输入:由文件input.txt给出输入数据。第1行有2个正整数n和k。第2行的n个正整数是完成n个任务需要的时间。

4、结果输出:将计算的全部任务的最早时间输出到文件output.txt。

5、输入文件示例:             输出文件示例:

             input.txt                    output.txt

             7 3                              17

             2 14 4 16 6 5 3

6、实现思路:   

   用一棵深度为n的k叉树表示解空间。   

(1)搜索从开始结点(根结点)出发,以DFS搜索整个解空间。 

(2)每搜索完一条路径则记录下t和best序列,开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点,并成为一个新的活结点,也成为当前扩展结点。

(3)如果在当前的扩展结点处不能再向纵深方向扩展,则当前扩展结点就成为死结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点;直至找到一个解或全部解。

解空间如下图所示。例如:机器数为3,则为3叉树;任务数为4,则树深度为4;用3台机器去调度4个任务,把这棵树深度遍历后,最终选出最优值。

python cplex怎么排除局部最优解 python最优解问题,python cplex怎么排除局部最优解 python最优解问题_叉树,第1张

7、代码:

# 5-15最佳调度问题

n = 0  # 任务数
k = 0  # 机器数
best = 99999  # 最优值(完成全部任务的最早时间)
len = []  # 每台机器已安排的时间
t = []  # 每个任务所需的时间
x = []  # 当前路径(调度)
bestx = []  # 最优路径(调度)


# 计算任务完成的时间
def comp():

    tmp = 0
    for i in range(k):
        if len[i] > tmp:
            tmp = len[i]
    return tmp


# 以深度优先遍历方式遍历解空间树
def search(dep, len, t):

    global best

    if dep == n:
        tmp = comp()
        if tmp < best:
            best = tmp
            for i in range(n):
                bestx[i] = x[i]
        return

    for i in range(k):
        len[i] += t[dep]
        x[dep] = i + 1
        if len[i] < best:
            search(dep + 1, len, t)
        len[i] -= t[dep]


if __name__=="__main__":

    strN = input("请输入任务数n:")
    strK = input("请输入机器数k:")
    n = int(strN)
    k = int(strK)

    strT = input("请输入完成{}个任务需要的时间(以空格分隔,以回车结束):".format(n))
    t = strT.split(" ")
    t = list(map(int, t))  # str转为int

    len = [0 for _ in range(k)]  # k长度
    x = [0 for _ in range(n)]  # n长度
    bestx = [0 for _ in range(n)]  # n长度

    search(0, len, t)
    print("最优值:", best)
    print("最优解:", bestx)

8、测试:

(1)输入:n=7,k=3,t=[2, 14, 4, 16, 6, 5, 3]

          输出:best=17,bestx=[1, 2, 1, 3, 1, 1, 2]

python cplex怎么排除局部最优解 python最优解问题,python cplex怎么排除局部最优解 python最优解问题_叉树_02,第2张

(2)输入:n=9,k=4,t=[10, 14, 3, 9, 21, 6, 18, 16, 5]

          输出:best=26,bestx=[1, 2, 2, 2, 3, 4, 4, 1, 3]

python cplex怎么排除局部最优解 python最优解问题,python cplex怎么排除局部最优解 python最优解问题_搜索_03,第3张

 


https://www.xamrdz.com/web/2jr1957638.html

相关文章: