Algorithm1

Algorithm1

  • 2019-01-18

动态规划

第一小题

题目：

某工厂调查了解市场情况，估计在今后四个月内，市场对其产品的需求量如下表所示。

时期（月） 需要量（产品单位）
1 2
2 3
3 2
4 4

已知：对每个月来讲，生产一批产品的固定成本费为 3 (千元)，若不生产，则为零。每
生产单位产品的成本费为 1 （千元)。同时，在任何一个月内，生产能力所允许的最大生产
批量为不超过 6 个单位。
又知每单位产品的库存费用为每月 0.5 （千元），同时要求在第一个月开始之初， 及
在第四个月末，均无产品库存。
问：在满足上述条件下，该厂应如何安排各个时期的生产与库存，使所花的总成本费用
最低？
要求：写出各种变量、状态转移方程、递推关系式、和详细计算步骤。

解：

如下图：

FN7KZ8.md.jpg

FN7QIg.jpg

FNqzfe.jpg

1
2


第二小题

题目：

某推销员要从城市 v1 出发，访问其它城市 v2，v3，…，v6 各一次且仅一次，

最后返回 v1。D为各城市间的距离矩阵。问：该推销员应如何选择路线，才能使总的行程最短？

节点v1,v2,…,v6之间的距离矩阵D如下

$$
D= \left[

\begin{matrix}
0 & 10 & 20 & 30 & 40 & 50 \
12 & 0 & 18 & 30 & 25 & 21 \
23 & 19 & 0 & 5 & 10 & 15 \
34& 32 & 4 & 0 & 8 & 16 \
45 & 27 & 11 & 10 & 0 & 18 \
56 & 22 & 16 & 20 & 12 & 0 \

\end{matrix}
\right] \tag{1}
$$

解:

令L(v,U) 表示从v出发遍历U中所有点一次仅一次后返回到原点v_1的最短路径长度，则有如下的递推公式
$$
L(v_i,U_i) =\min_{v_{i+1} \in U_i } { L(v_{i+1},U_i -{v_{i+1}}) +D[v_i] [v_{i+1}] } \tag{2}
$$
特别的
$$
L(v_i, \emptyset) = D[v_i][0] \tag{3}
$$
令函数
$$
min_len( v_i,U_i )
$$
实现 L的功能

min_len ()函数输入起始城市和要遍历城市的集合，返回最小长度,下一跳节点组成的元组(最小长度,下一跳节点)流程图如下：

FNaoB8.png
主函数用于输出整个过程的路径和最小长度，流程如下：

答案输出：

最小路径长度： 80
路径为: V1 ->V2 ->V6 ->V5 ->V4 ->V3 ->V1

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
#!/usr/bin/env python
# encoding: utf-8
# 姓名：魏翔
# 学号：ZY1806220




dislist = [
    [0,10,20,30,40,50],
    [12,0,18,30,25,21],
    [23,19,0,5,10,15],
    [34,32,4,0,8,16],
    [45,27,11,10,0,18],
    [56,22,16,20,12,0]
]
U = set([0,1,2,3,4,5])

# 函数输入参数为：
# 起点v_i和待访问集合 u_i
# 函数返回：
# 以v_i为起点遍历u_i后返回原点v_1的最小路径长度 以及 下一跳节点编号
def min_len(v_i,u_i):
    if len(u_i)==0:              #  如果u_i集合为空则返回 （从v_i到v_0的长度，下一跳节点：0）
        return dislist[v_i][0],0 
    results = []
    for item in u_i:             #  遍历所有未访问过得节点，将他们作为下一跳
        temp = (min_len(item,u_i-{item})[0]+dislist[v_i][item],item) # 递推公式
        results.append(temp)
    result = min(results)        # 找到最小的路径长度和下一跳节点
    return result


if __name__ == "__main__":
    U=U-{0}
    print ("最小路径长度：",min_len(0,U)[0])  # 最短路径长度
    print("路径为:\n\nV1 -> ")
    index=0
    while len(U)!=0:                        # 循环打印路径索引（下一跳节点）
        result,index = min_len(index,U)
        print('V' + str(index+1)+' -> ')    # 路径索引加1 因为list索引下标是从0开始 而题目中的下标从1开始
        U.remove(index)

    print('V1')                             # 最后返回到v1节点

分支定界

问题描述

k9sKln.png

直接上代码

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
 //ZY1806220 魏翔
/*
 * @Description: Assignment 2
 * @Author: ZY1806220_魏翔
 * @Date: 2019-01-08 10:34:46
 * @LastEditTime: 2019-01-08 15:32:16
 * @LastEditors: Please set LastEditors
 */
