注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

小木舟的博客

笔墨生活随想,记录似水年华。

 
 
 

日志

 
 

餐巾问题(Napkin Problem) - Flex实现  

2012-01-06 00:52:31|  分类: 课程学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
餐巾问题(Napkin Problem) - Flex实现 - 小木舟 - 小木舟的博客

1.     问题描述(Problem Description

一个餐厅在相继的N天里,第i天需要ri块餐巾(i=12……n)。餐巾可以购买新的,每块餐巾p分,或者把旧餐巾送到快洗部,洗一块需m天,其费用为f分,或者送到慢洗部,洗一块需n天(n>m),其费用为s<f分。每天结束时餐厅必须决定多少块脏的餐巾送到快洗部,多少块送到慢洗部,以及多少保存起来延期送洗。但是洗好的餐巾和购买的新餐巾之和,要满足第i天的需求量,并使总的花费最小。

输入:天数N;每天需要的餐巾数ri;新餐巾的价值;快洗的天数;快洗费用;慢洗天数;慢洗费用。

输出:N天的方案;每天的方案包括新买餐巾数;干净餐巾数;快洗餐巾数;慢洗餐巾数;保存的餐巾数;总费用。

假定范围:2<N<30

2.     数学建模(Mathematical Modeling

l  问题概括

该餐巾问题属于图论领域的网络流优化问题,需要用最小费用最大流算法解决。最小费用最大流问题是经济学和管理学中的一类典型问题,一般定义是指在一个网络中每段路径都有容量费用两个限制的条件下,此类问题的研究试图寻找出:流量从AB,如何选择路径、分配经过路径的流量,可以达到所用的费用最小的要求。

l  建模说明

通过对问题的分析,可以使用二分图的建模方式,把每天分为二分图两个集合中的顶点XiYi,建立附加源S和汇TXi Yi分别表示每天要处理的餐巾很要使用的餐巾,分别用弧<SXi >和弧<YiT>的容量来限制数量。其中,每个Xi都有两条入边,一条<SXi >表示当天产生的需要处理的餐巾数,另一条< Xi-1Xi >表示上一天剩下的未处理的餐巾数,也就是说第i天既要处理当天产生的餐巾,又要处理昨天剩下的。同时,因为Xi有三种处理方式,即留到第i+1天、送快洗部以及送慢洗部,所以Xi有三条出边。概括如下:(其中N表示天数)

1)   S向每个Xi连一条容量为ri,费用为0的有向边。

2)   从每个YiT连一条容量为ri,费用为0的有向边。

3)   S向每个Yi连一条容量为无穷大,费用为p的有向边。   

4)   从每个XiXi+1 (i+1<=N)连一条容量为无穷大,费用为0的有向边。

5)   从每个XiYi+m (i+m<=N)连一条容量为无穷大,费用为f的有向边。

6)   从每个XiYi+n (i+n<=N)连一条容量为无穷大,费用为s的有向边。

建立的模型如下图所示:

餐巾问题(Napkin Problem) - Flex实现 - 小木舟 - 小木舟的博客

3.     算法设计(Algorithm Design

3.1 法描述

使用最小费用最大流的算法来解决餐巾问题,该算法和网络流的最大流算法思路相类似,它的基本思想是贪婪法,即:对于流f,每次选择最小费用可增广路径进行增广,直到不存在增广路径为止。这样的得到的最大流必然是费用最小的。算法的过程描述如下:

1)   求出从源S到汇T的最小费用路径(增广路径)和路径的最大流量f

2)   让路径上的边(i,j)流量减去f;让反向边(j,i)增加容量f,费用为-cost(i,j)

3)   重复1,2,直到从ST的流量=v(f)或者再也找不到从ST的最小费用路径(增广路径)为止。

3.2 法具体细节说明

l  求增广路径

该过程使用的是求单源最短路的SPFA算法Shortest Path Faster Algorithm,该算法是西南交通大学段凡丁于1994年发表的。只要最短路径存在,SPFA算法就必定能求出最小值。之所以不使用求单源最短路的经典算法Dijkstra算法,是因为在餐巾问题的模型中会存在负权边。SPFA算法伪码如下:

