动态规划--邮局选址问题

2020年06月05日 阅读数:90
这篇文章主要向大家介绍动态规划--邮局选址问题,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
动态规划(Dynamic Programming)是一种算法设计技术,它有着至关有趣的历史。做为一种使多阶段决策过程最优的通用方法,它是在20世纪50年代由一位卓越的美国数学家Richard Bellman所发明的。所以,这个技术名字中的“programming”是计划和规划的意思,不是表明计算法中的编程。它做为一种重要的工具在应用数学中的价值被你们认同之后,起码在计算机科学的圈子里,人们不只用它来解决特定类型的最优问题,并且最终把它做为一种通用的算法设计技术来使用。在这里,咱们正是从这个角度来考虑这种技术的。
  若是问题是由交叠的子问题所构成的,咱们就能够用动态规划技术来解决它。通常来讲,这样的子问题出如今对给定问题求解的递推关系中,这个递推关系中包含了相同类型的更小子问题的解。动态规划法建议,与其对交叠的子问题一次又一次地求解,还不如对每一个较小的子问题只求解一次并把记录记录在表中,这样就能够从表中得出原始问题的解。

  ——《算法设计与分析基础》算法


Description (问题描述)


  有一条公路通过V个村庄,每个村庄都处在整数的坐标点上(这里假设公路拉直为X轴).规划在这条公路上创建P个邮局,固然为了方便,这些邮局应建在某P个村庄上,可是要求让不一样村庄的人到邮局要走的总路程最小.
编程

Input数组

先从键盘读入两个整数V和P,而后再读入V个整数,分别表示V个村庄的坐标(坐标>=0)数据结构

Output函数

输出P个以空格分隔的整数,按坐标从小到的顺序给出P个邮局的坐标.工具

Sample Inputpost

       10 3spa

1 4 7 19 70 89 105 204 18 40设计

Sample Outputblog

7 89 204

 

Analysis(分析)

1、问题分析

l         在解决本问题以前,咱们有必要先明确如下几点要点:

一、对于复杂的问题,咱们有必要先从考虑简单状况出发,并由简单状况找出规律,发现思路

二、当有V个村庄点,且只有一个邮局点时,邮局点的最佳选址位置为这V个村庄点的中位点

三、当有V个村庄点,而且不仅一个邮局点时,咱们发现:此问题能够分解为多个子问题进行计算,而且邮局选址的最优解包含子问题的最优解,即这个邮局选址问题具备最佳子结构性质

四、在咱们容易地列出此问题的递归表达式(即后文即将说起的表达式1.1)以后,咱们发现:在递归计算的过程当中,许多子问题被重复计算了屡次

×         要点34的这两点发现,是选择动态规划求解的显著特征,也是咱们选择用动态规划来解决此问题的一个重要缘由.

2、算法分析

(一)、找出递归表达式

根据从特殊到通常的思路,咱们先考虑当邮局数为1时的状况,再考虑邮局数大于1的状况.

1、当邮局数P=1时,易知邮局的最佳选址位置为V个村庄的中位点

2、当邮局数P>1时,咱们能够想象每一个邮局对应一个辖区,那么问题就能够被转化为如何将V个村庄划分为连续的P个辖区.为此,咱们作如下定义:

(1)、Center(l,r),表示当村庄xlxr为一个辖区时,邮局所在位置

2)、Dis(l,r),表示当村庄xlxr为一个辖区时,该辖区内村庄到邮局的最小距离

(3)、TotolDis(t,k),表示将村庄xt以后的全部村庄(包括村庄xl)划分为k个辖区时,全部辖区的Dis(l,r) 总和的最小值,题目就转化为求TotolDis(t,k),有

下面,咱们仍是经过从特殊到通常的方法,考虑如何求TotolDis(t,k)

举特例:“在V=7,P=3时,目标是求TotolDis(t,k).”



显而易见,TotolDis(t,1)=Dis(t,6)t=2,3,4,5,6;也就是说TotolDis(1,2)=min{F,G,H,I,J},是能够在原有子问题上计算出来的.
  对于状况BCDE,同理.
  
根据上述特殊,推广而且改造表达式(1.1),可得:

                   

         显然,这是一个典型的递归过程.

 

(二)、构造动态规划的程序结构

       在以上定义Center(l,r)Dis(l.r)TotalDis(t,k)的基础上,构造合理的数据结构和控制结构,自底向上的求解这个问题.

       仍是先考虑上述“V=7P=3,村庄坐标为06”的特例,Center(l,r)表和Dis(l,r)表以下所示.

l"r

0

1

2

3

4

5

6

l"r

0

1

2

3

4

5

6

0

0

0

1

1

2

2

3

0

0

1

2

4

6

9

12

1

 

1

1

2

2

3

3

1

 

0

1

2

4

6

9

2

   

2

2

3

3

4

2

   

0

1

2

4

6

3

     

3

3

4

4

3

     

0

1

2

4

4

       

4

4

5

4

       

0

1

2

5

         

5

5

5

         

0