#include<stdio.h>
#include<iostream>
#include<fstream>
#define max_vexNum 50
#define MAX_INT 0x7FFFFFFF
using namespace std;

typedef struct{
    bool is_visited[max_vexNum];                //标记节点在当前深度(deep)下是否被访问过 
    int dist[max_vexNum][max_vexNum];           //记录距离的邻接矩阵
    int cost[max_vexNum][max_vexNum];           //记录花费的邻接矩阵
    int path[max_vexNum];                       //记录全局最小距离对应的访问路径
    int sumCost;                                //记录全局最小距离对应的cost总和
    int min_sumDist;                            //记录全局最小距离
}Graph;
int path[max_vexNum] = {0};

/**
 * @description: 深度优先遍历图，并按条件进行剪枝，最终找到满足条件的最短路径，并更新全局最小距离，保存路径轨迹
 * @param {Graph &G:待遍历的图的引用, int start_vex：当前起始节点, int dist：从0到当前节点已用距离, int cost：从0到当前节点已用花费, int deep：当前深度}   
 * @return: void
 */
void DFS(Graph &G,int start_vex,int dist,int cost,int deep)
{
    G.is_visited[start_vex]=true;   //当前节点访问过标志为真
    path[deep] = start_vex+1;       //当前路径当前深度下节点编号
    
    if (start_vex==max_vexNum-1) {            //找到满足条件的更短路径，更新全局最短路径
        /* code */
        G.min_sumDist = dist;
        G.sumCost = cost;
        for (int i=0; i<max_vexNum;i++)
        {
            G.path[i]=0;
        }
        for (int i=0; i<=deep;i++)
        {
            G.path[i] = path[i];
        }
    }
    
    for(int i = 0; i < max_vexNum; i++)
    {
        /* code */
        if((G.dist[start_vex][i]>0) && (G.dist[start_vex][i]<9999) && (G.is_visited[i]==false))
        {
            int new_dist = dist+G.dist[start_vex][i];
            int new_cost = cost+G.cost[start_vex][i];
            if( (new_cost>1500) || (new_dist>G.min_sumDist)){       //满足剪枝条件
                continue;
                //这个剪枝的界还是不够紧凑
                //可以先通过Floyd求出每个节点到B的最短路径（路径下届）
                //求出每个节点到B的最小cost（花费下届）
                //如果 当前已有cost+从当前节点到B的最小cost>1500 || 
                //     当前已有路径长度+当前到B最短路径长>G.min_sumDist 
                //则剪枝
            }
            else{
                DFS(G,i,new_dist,new_cost,deep+1);
                G.is_visited[i]=false;
            }
        }
    }
    
}


/**
 * @description: 初始化图 
 * @param ：
 * Graph的引用 Graph &
 * @return: void
 */
void initial_Graph(Graph &G)
{
    ifstream in_dist;
    ifstream in_cost;
    in_dist.open("m1.txt");
    if(!in_dist.is_open()){
        cout<<"Open file m1.txt failure"<<endl;
    }
    in_cost.open("m2.txt");
    if(!in_cost.is_open()){
        cout<<"Open file m2.txt failure"<<endl;
    }
    for(int i=0; i<max_vexNum; i++)
    {
        G.is_visited[i]=false;
        G.path[i]=0;
    }
    G.sumCost = 0;
    G.min_sumDist = MAX_INT;
    for(int i = 0; i < max_vexNum; i++)
    {
        /* code */
        for(int j =0; j<max_vexNum; j++)
        {
            in_dist >> G.dist[i][j];
            in_cost >> G.cost[i][j];
        }
    }
}

/**
 * @description: 打印图G中的最小距离和其花费，以及最小距离对应的一个路径
 * @param {Graph &} 
 * @return: void
 */
void printGraph(Graph &G)
{
    printf("最小距离为:%d;\t其花费为:%d\n", G.min_sumDist, G.sumCost);
    for (int i = 0; G.path[i] != 0; i++)
    {
        if (i == 0) printf("路径:%d", G.path[i]);
        else printf("->%d", G.path[i]);
    }
}

int main(int argc, char const *argv[])
{
    Graph G;
    initial_Graph(G);
    DFS(G,0,0,0,0);
    printGraph(G);
    cout<<endl;
    system("pause");
    return 0;
}
感谢您的阅读，本文由 Space-X 版权所有。如若转载，请注明出处：Space-X（https://spaces-x.github.io/2019/01/18/alogorithm/）
Nanjing
DecoratorMode