void spfa() {
  初始化(G,s);
  初始化队列Q;
  插入s到队列Q;
  while(!空(Q)) {
  u=Q的开头元素,并删除;
  for each v in adj[u] {
  tmp = d[v];
  relax(u,v);
  if((tmp<>d[v])&&(!v in Q)) 插入v到队列Q;
  }
  }
  }

l  松弛操作

单源最短路径算法中使用了松弛(relaxation)操作。松弛技术本质上就是一个贪心操作。松弛操作:对每个顶点vV,都设置一个属性d[v],用来描述从源点 s v 的最短路径上权值的上界,成为最短路径估计(Shortest-path Estimate),同时π[v]代表前趋。用下面的Θ(V)时间的过程来对最短路径估计和前趋进行初始化:

INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex v ∈ V[G]
do d[v] ← ∞
π[v] ← NIL
d[s] ← 0

  初始化之后,对所有 vVπ[v] = NIL,对vV – {s},有 d[s] = 0 以及 d[v] = ∞。松弛一条边(u, v),如果这条边可以对最短路径改进,则更新 d[v] π[v] 。一次松弛操作可以减小最短路径估计的值 d[v] ,并更新 v 的前趋域 π[v]。下面的伪代码对边(uv)进行了一步松弛操作:

RELAX(u, v, w)
if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
π[v] ← u

每个单源最短路径算法中都会调用INITIALIZE-SINGLE-SOURCE,然后重复对边进行松弛的过程。另外,松弛是改变最短路径和前趋的唯一方式。

l  最小费用最大流算法(MinCost_MaxFlow

算法思想见3.1部分的算法描述。算法伪码如下:

function mcmf():int
{
var flow:int = 0;
var cost:int = 0;
while(this.SPFA())
{
var minn:int = this.INF;
var u:int;
var i:int;
u = this.sink;
while(u != this.source)
{
minn = Math.min(minn,this.edges[this.pre[u]].vol);
u = this.edges[this.pre[u]].from;
}
u = this.sink;
while(u != this.source)
{
this.edges[this.pre[u]].vol -= minn; //前向边
this.edges[this.pre[u] ^ 1].vol += minn; //后向边
u = this.edges[this.pre[u]].from;
}
flow += minn;
cost += this.dis[this.sink] * minn;
}
return cost;
}

4. Flex实现的程序(Implementation with Flex

4.1 源码及演示程序

l  源码:http://jasonstudio.googlecode.com/svn/trunk/NapkinProblem/

l  演示程序:http://jasonstudio.googlecode.com/svn/trunk/NapkinProblem/bin-release/NapkinProblem.html

l  说明:程序主要用以演示,因此功能写得不完整,操作需要严格遵循以下简单流程:

餐巾问题(Napkin Problem) - Flex实现 - 小木舟 - 小木舟的博客


 对输入未作检验,输入的数值大小必须严格遵循餐巾问题的蕴涵条件,下面表为一输入示例的数据:

天数N

新餐巾的价值p

快洗的天数m

快洗费用f

慢洗天数n

慢洗费用s

3

10

2

3

3

2

各天需要的餐巾数量:

1

2

3

5

6

7

 4.2 程序效果截图

餐巾问题(Napkin Problem) - Flex实现 - 小木舟 - 小木舟的博客

输入面板和结果输出面板

餐巾问题(Napkin Problem) - Flex实现 - 小木舟 - 小木舟的博客

初始模型和最终结果模型

  其中,建立的模型图支持拖动,橙色顶点表示源S和汇T,较小者表示源,较大者表示汇。

5. 参考(Reference

本文主要参考了以下相关资料:

l  《最小费用最大流问题》:http://baike.baidu.com/view/638894.html?fromTaglist

l  《网络流》:http://zh.wikipedia.org/wiki/网络流

l  《网络流之——最小费用最大流》:http://yzmduncan.iteye.com/blog/985356

 


小木舟推荐阅读:
  评论这张
 
阅读(841)| 评论(1)
推荐

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017