1

6

           

6

6

           

0

center[l][r]

1-1 特例的Center(l,r)

dis[l][r]

1-2 特例的Dis(l,r)

      

       据此,咱们能够很容易的编写出计算center[l][r]dis[l][r]的代码模块.

 

 1 void  calculateCenter() {
 2
 3       //--- 内存分配
 4
 5       center = new unsigned *[village];      //动态分配二维数组的第一维
 6
 7       for (unsigned i=0; i<village; i++)      //动态分配二维数组的第二维
 8
 9              center[i] = new unsigned[village];     
10
11       
12
13       //--- 初始化Center(l,r)
14
15       for (unsigned l = 0; l < village; l++)   
16
17              for (unsigned r = l; r < village; r++)
18
19                     center[l][r] = xCoordinate[(r-l)/2 + l];
20
21}

22

calculateCenter()函数

 1 void  calculateDis() {
 2
 3       //--- 内存分配
 4
 5       dis = new unsigned *[village];            //动态分配二维数组的第一维
 6
 7       for (unsigned i = 0; i < village; i++)     //动态分配二维数组的第二维
 8
 9              dis[i] = new unsigned[village];
10
11       
12
13       //--- 初始化Dis(l,r)
14
15       for (unsigned l = 0; l < village; l++)
16
17              for (unsigned r = l; r < village; r++){
18
19                     dis[l][r] = 0;
20
21                     for (unsigned k = l; k <= r; k++)
22
23                            if (center[l][r] > xCoordinate[k])
24
25                                   dis[l][r] += center[l][r] - xCoordinate[k];
26
27                            else
28
29                                   dis[l][r] += xCoordinate[k]- center[l][r];
30
31              }

32
33}

34

calculateDis()函数

      
  
在计算TotalDis(0,P)时,因为题目要求输出邮局的位置,因此在计算TotalDis(0,P)的过程当中,只计算最小值还不够,还必须记录下取得最小值时的分辖区状况.因而,咱们这么定义TotalDis二维数组.

  

 1 struct  info {
 2
 3       unsigned dis;   //最小值
 4
 5       unsigned r;     //标号r以前(包括r)的村庄为一个辖区
 6
 7}
;
 8
 9  
10
11 info  ** totalDis = NULL;
12

 

totalDis表的元素结构


  计算过程以下所示.

 1 void  calculateTotalDis() {
 2
 3       //--- 内存分配
 4
 5       totalDis = new info *[village];       //动态分配二维数组的第一维
 6
 7       for (unsigned i = 0; i < village; i++)     //动态分配二维数组的第二维
 8
 9              totalDis[i] = new info[postoffice+1]; 
10
11 
12
13       //--- 计算TotalDis(v,p+1)
14
15       //---- 当k=1时,根据公式(1.2),直接计算
16
17       for (unsigned t = 0; t < village; t++)
18
19              totalDis[t][1].dis = dis[t][village-1];
20
21       //---- 当k=2,3,,p时的状况
22
23       for (unsigned k = 2; k <= postoffice; k++)
24
25              for (unsigned t = 0; t < village; t++){
26
27                     totalDis[t][k].dis = (unsigned)-1;
28
29                     totalDis[t][k].r = 0;
30
31                     for (unsigned r = t; r <= village-k; r++){
32
33                            unsigned temp = dis[t][r] + totalDis[r+1][k-1].dis;
34
35                            //---- 计算最小值
36
37                            if (temp < totalDis[t][k].dis){
38
39                                   totalDis[t][k].dis = temp;
40
41                                   totalDis[t][k].r = r;
42
43                            }

44
45                     }

46
47              }

48
49}

50

calculateTotalDis()函数


  获得的
TotalDis(t,k)表以下所示.

t"k(dis/r)

1

2

3

0

12/

2/6

4/0

1

9/

4/3

3/1

2

6/

3/3

2/2

3

4/

2/3

1/3

4

2/

1/4

0/4

5

1/

0/5

-1/0

6

0/

-1/0

-1/0

 表示此区域在本算法中为无效区域

 表示此区域在本算法中为有效区域

totalDis[t][k]

1-3 特例的TotalDis(t,k)


  对于本题,还有一个地方须要注意,那就是输出.因为题目要求输出各邮局的坐标,在这里需用到递归的方法,具体输出模块以下所示.


  

 1 void  output(unsigned t, unsigned k) {
 2
 3       if (1 == k)
 4
 5              cout << center[t][village-1];
 6
 7       else{
 8
 9              cout << center[t][totalDis[t][k].r] << ' ';
10
11              output(totalDis[t][k].r+1, k-1); //递归
12
13       }

14
15}

16

 

output函数


  3、结语

              另外,本问题也能够采用“备忘录”方式解决,有兴趣的朋友能够本身研究,这里再也不赘述.

时间仓促,水平有限,不足之处,请各位批评指正!


Code(源码)

  下载入口:
  http://www.cnblogs.com/Files/norx/[ReleaseEdition].[DynamicProgramming].[ByNORX].rar