贪心算法在医院信息系统中的应用

摘要:贪心算法是很常见的算法,贪心策略是最接近人的日常思维的一种解题策略。本文具体分析了医院信息系统中药品发放问题所具备的贪心选择与最优子结构性质,并给出了采用贪心算法解决药品发放问题的具体代码。

关键词:贪心算法;医院管理系统

中图分类号:TP317.3 文献标识码:A文章编号:1007-9599 (2010) 07-0000-01

Greedy Algorithm in the Hospital Information System

Yuan Guanyuan,Luo Lin,Du Jian

(South China Institute of Software Engineering of GuangZhou University,Guangzhou510990)

Abstract:Greedy algorithm is a series of selects to get a solution of the problem. The current status of each choice is the best choice in a sense that greedy choice. This article analyzes the system of drug distribution in hospital information problems with the greedy choice and optimal substructure,and gives the detail code of drug distribution problem with greedy algorithm.

Keywords:Greedy algorithm;HIS

一、贪心算法简介

贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法[1]。基本思路是从问题的某个初始解出发逐步逼近给定的目标,以尽可能快地求得更好的解。当到达算法中的某一步不能再继续前进的时候,算法停止[2]。

贪心算法具有两个重要的性质:一是贪心选择性质,指所求问题的整体最优解可以通过一系列局部最优解的选择来达到。二是最优子结构性质,指一个问题的最优解包含着它的子问题的最优解时[2]。

二、用贪心算法解决药品发放问题

医院信息系统(HIS)是数字医学的一个重要组成部分,具有很强的综合性、集成性、复杂性[3]。很多模块如排队模块、收费划价模块中的药品发放问题均可以采用贪心算法实现。

(一) 需求描述

在收费划价模块中,药房中同一种药品可能存在几种不同的批次,由于药品具有严格的有效期,因而发放次序需要严格按照先出厂的批次发放。在系统运行过程当中,往往最早批次的药品数量少于处方上所开的药品数量,这种情况下,需要对同一种药品发放两个甚至更多的批次才能满足要求。

(二)问题分析

本问题采用贪心算法求解,贪心策略如下:首先对最早批次的药品进行发放,即做完第一次选择后,原问题T变成了需对n-1个批次选择发放的新问题T’。新问题和原问题相同,只是问题规模由n减小为n-1。基于此种选择策略,对新问题T’,选择n-1个批次中最早批次的药品先进行发放,如此进行下去,直至达到处方所开数量为止。

显然,问题具有贪心算法的贪心选择和最优子结构这两个基本性质,可采用贪心算法解决。

(二) 系统设计

药品发放问题中,主要涉及到两个数据表:

一个是库存表,用于保存药品的库存信息,主要有药品ID、批次、数量等字段。

另一个是处方明细表,是处方表的字表,用于记录一个处方某种药品某个批次发放的数量。主要字段有处方单ID、,药品ID、批次、数量等字段。

药品发放时,根据医生所开处方某种药品的数量,从库存表中按照批次先后顺序减少库存,并在处方明细表中添加相关记录。

(三) 算法实现

以下代码采用C#描述,演示了使用贪心算法的药品发放方案:

DataTable stockTable; //药品库存,已按批次排序

decimal rest = Quantity; //未发放数

int rowIndex = 0; //当前行号

DataRow dr;//当前行

string batchNo;//当前行批次

decimal batchQuantity;//当前行存量

while (rest > 0)

{ dr = stockTable.Rows[rowIndex];

batchNo = dr[“BatchNo”].ToString();

batchQuantity= Convert.ToDecimal(dr[“Quantity”]);

if (batchQuantity >= rest)

{ //库存表数量减去 rest

//处方明细表中加入一条记录,批次为 batchNo,数量为 rest

rest = 0;

}

else

{ //库存表数量减去 batchQuantity

//在处方明细表中加入一条记录,批次为 batchNo,数量为 batchQuantity

rest -= batchQuantity;

}

rowIndex++; //进入下一行

}

(四)算法分析

程序主要是花费在对批次的排序和贪心算法,即按批次发放的时间上面。其中,贪心算法部分只有一重循环影响时间复杂度,其时间复杂度为O(n);而排序在读取数据库时进行,库存表中已按药品ID以及批次索引,因此,排序时间可以忽略不计。因此,综合来看算法的时间复杂度为O(n)。

三、总结

系统实际运行结果表明,用贪心算法解决药品发放问题是切实可行的,它能在保持很好性能的同时,使算法复杂度降低。

参考文献:

[1]常友渠,肖贵元,曾敏.贪心算法的探讨与研究[J].重庆电力高等专科学校学报.12(3):40-42

[2]王晓东.算法分析与设计[M].北京:电子工业出版社,2001:83-110

[3]薛涛,刘潇潇.医院信息系统建设与发展研究[J].电子商务.2010.2:40-41

作者简介:袁冠远(1977-),男,信息系统项目管理师,广州大学华软软件学院游戏系教师,主要研究方向为信息系统设计,计算机图形软件开发