最小最大准则范文（精选9篇）
最小最大准则 第1篇
To cope with the above uncertainty in prior probabilities, many approaches have been proposed[3—11].Ref.[2]gives an extensive survey on this subject.A-mong all the approaches presented, the minimax criterion is an effective one.The main idea of the approach is to minimize the worst (the maximum) possible overall risk.The corresponding classifier is referred to as minimax classifier which performs well over the range of all prior probabilities.Due to the robustness, the minimax classifier has been used in many applications.In ref.[12], a procedure based on the minimax criterion has been used to yield a solution to optimizing design of the control chart, which is an effective method for improving a firm’s quality and productivity.In ref.[13, 14], the minimax criterion is employed to help perform economical operations in electrochemical process of engineering practice.Ref.[2]presents a neural-based minimax classifier to find the minimax solution when there is a mismatch between the training and future priors.And also, the minimax criterion finds its use in the construction of intelligent tutoring systems[15].
However, the minimax criterion is too conservative.Compared with a Bayes classifier, the minimax classifier gives a relatively poor performance at most of possible prior probabilities.Motivated by this deficiency, this paper presents a novel classifier design method.We attempt to obtain a good approximation of the Bayes classifier by generalizing the minimax criterion.The basic idea of our method is to employ the principle of piecewise linear approximation.Firstly, the range of prior probabilities into three or more intervals is divided.
Then the minimum risk curve on each interval with a linear function is approximated.In such a way, a switched classifier with different expressions on different intervals can be constructed.In real applications, the prior probability is first estimated, and then select a proper classifier from the switched classifier according to the estimated value.
1 Brief review of minimax criterion
1.1 Minimax criterion
For the sake of convenience, some notations as follows.Consider a two-category classification problem is first introduced.
LetΩbe the feature space, andω1andω2denote the corresponding two categories.Assume further thatΩis divided into two decision regions, Ω1andΩ2, whereΩ1belongs toω1andΩ2belongs toω2, respectively.Furthermore, Letλijbe the loss incurred for decidingωjwhen the true state of nature isωi, P (ωi) the prior probability ofωiand p (x|ωi) the class-conditional probability density function for x conditioned onωi, where i, j=1, 2.Suppose that a particular feature vector x is observed and that contemplated taking actionαi (deciding the category of x to beωi) .Then the expected risk associated with taking actionαiis
The overall risk is then given by
where
and
Apparently, R is a function of P (ω1) .For a fixed prior P (ω1) , there exists optimum decision regionsΩ1andΩ2, which are decided by the minimum-risk decision rule and can minimize the overall risk R.The resulting minimum overall risk is called the Bayes risk.In this case, the best performance can be achieved.Nevertheless, the prior is difficult to be precisely determined in many applications and it may vary with time.If we design the classifier by a prior specified beforehand according to the given training data, a greater risk may be resulted in for other future priors.As a strategy, the minimax criterion tries to make the worst overall risk for any value of the priors as small as possible.That is, to minimize the maximum possible overall risk.
The overall risk against priors is depicted in fig.1.The curved line at the bottom represents an example of the Bayes risk with varying priors.It can be proved that the curve is convex and unimodal[1,16].The tangent line passing through point B, which corresponds to the prior maximizing the Bayes risk, illustrates the minimax solution.In this case, the minimax risk R*is independent of priors.We denote the prior corresponding to the minimax solution as P* (ω1) and the decision regions asΩ1*andΩ2*.Then we have
and P* (ω1) satisfies
Typically, the loss incurred for making an error is greater than the loss incurred for being correct.Based on this reasonable assumption, both of the factorsλ21-λ22andλ12-λ11are supposed to be positive.Therefore, the minimax decision rule is described as
For more detailed description of the minimax criterion, we can refer to ref.[16, 17].
1.2 Shortcomings of the minimax criterion
Theminimax classifier is designed according to a particular prior P* (ω1) .Whatever the future prior is, the overall risk is a constant R*.But for a possible future prior Po (ω1) , if it differs greatly from P* (ω1) , the minimax risk may be much larger than the ideal Bayes risk R.In this case, there will be a significantly disappointing degradation for the performance of a minimax classifier.Fig.1 shows a typical example of this case.
2 Switched classifier based on Piecewise Linearization
2.1 Piecewiselinearapproximationtothe Bayes classifier
In view of the shortcomings of the minimax criterion, we propose a classifier design method based on piecewise linear approximation.As shown in fig.1, three red bold lines, respectively tangent at three definite points A, B and C (The choice of the three points will be discussed later) , represent our piecewise linear solution.For explanatory facility, the three lines, from left to right, are respectively denoted as line 1, line 2and line 3.Their corresponding intervals in the horizontal axis are accordingly named as interval 1, interval 2 and interval 3.In fact, each line stands for a classifier designed according to the specific prior.Our decision rule is stated as:
If there is evidence showing that the estimated future prior lies in Interval k (k=1, 2, 3) , then we use the classifier corresponding to the Interval to make a decision.
This method is helpful because smaller risk will be resulted when making a decision compared with the minimax criterion.Moreover, it is an approximation to the Bayes decision.In order to clarify our idea, an example is given in fig.1.Suppose an estimated future prior Po (ω1) lies in interval 1.If we use the minimax classifier, the overall risk is R*.If we turn to our proposed classifier, then the overall risk is Ro.We can see that as long as the prior Po (ω1) falls into interval 1or interval 3, our piecewise risk Rois much smaller than the minimax risk R*, and much closer to the Bayes risk R.Even though the prior lies in interval 2, which is the worst case, the piecewise risk is the same as—no worse than, the minimax risk.To sum up, wecan sayΔR=R*-Ro≥0 is always valid.
2.2 Proof ofΔR≥0
First of all, we will prove thatΔR≥0 is always valid.Though it is obviously true shown from fig.1, a further rigorous analysis will be more convincing and benefit our later discussion.Since the classifier is piecewise, our proof will be separately presented accordingly.The following part will restrict our attention to the case in which the future Po (ω1) falls into Interval 1.
Proof:
Consider the case when the future estimated prior Po (ω1) falls into interval 1 and the classifier designed according to PA (ω1) is employed.The corresponding decision regions are denoted asΩ1AandΩ2A.Then the parameters aAand bAare two constants and the piecewise risk Rois a linear function of Po (ω1) .We write Roas Ro=aA+bAPo (ω1) .Since R*is independent of priors, we can say R*=a*+b*Po (ω1) , then
If we let
and
thenΔR can be simplified to
Another fact we should be clear is that when plotting R~P (ω1) curve, R is calculated according to egua. (2) for every P (ω1) .The decision regions in equa. (2) are obtained by the minimum-risk decision rule, which is
then we have
and
From fig.1 we can easily see that
and
Together with the generally reasonable assumptions ofλ21-λ22>0, λ12-λ11>0 andλ22-λ21<0, we have ax>0 and bx<0.Besides, axand bxare constants when point A is chosen.Therefore, ΔR=ax+bxPo (ω1) is a monotoneically decreasing function of Po (ω1) .When Po (ω1) =0, we haveΔR=ax>0from equa. (13) .And when Po (ω1) =P' (ω1) , we haveΔR=0 because the two risks are identically the same at this time.Consequently, for the monotony ofΔR, we know that
which means our piecewise linear decision risk is always smaller than the minimax risk.
The above presented is just the circumstance of Po (ω1) being in interval 1.With respect to interval 2, ΔR=0 is manifestly valid.When it comes to interval3, the proof follows a similar fashion.Taking these results together, we can say thatΔR≥0 is valid for all Po (ω1) ∈[0, 1].
2.3 Choice of points A, B and C
The proposed switched classifier is deeply related with the choice of points A, B and C.For the position of B, it is determined by equa. (7) .So the decision rule corresponding to interval 2 is
But when dealing with A and C, the situation is a little more complicated.We will refer to the principle of minimizing the summation of the overall decision risk across all priors—a principle which means that we should maximize the hatching area in fig.3.
Take the selection of point A as an example.According to fig.3, the upper-left hatching area can be expressed as
To obtain PA (ω1) that maximizes S, we need to solve the equation
Note that aAand bAare implicit functions of PA (ω1) .Further transformation of equa. (22) yields
In other words, the P (ω1) satisfying equa. (23) is the desired PA (ω1) .
After we get PA (ω1) , the decision rule of the presented classifier in interval 1 is described as Decideω1if
otherwise decideω2。
For the determination of point C and its corresponding decision rule, it follows the same way.
3 Application
The major topic of this paper is the derivation of the switched classifier, as described above.To demonstrate its application, we will give a description of its use for speaker recognition.Our experiments are run on the Connectionist Bench Data Set from the UCI Machine Learning Repository[18].It is a collection of fifteen individual speakers’pronunciation of eleven words (hid, h Id, h Ed, h Ad, h Yd, had, h Od, hod, h Ud, hud, hed) , each of which includes a vowel and was spoken by each individual six times.For every utterance there is a floating point number recording it, representing its sample feature.Our goal is to identify the speakers according to these known samples.We concentrated our attention on two individuals and the problem becomes a two-category pattern recognition application.
Three different classifiers are designed to solve the problem.They are Bayes, minimax and the presented switched classifier.60 samples are used as training data and 72 as testing ones.Since we find the floating numbers of each person’s utterances clutter about a mean value but are corrupted by some noise, the Gaussian density is a good model for the actual probability distribution.As for mean and variance, two parameters that completely decide the distribution, they are estimated by maximum-likelihood estimation.Furthermore, the zero-one loss function is employed to calculate the decision risk.
Having finished the classifier design, we use the test data to examine the classifiers’recognition rates.We intentionally control the ratio between the numbers of two categories’test data and treat it as the ratio between the two priors.This is reasonable and always used as a simple means for prior estimation.
Table 1 shows our results.For the three tests, there are three priors, respectively falling into the three different intervals.We can see that the Bayes classifier is the best one in all the three cases.When the estimated P (ω1) lies in interval 1 and interval 3, the presented classifier performs better than the minimax classifier and approaches closer to the Bayes classifier, but when it lies in interval 2, the two of them are the same.Our classifier’s superiority will be obvious especially when we can not get a precise prior estimation.For example, if we can only restrict the estimated P (ω1) to an interval, say P (ω1) ∈[0.7, 0.95], but enough to absolutely affirm P (ω1) falling into interval 3, we can use the results of line 3, too.That means our algorithm relaxes the limitation of the general classifier’s need for an exactly estimated prior.That may be of great convenience in many conditions.
4 Conclusion
A novel classifier design method based on piecewise linear approximation has been presented in this paper.Though the proposed classifier is illustrated as the combination of three classifiers, the number can be more than that if necessary.Our contributions are twofold.Firstly, the presented algorithm is not only an improvement of the minimax classifier but also an approximation to the Bayes classifier.Compared with the minimax classifier, it can saliently decrease risk when making decisions.Secondly, it is an alternative solution to the problem of unknown priors when designing a classifier.Only need to make a rough estimation of the prior instead of knowing the precise one.As long as the estimated prior falls into the right interval, our classifier will give a better result.
奥数最大和最小的问题教案 第2篇
最短的时间内完成作业，有更多时间发展自己的业余爱好
怎样乘车路程最短，话费时间最少
怎么样做可以使原材料最省
大桥建设在什么位置，才能方便附近尽可能多数居民
......例1.幼儿园老师把100根小棒分给小朋友做数学游戏，每个小朋友分的小棒根数不同。那么最多能分给几个小朋友？
100=10+20+30+40 100=10+11+12+13+14+15+25
分析：得掉小棒的小朋友尽量多
每个人分的根数不同
↓
丨
每个人得到的小棒尽量少
丨
丨
丨
每个人分得的根数分别是1，2，3，4，......算一算：1+2+3+4+5+...+？=100
试算：1+2+3+4+5+...+13=91
＜100
1+2+3+4+5+...+13+14=105
＞100
解：每人分得的小棒分别是1根，2跟，3根，4跟，......1+2+3+4+5+6+7+8+9+10+11+12+13=91（根）1 1 1 1 1 1 1 1
100-91=9（根）
100根分给13人，分别是1根，2根，...13根，余9根
这9根只能分给得小棒多的1人，2人...，最多9人
答：最多能分给13个小朋友。
例2.把自然数1，2，3，......，19依次排列，1234567891011......1819，划去24个数字后得到一个多位数，这个数最大是多少？
11213
71819
789 9
99887×错误
78989
分析：（1）去掉24个数字之后，得到一个几位数？
（2）要使得到的多位数最大，在高位上尽量留较大的数字，9，8，7，......解：（1）这一列数共有多少个数字？
｝
一位数：1-9，有9个数字
｝共有29个数字
二位数：10-19，有2×10=20个数字
｝
（2）划去24个数字后，得到一个几位数？
29-24=5（位）
（3）划去24个数字，合理的在高位数上尽量留较大数字
******819 819
划掉24个数字→97819
观察下面两组算式的结果怎样变化，由此得出什么规律？
10=1+9
1×9=9
10=2+8
2×8=16
10=3+7
3×7=21
10=4+6
4×6=24
10=5+5
5×5=25
规律1：两个数的和一定时，这两个数越接近，它们的乘积越大：当两个数相等时，它们的乘积最大。
例3.周长为36米2的竹篱笆围成一个长方形菜园，要使菜园的面积最大，它的长和宽应该是多少？这时的最大面积是多少？
分析：
面积最大
周长36米
长×宽（最大）
长+宽=18
规律1：长=宽时
解：菜园的长+宽是：
36*2=18（米）
据规律1，当长=宽时，长×宽的积最大
长-宽=18*2=9（米）
最大面积是：9×9=18（平方米）
答：菜园围成边长为9米的正方形，面积最大，最大的面积是81平方米。
观察下面两组算式的结果怎样变化，由此得出什么规律？
16=1×16
1+16=17
16=2×8
2+8=10
16=4×4
4+4= 8
规律2：两个数的积一定时，这两个数越接近，它们的和越小：当两个数相等时，它们的和最小。
例4.用竹篱笆围一个面积为25平方米的长方形菜园。这个长方形菜园的长、宽哥等于多少时，最省材料？
分析：最省材料→周长最小→长=宽（最小）
↑
面积25平方米→长×宽=25
规律2：长=宽时
解：因为长茶宽=25（平方米）
据规律2，当长=宽时，长+宽的和最小
25=5×5，所以：长=宽=5（米）时，周长最小
答：长方形菜园的长、宽都等于5米时周长最小，最省材料。
练习：把14拆成两个数字的和。再求出这两个数字的乘积。如何拆可以使乘积最大？最大积是多少？
分析：把14拆成两个数的和
两个数的乘积最大
↓
两个数的和是14
↓
↑
规律1：两个数相等时
解：14=7+7
最大积：7×7=49
答：14拆成两个7的和时，这两个数字的乘积最大，是49。
例5.把14拆成几个自然数的和，再求出这些数的乘积。如何拆可以使乘积最大？最大的乘积是多少？
14=7+7
14=4+5+5
分析：（1）拆分出的自然数个数应尽可能多
（2）拆分出来的每个数尽量小
（3）拆分出的自然数中没有1
（4）拆分出来的数字中3多2少，且数2最多两个
14=2+2+2+2+2+2+2
3+3
3+3
2×2×2×2×2×2×2=128
3×3×3×3×3×3×3=144
3×3×3×3×2=162
解：14=3+3+3+3+2
最大积是3×3×3×3×2=162
答：把14拆成4个3和1个2的和时，这几个数的乘积最大，是162。
规律3：把一个自然数拆成若干个自然数的和.如果要使这些数的乘积最大，那么拆出的数中3的个数尽量多，2的个数不多于两个。
例6.比较12489×12356与12359×12486的大小
↑ +3 ↑
观察：12489×12356 ○12359×12486
↓
↓
解：12489+12356=12359+12486 和一定
12489-12356=133
12486-12359=127
差较小
所以12489×12356 ＜ 1235912486
随堂练习
例1.幼儿园老师把100根小棒分给小朋友做数学游戏，每个小朋友分的小棒根数不同。那么最多能分给几个小朋友？
例2.把自然数1，2，3，......，19依次排列，1234567891011......1819，划去24个数字后得到一个多位数，这个数最大是多少？
例3.周长为36米2的竹篱笆围成一个长方形菜园，要使菜园的面积最大，它的长和宽应该是多少？这时的最大面积是多少？
例4.用竹篱笆围一个面积为25平方米的长方形菜园。这个长方形菜园的长、宽哥等于多少时，最省材料？
例5.把14拆成几个自然数的和，再求出这些数的乘积。如何拆可以使乘积最大？最大的乘积是多少？
例6.比较12489×12356与12359×12486的大小
课后作业
1.从0，1，2，4，6，8，9这七个数字中，选出五个数字组成一个被5整除并且尽可能大的五位数，这个五位数是多少？
2.小明看一本90页的童话故事，每天看的页数不同，而且一天中最少看3次。那么小明看完这本书需要多少天？
3.把自然数1，2，3，......，39，40 依次排列：
1234567891011......3940.划去65个数，得到的多位数最大是多少？
4.a，b是两个自然数，a+b=16，那么a×b最大是多少？
5.a，b是两个自然数，a×b=49，那么a+b最小是多少？
6.用40厘米的铁丝围成一个长方形（不计接头长度）中，最大的一个面积是多少平方米？
7.教室一个窗户的面积是225平方米，怎样设计窗户的形状和尺寸最省材料？
8.把17分成几个自然数的和，再求出这些数的积，要使得积尽可能地大，最大的积是多少？
9.把1，2，3，4，5，9，填入下面方框里，要使两个三位数的积最大，怎样填？
（）（）（）×（）（）（）
10.比较下面两个积的大小。
A=987654321×123456789
最小的“国家”最大的“网城” 第3篇
21岁的麻省理工学院辍学生莱恩拉奇,与一群志同道合的冒险者和电脑鬼才,准备把一座历史悠久、被拥有它的英国佬称做“海上孤岛”、孤立于北海当中的废弃碉堡,变成一个高科技城——一个超高频宽的网络服务器中心暨全球网络枢纽。
去年夏天,随着网络创投业者注入100万美元的资金,拉奇和他的同事们终于开始着手把海上孤岛建构成全世界第一个真正立足“海外”的电子资料庇护场所,一个拥有无限可能、处于法律灰色地带,不受任何国家管辖的地方。
这家新创立的公司就叫做Haven Co.Ltd(Haven是“庇护所”的意思),总部位于一座第二次世界大战留下的制空碉堡那片557平方米的甲板上。这座碉堡说实在没什么看头,就是被两根中空的笨重水泥圆柱顶在20米高的半空中、一块生满铁锈的铁板而已。上面有一栋看来死气沉沉的建筑物,和一个临时搭建的直升机停机坪。
欲建网络王国
拉奇相信在大刀阔斧的改造之下,海上孤岛很快就会焕然一新。支撑甲板的那两根水泥圆柱里面,将会放入价值数百万美元的网络设备:电脑、服务器、交易处理器、资料储存设备,当然还要有空调设备和发电机等基本设施。Haven Co.这个海上孤岛将提供客户每秒1gigabit的网络频宽,而价钱则要比层层管制的欧洲各国便宜上好几倍。Haven Co.可以通过微波、卫星和海底光纤网络迅速连结位于全球各地的合作伙伴,确保资料的流动如滔滔江水永不停歇。
Haven Co.的员工将搭乘直升机或快艇来公司报到,公司将有4名保安人员随时驻守,6名电脑怪才将负责整个网络营运中心的运作。拥有强大火力的保安人员,也已经准备好要把任何不速之客轰到九霄云外,他们的工作是要确保未经授权的船只和飞机与海上孤岛保持适当的距离;而电脑怪才们则负责维修工作,譬如更换出故障的硬盘和安装新设备等等。换句话说,如果你不小心从海上孤岛的甲板上掉下去的话,可能只有淹死的份;想要进去某一个机房,还得穿上全副潜水装备,因为机房里的纯氢气令人无法呼吸——为了防止外人入侵、灰尘和减少发生火警的危险,Haven Co.想到了使用氢气这个办法。
这里的法律虽然没有到无政府状态地无法无天,但是也宽松得让这些公司感觉“好自在”了。基本上,Haven Co.就是希望给人们一个安全的环境,没有律师、政府和各方闲杂人员的打扰。如果你想让别人无法追踪你公司付账系统的话,Haven Co.可以帮上你的忙;不过如果你想要帮毒贩洗钱,或者寄送儿童色情图片,那你想都别想。
原“国王”乐意甩包袱
而Haven Co.所存在的海上孤岛,是真实存在的一个迷你国家,于1967年成立,据说是全世界独一无二的海上小国。海上孤岛原本是一座塔台,它的前身是二次大战期间的一个海上碉堡,作用是防御英国免于纳粹轰炸机的攻击。它在战后被一个英国退役军人罗伊·贝兹占有,并重新命名为“海上孤岛”,宣布自大英帝国独立,并指定自己为“王储”。
这段日子以来,贝兹(正式“登基”为王,现年78岁)、他的妻子琼安(王后,70岁)和儿子麦可(47岁的王储)基本上是靠着打鱼和鱼类加工过日子,然后在平台和陆地之间往返,以保持英国和海上孤岛的双重国籍。他们想过了各种赚钱的方式——包括地下电台发射站、避税天堂,他们投入了大量的维护、修缮及法律费用,但是最后却发现海上孤岛是个只进不出的钱坑。在经历了一番跌跌撞撞的失败尝试之后,海上孤岛终于找到了最新的一批合作伙伴——Haven Co.,准备把这个地方纳入网络经济的一部分。
离梦想越来越近了
Haven Co.招募到了核心团队的成员,研究了相关且复杂的国际法律,另外也找到创业所需的资金。他们相信Haven Co.在营运的第3年结束前,可以赚进5000万到1亿美元的利润。
不过如此乐观的预测尚待观察,拉奇说他有不少客户已经在排队等待了。在Haven Co.正式开始上路之前,公司就已经吸引了相当多的资金。两位网络百万富翁公开表态加入Haven Co.:30岁的弗里曼(Avi Freed-man),前任Akamai的网络架构副总裁,投资了50万美元;34岁的日本Infoseek董事长伊藤(Joichi Ito)也注入了20万美元。(徐子超)
最小最大准则 第4篇
虚拟声通过双扬声器重放, 会引入交叉串声, 即不但左耳、而且右耳都会听到左扬声器的信号, 反之亦然。交叉串声的存在会破坏双耳声信号所包含的声音空间信息。因此, 通过扬声器重放时, 虚拟声场控制需先进行串声消除[1—3], 即在双耳声信号馈给扬声器重放之前, 先将其经过串声消除系统 (cross-talk cancellation system, CCS) , 用信号处理的方法进行预校正, 也即引入扬声器到双耳的传递矩阵的伪逆, 以消除交叉串声的影响。使得最终人左耳所听到的声信号为原始立体声的左通道信号, 右耳听到原始立体声的右通道信号。
扬声器重放双耳声信号的关键是串声消除, 串声消除是和声源 (扬声器) 与倾听者的相对位置密切相关的, 对于特定的扬声器布置, 信号处理只对特定的倾听位置有效, 也就是所谓的“甜点”。倾听者头部的转动会影响串声消除的效果。因而扬声器重放虚拟声的听音区域是窄的, 这是一种普遍缺陷。
扬声器重放和串声消除可看成是多输入、输出通路的线性系统。串声消除是按一定的理想条件进行设计的, 当系统的条件发生改变, 如倾听者头部转动或移动, 都有可能对重放声像产生影响。因而声像稳定性可看成是系统在一定的干扰下的鲁棒性问题。
20世纪90年代, Kirkeby等[4]提出了“立体声偶极子系统”, 即采用一对张角较小的扬声器系统来重放前方声场, 并指出相对于大张角扬声器重放系统, 立体声偶极可在一定程度上提高重放声像的稳定性, 其后小张角扬声器系统的虚拟声场控制的研究也越来越多[1—3], 但都是基于头部在特定位置时的串声消除算法, 即只追求局部最优。在扬声器张角确定的情况下, 还较少有文献研究如何通过算法优化来提高鲁棒性。现针对确定的扬声器张角、及允许头部偏移特定的倾听位置一定范围的情况下, 提出了一种新的基于最小最大准则的声场鲁棒控制优化算法。
1 鲁棒控制全局优化算法
1.1 经典串声消除结构
图1所示是经典的Atal-Schroeder两扬声器系统串音消除器框图[1], 扬声器与人头中心的张角为±θ (θ=0对应正前方) , 距离为r。左扬声器到左、右耳的声学通道传递函数分别为Cll和Clr, 右扬声器到左、右耳的声学通道传递函数则分别为Crl和Crr, 令, 为声学通道传输矩阵。原始的双通道立体声信号pL和pR, 经过串音消除矩阵H处理成两通路信号, 分别由左、右两个扬声器重放, 经过声学通道传输矩阵C到达双耳。
为了消除串声信号, 串音消除系统矩阵H的设计应该达到这样的目标:左边的信号只会到达左耳, 而不会在右耳处被接收。同样地, 右边的信号则只会被右耳所接收。即
当串声消除滤波器工作良好的时候, G的期望值为2×2单位矩阵。
对于头部在固定位置的CCS滤波器设计, Kirkeby等定义了一个代价函数[4]
式 (2) 中, ‖·‖2代表2-范数, I是一个2×2单位矩阵, u是双耳信号向量, v=Cu是扬声器输入信号向量。β为调整参数, 用于权衡输入信号对于性能误差的比例。式 (2) 右边的第一项表示串声消除的性能误差, 第二项为输入能量。
通过最小化J, 可以得到串音消除矩阵:
式 (3) 中右上角的角标T表示共轭转置。
需要注意的是式 (3) 的计算是在频域进行的, 要获得时域的FIR滤波器则必须还要进行反傅里叶变换和环形移位[5,6] (即延时) 。
在理想的倾听位置, 理论上应能完全消除串声。而偏离理想的倾听位置后, 即有可能出现一定的交叉串声。
串声消除的性能用通道分离度来表示, 假设
左右耳的通道分离度定义为
串声消除的性能用通道分离度来表示, 式 (5) 和式 (6) 表示在倾听者耳道声压中, 同侧与异侧的原始 (双耳声) 信号的贡献之比[7], 也即经串声消除系统补偿后的同侧与异侧通道的频域脉冲响应之比, 换算成d B值后则为二者之差。
串声消除系统最主要的问题是它对听音者头部位置的变化非常敏感。以上的CCS系统仅当听音者头部处于已知位置时效果较好, 也就是所谓的“甜点”过于狭窄。即使滤波器的设计能针对听音者头部所在的某个特定位置能给出完美的重放效果, 但当头移动时, 效果会下降。在文献[8]中, 提出了一种能跟踪听音者头部的位置从而可以持续更新滤波器的方法, 然而, 让听音者总是佩戴额外的跟踪器不大现实。
1.2 基于最大最小准则的鲁棒控制优化算法
以往的研究表明, 头的前后移动对串声消除性能变化的影响不大, 而左右移动则会引起很大的变化。希望当头偏离中心点时, CCS的效果依然能达到较好的性能。全局优化的策略更能满足这种实际的需要。
式 (3) 中, 参数β可以是常数[4], 也可以是频率相关的。β过小将使得异侧冲激响应峰值的两旁会出现不希望的峰;但β过大将会直接影响同侧和异侧响应的能量比值, 造成过低的通道分离度, 同侧冲激响应幅度下降了, 但是异侧冲激响应却增大了, 消除性能能将会很糟糕[9]。由于串声消除性能是与频率相关的, 所以β的调整随频率而变化更为合理。
线性系统的稳定性理论可应用于扬声器重放的分析[10], 根据系统理论, 表示系统在干扰作用下稳定性的条件数与扬声器张角和频率均有关, 串声消除只能在特定的扬声器布置和特定的频率是最稳定的。文献Takeeuchi[11]提出的最佳声源分布重放系统, 对不同的频率应采用不同半张角的扬声器布置, 也就是采用按不同半张角连续布置的一系列扬声器重放不同频率的双耳声信号。实际应用中, 可以采用几对不同张角的扬声器布置及串声消除处理, 分别重放不同频段的信号, 使得在可听声频率范围内串声消除近似是稳定的。这就是Takeeuchi提出的最佳声源分布重放系统。但现实中往往只允许布置一对扬声器, 所以应从频率对系统的稳定性的影响来考虑。
当β为常数时, 式 (3) 只是针对头部在确切位置给出了串声消除矩阵最优值, 也就是局部最优。如果在串声消除矩阵设计时就能考虑头部移动时的听音区域内的全局串声消除性能, 那也许在确定的头部位置时的串声消除性能会有所下降 (在可以接受的范围内) , 但是在听音区域内的其他地方却能得到改善。在实际使用中, 倾听者头部必须一动不动是不现实的。相对于某个确定点非常好、但其他地方都很差的情况, 往往更能接受可能没有哪一点特别好、但在整个范围内都可接受、较均衡的性能。可以制定这样的优化策略:通过算法优化, 如果偏离范围内性能最差的地方也可以接受 (或得到改善) , 那么全局优化就是成功的。
当头部位置不能精确获得时, 调整参数β能增加CCS系统的鲁棒性[12]。故提出在这种策略下如何随频率来自适应调整β的方法, 步骤如下:
确定一个头部移动区域, 在其中选取n个位置
(1) 对于特定的频率ω, 找出n个位置中串声消除性能最差的地方, 即对应通道分离度中的最小值min[Sep (β, ω) ]。
(2) 对情况最差的地方进行优化, 最大化min[Sep (β, ω) ], 当min[Sep (β, ω) ]最大时所对应的β即是对应频率ω时的最优值, 即
将式 (7) 代入式 (3) , 即得到新算法中的串声消除矩阵。
2 仿真实验
为验证算法的可行性, 进行了仿真实验。试验中采用了B&K 4100人工头来测量头传输函数HRTF、接收和记录扬声器的信号。双通路信号通过串音消除系统矩阵C处理成两通道信号之后, 馈给两个扬声器重放。
设定头部半径为0.087 5 m, 即B&K 4100人工头半径。两扬声器间距为10 cm, 扬声器连线中点距人头中心距离r为57 cm, 即系统半总张角θ=±5°。数据采样率为65 536 Hz。
考虑头部左右3 cm范围内的区域。其中x=0表示头处于中间位置, x=-2和x=-3表示头往左偏离2 cm和3 cm的位置, 类似地x=2和x=3表示往右偏离2 cm和3 cm的位置。需要指出的是, 偏离头部距离的最大值应小于波长, 否则无法分辨相位差为2π的两种情况。
图2~图4分别对应采用固定的β=0.01, β=0.001, 以及采用由本文提出的新算法即式 (7) 对应的β。其中, 图 (a) 、 (b) 和 (c) 分别对应头部在x=0, x=-2以及x=-3 (由对称性仅列出左边区域) 。每个图中上面的曲线表示同侧耳的频率响应, 下面的曲线表示异侧耳的频率响应, 二者之差即为通道分离度。
图2和图3为采用固定的β的仿真图, 由于采用固定的β都只是针对x=0处的算法, 可以看到当β变化时, 主要改变的是x=0处的情况, 其他偏离处的性能很难改善, x=-2和x=-3处的通道分离度都较差。图4是采用本文提出的随频率变化的β, 在x=0处的性能有所下降, 但在x=-2和明显得到改善, 图4 (b) 和图4 (c) 都要优于图2和图3中对应位置的情况。而且低频和中频段新算法的性能更为明显。而这也正是语音信号的主要频段。
3 总结
提出了一个用于虚拟声重放串声消除的鲁棒控制优化算法。在确定的扬声器张角下, 通过调整频率相关的参数β, 基于最小最大准则针对全局的通道分离度性能进行优化, 即使头部偏移特定的倾听位置一定范围, 依然可以保证较好的重放性能, 仿真结果表明相较针对固定头部位置的CCS算法, 该算法能提高头部转动时低频和中频段的鲁棒性。由于语音信号主要集中在4 000 Hz以下, 故提出的算法可满足该频段的要求, 具有较好的应用价值。
参考文献
[1] 谢菠荪.头相关传输函数与虚拟听觉.北京:国防工业出版社, 2008
[2] Parodi Y L, Rubak P.Analysis of design parameters for crosstalk cancellation filters applied to different loudspeaker configurations.Journal of Audio Engineering Society, 2011;59 (5) :304—320
[3] Doutre C, Nasiopoulos P.Optimized contrast reduction for crosstalk cancellation in 3D displays.Proc 3DTV Conference:The True Visioncapture, Transmission and Display of 3D Video (3DTV-CON) , Antalya, USA, 2011:1—4
[4] Kirkeby O, Nelson P A, Hamada H, Fast deconvolution of multichannel systems using regularization.IEEE Trans Speech Audio Process, 1998;6:189—195
[5] Hamada H.Construction of orthostereophonic system for the purposes of quasiinsitu recording and reproduction.J Acoust Soc Jpn, 1983;39:337—348
[6] Ward D B.Joint least squares optimization for robust acoustic crosstalk cancellation.IEEE Trans Speech Audio Process, 2000;8:211—215
[7] Gardner W G.3-D audio ising Loudspeakers.London:Kluwer Academic, 1998
[8] Gardner W G.Head tracked 3D audio using loudspeakers, .Proc IEEE Workshop Applicat.Signal Processing Audio Acoust (WASPAA-97) , Mohonk, NY, 1997
[9] Bai M R, Lee C C.Development and implementation of cross-talk cancellation system in spatial audio reproduction based on the subband filtering.J Sound Vib, 2006;290:1269—1289
[10] Nelson P A, Rose J F W.Errors in two-point sound reproduction.J Acoust Soc Am, 2005;118 (1) :193—204
[11] Takeuchi T, Nelson P A.Optimal source distribution for binaural synthesis over loudspeakers.J Acoust Soc Am, 2002;112 (6) :2786—2797
关于最大值与最小值问题的讨论 第5篇
一、增长函数
1.简单增长函数
f (t) =A+dt其中A、d为常数
它是时间t的线性函数.
2.复合增长函数
f (t) =A (1+r) t
函数成比例增长.
如银行年利率为r, 若现值为A, 则t年末本、利之和为f (t) .此时利率因以年计息, 称离散复利.
3.指数型成长函数
f (t) =Aert
函数呈指数型增长.
如银行利率为r, 现值为A, 按连续复利计算, t年末本利和为f (t) .
二、需求函数
需求量Q与价格P之间的函数关系称为需求函数, 记为Q=f (P) , 其中Q为需求量, P为价格, 它是单调减少函数.其反函数P=f-1 (Q) 也称为需求函数.
三、供给函数
设产品的供给量为Q, 价格为P, 一般地, 供给量Q是价格P的函数Q=渍 (P)
四、成本函数
设C为总成本, C1为固定成本, C2为可变成本, C为平均成本, Q为产量, 则有:
总成本函数C=C (Q) =C1+C2 (Q)
五、收益函数
设R为总收益, Q为销售量, P为价格
则R=R (Q) =PQ称为总收益函数
为平均收益函数
六、利润函数
设R为总收益, C为总成本, L为总利润.
则称L (Q) =R (Q) -C (Q) 为总利润函数.
列出函数关系式后, 就可以求驻点;然后判别函数在驻点处是否取得极值
利用极值可以解决复利与贴现问题:
复利与贴现问题主要是考虑时间因素对优化问题的作用, 若题设为连续复利, 年利率为r, 则t年后的资金按现值计算应乘贴现因子e-rt, 称为贴现问题;反之若现值t年后计算,
考虑资金利率因素, 应乘复利因子ert, 称为复利问题。
例1某酒厂有一批新酿的好酒, 如果现在 (假定t=0) 就售出, 总收入为R0 (元) ;如果用窖藏起来待来日按陈酒价格出售, t年末总收入为R=R0e-rt, 假定银行年利率为r, 并以连续复利计息.试求窖藏多少年售出可使总收入的现值最大, 并求r=0.06时的t值.
解:根据连续复利公式, 在年利率为r的情况下, 现值为A (元) , t年末的总收入为R (t) =Ate-rt, 反之t年末总收入为R (t) 的现值为代入,
即得到总收入的现值与窖藏时间t之间的关系式,
在用微分法求其最大值.
故是极大值点 (即最大值点) .故窖藏 (年) 售出, 总收入的现值最大.
当r=0.06时,
利用极值可以求成本最小, 或收益最大, 或利润最大等问题:
求成本最小, 或收益最大, 或利润最大等, 关键是要构造目标函数, 即构造成本函数、收益函数与利润函数。基本成本函数C (x) 主要由固定成本和可变成本两个部分构成, 固定成本也可记作C (0) , 一般不为零, 总收益函数R (x) 表示以价格P销售x单位产品获得的收益, 记为x P。其中x与P之间存在函数关系, 称为需求函数。因此R (x) =x P (x) 或P·x (p) 。收益函数一般可由需求弹性积分得到。而利润函数L (x) 可表示为R (x) -C (x) 。
例2已知某产品边际成本为 (万元/单位) , 固定成本为1万元, 产品对价格的需求弹性为产品最大需求量为8, 求使产品取最大利润时的产量和销售价。
解:由已知, 所以
又有 (这时由于经济意义, 可判定。分离变量
, 积分得lnx=ln|p-8|+lnc
因为x (0) =8, 代入有c+1, 故有x=8-p, R (x) =8x-x2
综上讨论,
为最大值点, 此时, 即当产量为16/9个单位, 售价为万元时, 利润最大。
例3:某商品进价为a (元/件) , 根据以往的经验, 当销售价为b (元/件) 时, 销售量为c件 (c、b、c均为正常数, 且市场调查表明, 销售价每下降10%, 销售量可增加40%, 现决定一次性降价.试问:当销售价定为多少时, 可获得最大利润?并求出最大利润。
解:设P表示降价后的价格, x为增加的销售量, L (x) 为总利润, 那么
令L' (x) =0得唯一驻点
由可知, x0为极大值点 (也是最大值点) , 故定价为
时, 得最大利润:
例4:设某工厂生产甲, 乙两种产品, 产量分别为x, y千件, 利润函数为L (x, y) =6x-x2+16y-4y2-2 (万元)
已知生产这两种产品时, 每千件产品均需消耗某种原料2000kg, 现有该原料12000kg, 问这两种产品各生产多少千件时, 总利润最大?最大利润为多少?
解:由题意2000 (x+y) =12000
因此, 问题就是在x+y=6的条件下求利润L (x, y) 的最大值, 为此设F (x, y, λ) =6x-x2+16y-4y2-2+λ (x+y-6)
解得唯一驻点既是极大值点, 也是最大值点。
因此, 甲、乙两产品分别生产千件时, 总利润最大, 最大利润为
(万元) 。
例5:某养殖场饲养两种鱼, 若甲种鱼放养x万尾, 乙种鱼放养y万尾, 收获时, 两种鱼的收获量分别为 (3-αx-βy) x和 (4-βx-2αy) , 求使产鱼总量最大的放养数。 (α>β>0)
解:设产鱼总量为z, 则z=3x+4y-ax2-2ay2-2βxy由极值的必要条件得方程组
得到B2-AC=4β2-8α2=-4 (2α2-β2)
由题设α>β>0故B2-AC=4β2-8α2=-4 (2α2-β2) , 且A<0, 故z在 (x, y) 处有极大值, 即有最大值。
x与y分别为甲, 乙两种鱼的放养数。
例6:设某产品的需求函数与供给函数分别为Qd=14-2P, Qs=-4+2P,
若厂商以供需一致来控制产量, 政府对产品征收的税率,
求: (1) t为何值时, 总税收最大, 最大值是多少?
(2) 征税前后的均衡价格和均衡产量。
解: (1) 税后供方销售单位产品得到收益是p-t, 因此, 供给函数应为Q=-4+2 (p-t) ,
于是, 供需平衡时有-4+2 (p-t) =14-2p, 得纳税后的均衡价。
从而纳税后的均衡产量也即销量为Q0=4-2p0=5-t
从而总税收为T=tQ0=5t-t2
知, 当税率为时, 总税收最大, 最大税收为
(2) 征税前, 由Qd=Qs, 即14-2P=-4+2P
得均衡价格和产量为, 而征税后的均衡价格与产量为,
利用极值可以解决广告问题:
广告费问题要注意两点:一是收益函数构造只取决于广告费的投入, 一般情况下与销量价格无关;二是广告费不列入一般成本函数。
例7:设某产品销售单价为5万元, 可变成本为每单位3.75万元。又设产品经广告宣传后能全部售出, 且销量与广告费A有关系式, 求使产品经营利润最大的广告投入。
解:依题意总收益函数为
又知A*为最优的广告投入, 使利润最大。
摘要：本文通过微积分最值的求法经大量例题分析, 运用函数的求导数、求积分、求偏导数等方法解决经济问题中复利与贴、成本最小, 或收益最大, 或利润最大, 税收等问题。
最小最大准则 第6篇
1中文自动分词算法简述
中文分词的基本方法是基于已有词典库或者规则库, 针对输入文字的字符串做分词、过滤处理, 输出最优切分的中文单词[1]。
中文分词算法主要分为以下四类[1,2,3]:
(1) 基于字符串匹配的分词方法:按照一定的字符串匹配策略, 将输入文字的字符串与词典库中的词条进行匹配, 若匹配成功, 则进行切分。主要算法有:最大匹配法、逆向最大匹配法、最佳匹配法、逐词遍历法等。
(2) 基于规则的分词方法:将基于字符串匹配的分词算法与分词规则库结合, 采用不同的策略对输入语句进行切分, 切分一致的部分判定为切分正确, 不一致的部分为歧义字段。
(3) 基于统计的分词方法:采用多种切分策略对输入字符串进行切分, 根据分词词典匹配出所有可能的切分情况并计算切分的概率, 求出概率最大的切分策略作为切分结果。
(4) 基于理解的分词方法:在分词的过程中, 不仅进行字符串的切分, 而且进行句法分析、语义分析, 利用句法和语义信息处理切分歧义。目前此方法尚处于试验阶段。
本文提出的基于最小费用最大流的中文分词算法模型即为基于字符串匹配的分词方法, 而且此分词算法模型可以拓展为基于统计的分词方法。
2基于最小费用最大流的中文分词算法模型
2.1最小费用最大流
最小费用最大流问题的定义如下:设G= (S, T, V, E) 是一个有向图, S为起点 (源点) , T为终点 (汇点) , 其中每一条边<u, v>∈E均有一个非负容量c (u, v) ≥0、一个费用cost (u, v) 和一个不大于容量的流量f (u, v) ≤c (u, v) , 问怎样制定运输方案使得从S到T的流量最大且总费用最小?
最小费用最大流问题的求解途径有两种[4]: (1) 保持网络中的可行流是最大流, 逐步调整使得总费用逐步减小, 最终得到最大流量的最小费用流; (2) 保持网络中的可行流是最小费用流, 逐步调整使得流量逐步增大, 最终得到最小费用的最大流。显然第二种途径与已 (i知, j) 最大i流问题j的求解算法相近, 并可以将问题转化为一个求从S点到T点的最短路径问题:不断以费用为权值, 使用最短路径算法, 寻找一条从S点到T点的最小费用增广路, 直至找不到从S点到T点的增广路。
2.2中文分词算法模型
基于上述最小费用最大流模型, 下面给出基于最小费用最大流的中文分词算法模型。
(1) 将输入文字串进行全切分。
1删去输入文字串的空格、回车等非中文字符。
2将得到的字符串对切分大小从1到7进行反复切分, 并在词典库中查找切分结果:找到, 则在词表增加一条记录;没找到, 则忽略此次切分结果。
(2) 基于全切分的结果建图。
1遍历全切分结果词表:对词表每一条记录添加一个顶点。如果词表两个记录u, v是相邻的, 则建立一条从u到v的有向边<u, v>, 容量c (u, v) =1, 费用cost (u, v) =1, 流量f (u, v) =0。
(3) 求解此最小费用最大流问题。
1在只允许通过容量-流量>0的边的限制下, 以费用为权值, 使用SPFA算法[5]求从源点S到汇点T的一条最短路径, 即最小费用增广路。
2对于 (a) 中求得的路径, 令路径上的每一条边的流量=容量。
3重复 (a) (b) 过程, 直至无法找到从源点S到汇点T的最短路径。
(4) 从源点S遍历整个图, 对于任意一条有向边<u, v>, 如果流量f (u, v) =c (u, v) , 输出顶点u和v对应的中文单词。即可得到中文分词结果。
2.3模型拓展
在上述分词算法模型的基础上, 通过改变边的费用权值, 可以将算法拓展为基于统计的分词方法。下面给出一种拓展方法[3]。
(1) 设词典包括n个词条, 则为这n个词条建立n×n的马尔科夫一阶转移矩阵Pn×n, 其中P (i, j) =词i与词j同时出现次数/词i词i出现次数。
(2) 建立从u到v的有向边<u, v>时, 令费用cost (u, v) =-log2 P (u, v) 。
这样我们就得到一个基于统计方法的最小费用最大流中文分词算法。
3算法分析与实验
3.1算法的时间复杂度分析
设输入字符串长度为N, 每次查询词典库的时间复杂度为ts, 则对字符串进行全切分的时间复杂度为O (Nts) ;设有向图G的顶点个数为|V|, 边的个数为|E|, 寻找最小费用增广路的次数为w, 则每次求解从源点S到汇点T的最短路径的时间复杂度为O (|E|) [5], 求解最小费用最大流问题的时间复杂度为O (w|E|) 。综合上述两个步骤的时间复杂度, 中文分词算法总时间复杂度为O (Nts+w|E|) 。
3.2实验
为了验证本文提出的中文分词算法的准确性, 本文使用教育部语言文字应用研究所《现代汉语语料库词频表》[6]作为词典库, 对50篇新闻文章进行中文分词, 分词正确率达到96.81%, 说明了此分词算法具有很高的准确性。
4结语
本文提出的基于最小费用最大流的中文分词算法模型不仅能准确地切分输入字符串, 而且可以通过改变费用权值拓展算法考虑的切分标准来提高切分准确度, 具有很好的拓展性。
参考文献
[1]龙树全, 赵正文, 唐华.中文分词算法概述[J].电脑知识与技术, 2009, 5 (10) :2605-2607.
[2]黄昌宁, 赵海.中文分词十年回顾[J].中文信息学报, 2007, 21 (3) :8-19.
[3]宋继华, 杨尔弘, 王强军.中文信息处理教程[M].北京:高等教育出版社, 2011.
[4]Orlin, J.B.A faster strongly polynomial minimum cost flow algorithm[J].Operations research, 1993:41 (2) , 338-350.
[5]段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报, 1994, 29 (2) :207-212.
最小最大准则 第7篇
关键词：最大公约数,最小公倍数,问题解决
在平时的教学中, 起初学生在没有理解最大公约数和最小公倍数的意义时, 就会产生困惑, 还有些数学应用题, 不具备常规的解题条件, 在解答时会感到无从下手, 因为这类题的特点是没有直接告诉求最大公约数还是求最小公倍数, 而是让你对题意的条件与问题通过阅读做出全面的分析, 找出几个关键性的词, 比如:最长 (或最多) 是多少, 最少、最短 (或至少) 是多少等等, 才能发现数量之间的关系, 才能找到解决问题的途径。新课标设计理念强调数学与人类的活动密切相关, 数学更加广泛地应用于生产和生活的各个方面。“最大公约数”和“最小公倍数”的用途与日俱增。例如:在做手工时把不同长短的几根木条截成长短相同的木条, 还不能有剩余;又如两辆公交车同时同地发车, 经过多长时间两车又相遇了;还有常见的在装修房间时要将长方形瓷砖铺成一块正方形瓷砖地板, 至少要用多少块瓷砖;人数不同的教学班, 分成人数相等的小组, 等等。用“最大公约数”与“最小公倍数”的含义去解决这些实际问题时就会变得容易许多, 同时会收到较好的效果。下面举几例加以分析。
一、用最大公约数解决日常实际问题
例1.同学们用长28分米、42分米、56分米的三种颜色的彩条, 截成同样长的小段, 围成一个学习园地, 不能有剩余, 问每段最长多少分米?
分析:要求截成的彩条的长度都相等, 必须找出28、42和56的最大公约数, 因为问题是“每段最长多少分米”, 所以就是要求28、42和56这三个数的最大公约数。
解答:每段最长为多少分米为:[28、42、56]=14 (分米)
例2.木工师傅要从长28厘米、宽42厘米、高56厘米的长方体木块中, 截出15块尽可能大的正方体木块。请帮木工师傅算一算, 这个木块够截吗?
分析:根据题意可知首先要算出最多能锯成同样大小的木块多少?这就首先求出长方体木块的长、宽、高的公约数;题中还要求尽可能大的正方体, 所以截成的正方体的棱长应该为长方体木块的长、宽、高的最大公约数。一旦求出长方体木块的长、宽、高各锯成的份数, 就可以求出锯成的块数。最后与15比一比便可知晓够不够截了。
正方体木料的棱长为[28、42、56]=14 (厘米) , 锯成正方体的块数为 (28÷14) × (42÷14) × (56÷14) =2×3×4=24 (块)
因为, 24>15所以能截出15块
例3.现有252个红球, 396个篮球, 468个黄球, 把它们分别装在若干个袋子里, 要求每个袋子里都有红、蓝和黄三种颜色的球, 而且每个袋子里的红球数相等, 篮球数相等, 黄球数相等, 问最多需要袋子多少个?每个袋子里各有红球、篮球和黄球多少只?
分析与解答:要求最多需要袋子多少个, 实际上是求每个袋子中最多能装相同数量的三种球各为多少只。因为252=2×2×3×3×7=36×7;396=2×2×2×3×11=36×11;468=2×2×3×3×13=36×13, 因此可得, 最多需要袋子36个。每只袋子里有红球7只, 篮球11只, 黄球13只。
二、用最小公倍数解决日常实际问题
例题1.五年级二班表演广播操。每行6人、8人或9人都正好排完, 五年级表演广播操的学生至少有多少人?
分析与解答:根据题意可知, 表演广播操的人数必须是6、8和9的公倍数, 要求学生至少有多少人, 所以是求6、8和9的最小公倍数。
表演广播操的学生人数至少有[6、8、9]=72 (人)
例2.用长方体石料堆积成一个正方体, 长方体的长32厘米、宽12厘米、高24厘米。至少需要这种长方体石料多少块?
分析:用长方体石料堆成一个正方体, 这个正方体的棱长分别是长方体石料的长、宽、高的倍数。因为题目中要求堆成一个最小的正方体, 所以正方体的棱长是长方体石料的长、宽、高的最小公倍数。因此正方体的棱长分别包含长方体的长、宽、高的份数, 这样就可以求出长方体石料的块数了。
解答:堆成的正方体的棱长为[32、12、24]=96 (厘米) , 长方体石料的块数就为 (96÷32) × (96÷12) × (96÷24) =3×8×4=96 (块)
例3.甲、乙、两艘轮船都来往于上下两港之间, 每往来一次, 甲需要6天, 乙需要8天, 两轮船同日同时从上港出发后, 两船相遇最少需要几天?
分析:甲船和乙船同日同时开船, 以后同时开船时, 所经过的时间必须是6天的倍数, 同时又是8天的倍数。因为题目中要求至少再经过多少天又同时开船, 所以是求6和8的最小公倍数。
解答:再次两船相遇最少需要的天数为:[6、8]=24 (天)
例4.一间屋子的地面是正方形的, 需要用长50厘米, 宽26厘米的长方形瓷砖, 来铺这间屋子, 至少要用多少块瓷砖?
分析:用长方形瓷砖铺一个正方形地面, 这个正方形地面的边长分别是长方形瓷砖的长、宽的倍数, 因为问题是至少要用多少块瓷砖?所以正方形地面的边长是长方形瓷砖的长、宽的最小公倍数。
解答:铺成一个最小的正方形瓷砖边长为:[50、26]=650 (厘米) 长方形瓷砖的块数是: (650÷50) × (650÷26) =13×25=325 (块)
最小最大准则 第8篇
文献[1]给出了最大值堆在满堆情况下的枚举计数公式，通过递归算法分析堆中结点的排列情况，最终推导实现了所有可能存在的不同的堆的总数目。但是该算法的时间复杂度接近O(n2)，实现的效率比较低。本文首先根据文献[1]的满堆计数公式，分析讨论了当最小最大堆为满堆时的情况，并推导出该堆的枚举技术公式;然后利用堆的对称原理给出了一个复杂度为为O(n)的实现算法[2]。
1 定义与定理
定义1：最小最大值堆[3]
最小最大堆是一颗完全二叉树，且其中每个元素有一个数据成员key。树的各层交替出现为最大层和最小层。根结点为最小层。设x是最小最大堆的任意结点，若x在最小(最大)层上，则x中的元素的key值在以x为根的子树的所有元素中是最小(最大)的。位于最小(最大)层的结点称为最小(最大)结点。
根据定义，最小最大堆是一颗完全二叉树，根结点为最小值所在的层，次结点为最大值所在的层，再次结点为次小值所在的层，以此类推，最小值层和最大值层交替出现。
定义2：满堆
当最小最大值堆是一棵满二叉树，即所有结点都不为空，称该堆为满堆。同理，满堆的左右子堆仍然是满堆。
为了后面的算法实现需要，根据最小最大值堆得定义和二叉树的性质，给出以下两个满最大最小值堆的性质引理。
引理1：设一个满堆中结点数目为n，规定根结点最小层为l，叶子结点的最大层为k，那么，n=2k-1，即k=log2(n+1)[1]。
引理2:满堆的第r层上结点总数为2r-1个;以满堆第r层的叶子结点为根结点的左、右子树也都是满堆，且子树结点的总数是2k-r+1-1个[1]。
特别是，当r=1时，r层只有一个结点，即根结点;当r=k时，r层上共有2k-1个结点，即叶子结点。以叶子结点为根结点的满堆只含有它自身一个结点。
2 最小最大值堆的枚举计数公式[1]
假设以最小最大值堆中第i个结点为根结点的子二叉树为Ti，并假设Ti的结点个数为bi，其左右子树分别为TLi、TRi。特别是，当i=1时，T1对应整个堆b1=n;当i=n时，Tn对应一个叶子结点，也是一个堆bn=1。
假定现有以n个结点，每个结点赋予不同的数值，用以构造F(n)个最小最大值堆。根据最小最大值堆的定义可知，需将n个数值按照定义1排列到n个结点位置上，过程描述如下：
1)从b1=n个数值中选出最小值作为根结点;再在余下的b1-1个数值中选择b2个用来构造左子树TL1;在余下的b3=b1-b2-1个数值用来构造右子树TR1。共有Cb2b1-1种可能存在的组合。
2)从b2个数值中选出最大值作为T2的根结点;再在余下的b2-1个数值中选择b4个用来构造左子树TL2;在余下的b5=b2-b4-1个数值用来构造右子树TR2。共有Cb4b2-1种可能存在的组合。
3)按照最小最大值堆的定义，反复依次执行1)、2)。
4)假设堆中最后一个非叶子结点编号为m，因为m=n/2，所以可能有两种情况：其一，n=2m的情况(如图1)，不存在右子树TR2m+1，假设b2m+1=bm-b2m-1=0,b2m+1!=1，下文将使用此式;其二，n=2m+1的情况(如图2)，存在右子树TR2m+1，并且bn=b2m+1=bm-b2m-1=1。
5)对任意叶子结点j(n/2+1≤j≤n)来说，以j为根的二叉树只包含一个结点，每次构造只1种可能情况。bj=1，并且(bj-1)!=bj!=1。
综合上述过程，当n个结点处都放置一个合适的数值后，就得到一个最小最大值堆。根据乘法原理可以得到：
整理上述公式，首先将公式左边乘上，原公式依然成立，即：
再对分子分母进行约简。比如首先进行化简。，全部化筒完毕就可以得到：
式(1)就是本文提出的n个结点的任意最小最大值堆的枚举数公式，其中bi代表以第i个结点为根结点的子二叉树的结点个数。
3 最小最大满堆的枚举计数公式
假设满堆结点总数为n，深度为k，枚举总数目F(n)可以写成H(k)。H(k)按照以步骤得到：
1)计算n!;
2)计算以第i个结点(1≤i≤n)为根结点的子树的结数目bi。根据引理2，如果结点i处于第r层，该子满堆的结点数是bi=2k-r+1-1个，又因为满堆的第r层上结点总数为2r-1个,所以：
3)整理式(1)为：
由引理1可知：n=2k-1,n!=(2k-1)!
由引理2可知：
当r=1时，(2k-r+1-1)2r-1=2k-1
4)当r=k时，即当结点i是满堆的叶子结点时：
综合(1)，(2)，(3)，式(2)可以改写为：
再令i=k-r+1，则r-1=k-i;当r=2时，i=k-1;当r=k-1时，i=2。所以式(3)可以改写为：
这正是文献[1]中给出的结点数为n的满堆的枚举计数公式，文献[1]已经给出严格证明。
4 任意最小最大值堆的枚举计数算法
首先提出了一个简单的算法实现了任意最小最大值堆的枚举计数公式。假定一个有n个结点的最小最大值堆，第i个结点的父亲结点为第i 2(2≤i≥n)。定义数组A[i]表示以结点i作为根结点的子树的结点总数bi。
算法1(初始化数组)：
1)初始化数组A，使得数组内元素A[i]=1(1≤i≤n)，A[0]不使用。
2)初始化循环变量k=n(2≤k≤n)。
3)第k结点的父亲结点编号用p表示，则由二叉树的定义p=k/2，做如下操作：p=k/2;A[p]=A[k]+A[p]。
4)k=k-1，如果k>1，转到步骤(3);否则算法结束。
算法2(最小最大值堆枚举实现)
1)计算n!;
2)调用算法1，初始化数组A;
3)对数组A内n个元素值求积，
4)根据式(1)可以得到堆的总数：
根据算法2，可以计算满足图3中n=9的最小最大值堆的总个数。图中数字只代表结点的编号。
根据算法l，计算得到的A数组如表1所示。
然后对数组A内n个元素值求积：所以9个结点的最小最大值堆的枚举总数F(9)=9!/405=896。
5 算法复杂度分析[2]
本文算法中只使用一个整型数组A，占用空间非小。初始化、计算数组A的时问复杂度均为O(n);根据本文算法编制的一个MATLAB7.0程序，运行在一台CPU主频为1.7GHz的奔4微机上，在0.0lms内，就能够计算出n=l4时堆的枚举总数目为：F(14)=2745600;在3ms内，就能够计算出n=50时堆的枚举总数目：F(50)=4.52024e+045。而文献[1]中算法计算F(14)=2745600就要花赞60000ms，显然本文算法的效率更高。
6 小结
本文在构造n元排列数组的过程中推导出具有n个结点的最小最大值堆的枚举计数公式，并且用一个高效算法实现这个公式。值得注意的是，本文提出的最小最大值堆的枚举计数公式是在完全二义树的基础上讨论的;对于基于完全叉树[4]的其他堆以及立体堆[5]等堆结构都有普遍的适用性。
摘要：根据最小最大堆的定义,对n元排列组合进行该堆的构造并推导出对应的n个结点最小最大值可能存在的堆枚举总数目的计算公式;并给出了在满堆情况下,时间复杂度为O(n)的任意最小最大堆得枚举算法实现。
关键词：最小最大值堆,枚举公式,算法,排列
参考文献
[1]孙强.计算任意最大值堆的枚举总数目的实用算法[J].计算机工程,2002(12):86.
[2]董兆安,孙强.最大值堆的枚举计数公式及其实现[J].计算机工程,2005(3):113.
[3]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1996:278.
[4]金远平.数据结构(c++描述)[M].北京:清华大学出版社,2005:156.
最小最大准则 第9篇
关键词：智能交通,交通事件检测,因子分析,最小最大概率机,交通事件
0引言
交通事件不仅会引起交通拥堵,而且极大地影响着人们的生命财产安全。研究表明,在发达国家由交通事件引起的交通拥堵已达到12% ~ 33%。因此,准确、及时的交通事件自动检测算法 (automated incident detection algorithms,AID) 对于提高交通运输系统的效率与安全具有重要意义。自20世纪70年代以来,发达国家对交通事件检测算法的持续研究取得了一系列卓有成效的成果。早期开发的交通事件检测算法主要有加利福尼亚算法[1]、标准偏差算法[2]、贝叶斯算法[3]、 基于突变理论的McMaster算法[4]、低通滤波算法[5]等,其中加利福尼亚算法和McMaster算法是被公认的2种经典算法,通常被用于对比新开发AID算法的性能。随着对交通流特性的深入研究以及人工智能等新技术的发展,一系列AID新方法相继产生,如神经网络算法[6]、支持向量机算法[7]、小波算法[8]、卡尔曼滤波算法[9]、贝叶斯算法[10]、多智能体算法[11]等等。然而,现有AID算法的输入变量大多依靠人工经验确定,且使用的人工智能算法普遍存在学习速度慢、容易陷入局部最优、易发生过拟合等方面的不足,从而导致误警率较高、检测时间偏长,严重影响着AID算法的泛化能力。笔者在分析交通事件条件下交通流参数变化趋势的基础上,多角度构建交通事件检测初始交通 变量,利用因子 分析方法 (factors analysis,FA)对初始交通变量进行特征提取,使其既包含原始数据的全部有效信息,又避免输入变量之间的冗余和重复,并充分利用最小最大概率机模型全局优化、适应性强、泛化能力好的特点设计全新的交通事件自动检测算法。
1最小最大概率机原理
最小最大 概率机[12](minimax probability machine,MPM)是1种基于最小错分概率的新型分类器,它的分类思想是通过控制错分概率以达到分类最大化的目的[13]。最小最大概率机模型能够充分利用数据的全局性质,以样本的均值和协方差代替真实的均值和协方差,从而实现较好的分类效果。
式中:α为正确分类样本数据的概率。
设则()κα是1个单调递增函数,当α达到最大值时,κ也一定达到最大值,优化问题(1)中求α的最大值等价于在约束条件
式中:α*和κ*为α 和κ 达到最优 值时的值。式 (2)中约去b后经简单变换可变为
设aT(x-x-) =1,优化问题可变为
消去变量κ后式(5)变为
这是1个凸优化问题,可以求出a的最优值a*,进而求出κ 的最优值κ*,把a*和κ*代入式 (3)求出b的最优值b*,此时最优分类超平面的判别函数为sign (aT*znew-b*),如果值为+1,表示znew属于x类,否则znew属于y类。对于线性不可分的情况,可以引入核函数把数据从低维空间映射到高维空间中使用最小最大概率机对数据进行分类。
2初始交通变量构建
当路段发生交通事件时,线圈检测器所获取的交通流参数会有明显的变化。交通事件发生位置上游检测器采集的流量和速度急剧下降,占有率急剧上升;下游检测器采集的流量下降、速度上升、占有率下降[14]。事件发生时段交通流参数的显著变化是设计交通事件自动检测算法的基本依据,通过大量分析事件状态下线圈检测器获取的交通流数据发现,不仅流量、速度、占有率3个基本参数在交通事件发生时段会有明显变化,不同交通参数之间的组合对交通事件的发生也表现出很强的敏感性。因此,本文选取了如表1所列的交通事件检测初始交通变量。
3基于FA和MPM交通事件检测算法流程设计
首先利用因子分析法对初始交通变量提取关键特征,然后用最小最大概率机分类算法对处理后的数据进行分类,可构造如图1所示的交通事件检测算法流程。具体步骤如下。
1)获取事件检测的初始交通变量数据集,并对数据集进行归一化处理,形成标准化的事件检测初始变量数据集。
2)对标准化后的交通变量数据集进行因子分析,提取主因子并计算因子得分,得到训练样本集和测试样本集。
3)用训练数据集训练最小最大概率机分类器,用交叉验证法选取最小最大概率机的参数,得到最优决策超平面aT*znew-b*=0。
4)利用判别函数sign (aT*znew-b*)判别测试数据的类别,本文将事件数据标记为+1,正常状态数据标记为-1。如果判别函数为+1,则表明测试数据为事件数据,如果判别函数为-1,则测试数据为正常状态数据。
4实证分析
4.1数据来源
实验数据来源于美国加利福尼亚州I-880数据库,该数据库包含I-880高速公路上35个检测站所有车道的流量、速度和占有率数据。数据的采样间隔为30s。前期采集时间为1993年2月16日~3月19日,后期采集时间为1993年9月27日 ~10月29日,记录了每 天上午05:00~ 10:00时,下午14:00~20:00时的交通流 数据。 通过整理数据,挑选出45个交通事件,其中,向北的事件22个,向南事件23个,将事件开始到事件结束时段内的所有交通流参数均视为事件数据。 将1993年2月18日全天无事件的交通流参数作为正常状态数据。将交通事件数据库与正常状态的交通数据库分为训练集和测试集2个部分,其中约2/3用于训练,剩余部分用于测试。
4.2初始交通变量的因子分析
利用SPSS17.0统计分析软件对选取初始交通变量进行因子分析,首先对初始交通变量数据集进行归一化标准处理,并进行KMO检验和巴特莱特球度检验。检验结果见表2。
由检验结 果可见,KMO值为0.833大于0.5,且巴特莱 特球度检 验的球度 检验值为6 738.372,显著性概率为0.000,小于0.01,说明本文选取的初始交通变量具有较强的相关性,适合做因子分析。图2为利用因子分析所得到的因子提取碎石图,由图2可见,只需提取前3个主因子即可较好的涵盖所有初始交通变量的有效信息。因此,本文选取主因子个数为3。
表3为交通变量的主因子得分,各个主因子可通过初始交通变量的线性组合表示,并可计算各个交通变量主因子的得分值,进而获取交通事件检测输入数据集。
4.3核函数的选择与参数确定
为了验证最小最大概率机算法的分类性能, 本文选取线 性MPM和核MPM 2种形式进 行分析,其中核函 数的表达 式为K (zi,zj)= exp(-‖zi-zj‖2/σ)。高斯核函数 参数σ 的选取对分类效果有很大影响,以往的研究大多按照经验选取。为了得到合理准确的核宽度σ 值,本文采用交叉验证的方法确定σ值,图3为向南方向测试数据库中高斯核函数参数σ对分类正确率的影响。
由实验结果可以看出,当σ为1.6时,交通事件检测率最高,达到98.6%,且当σ取0.4~1.6时,分类正确率维持在98.5%上下,具有较好的稳定性。因此,MPM算法对于参数的选取具有较好的鲁棒性,能够增强算法的灵活性,本文选取高斯核函数的核宽度值σ为1.6。
4.4实验结果分析
为了验证因子分析方法对于提高交通事件检测效果的有效性,笔者分别将初始交通变量和特征提取变量作为输入变量,以向南方向交通事件数据库为例,利用核函数MPM算法(kernel minimax probability machines,KMPM)和线性MPM算法 (linear minimax probability machines, LMPM)进行实验,采用检测 率 (identification rate,IR)、误检率 (false identification rate,FIR) 和平均检 测时间 (mean time to detection, MTTD)作为评价指标,结果见表4。
由检测结果可见,2种不同形式输入变量的事件检测效果均较好,相比之下,笔者提出的利用因子分析进行特征提取的交通事件检测方法效果更优。由此可见,深入分析交通流的运行特性,从多角度设计初始交通变量,能够得到较好的交通事件检测效果,同时对初始交通变量进行合理有效的特征提取对提高事件检测效果也尤为重要。
BP神经网络 模型 (back propagation neural network,BPNN)和支持向量机模型(support vector machine,SVM)是目前应用最广泛的2种人工智能AID算法,其应用效果得到了充分证明。为进一步对比分析本文所设计算法的有效性,本文选取以特征交通变量作为输入变量的BP神经网络模型和支持向量机模型作为对比算法进行对比分析。为充分验证本文设计算法的有效性,将事件数据按向南方向、向北方向和混合方向进行分类,分别进行实验分析和对比分析。实验结果见表5。
由检测结果可见,对于向南方向、向北方向和混合方向,FA-MPM方法事件 检测效果 均优于SVM和BP神经网络方法,且KMPM的检测效果更优于LMPM,说明FA-MPM能够有效的提高交通事件检测的效果,且使用核函数MPM方法的检测效果更优于线性MPM方法。从不同交通事件库的检测效果看,向南方向的事件检测效果最好,这是因为向南方向的交通事件大多导致多条车道发生堵塞,交通流参数波动较大;向北方向的事件检测效果最差,这是因为向北方向多为轻微交通事件,对交通流影响较小,交通流参数波动不明显。从混合方向的检测效果看,笔者所设计的算法总体取得了较好的检测效果,明显优于对比算法。
5结束语
针对现有交通事件检测算法在输入变量选取方面的局限性,笔者综合分析交通流参数的变化趋势,构建了全面的交通事件检测初始变量,设计了1种基于因子分析和最小最大概率机的交通事件检测算法,并通过实测数据验证取得了较好的检测效果。然而,本文方法仍存在一些不足和缺陷,主要有以下几点。
1)本文方法的实现依赖于道路上地点交通参数采集设备布设的数量和密度,且仅适用于连续交通流的高速公路和城市快速路,对于有信号控制的城市道路具有一定局限性。