关于"决斗"问题的思考：
原题请参见此贴：
http://expert.csdn.net/Expert/topic/2209/2209486.xml?temp=.8447229
我把他分成两个问题：
1：每个人都不放空枪。
2：每个人都可放空枪。
第一个问题理论上是基本上解决了。
第二个问题按第一个问题的框架，遇到一个很大的困难，
故再发一个新贴，希望大家都来看看，研究研究。
决斗问题，
引理1：设A1,A2两人的命中率分别为P1,P2; A1先开枪。
则A1生存的概率为：P1/(1-(1-P1)*(1-P2))
A2生存的概率为：((1-P1)*P2)/(1-(1-P1)*(1-P2))
证明：A1第一次射A2,有P1的几率命中，
A1第二次射A2,这是当A1,A2第一次射击都没命中的情况下才会发生，
故发生A1第二次射击的概率是(1-P1)*(1-P2)，
A1在第二次射击中命中A2的概率是P1*(1-P1)*(1-P2))
以后类推..
A2总的死亡概率是一个等比数列求和。套用公式算一下就是P1/(1-(1-P1)*(1-P2))
为方便起见，用 State(P,n,i)表示一个系统的状态。
P是每个人命中率的集合，n,表示人数，i,表示第几个人先射。
当有n个人，第i个人先射击时，如果他没射中，整个系统状态过渡到
State(P,n,Next(i) );
如果他选择第j个人，并射中了，系统状态过渡到
State((P - Pj),n-1,Next(i));
所以，第i个人先射击时，他会在所有
State((P - Pj),n-1,Next(i)); j=1 to n-1,j != i
的状态中，选择一个他生存概率最大的状态的j,射击第j个人.
j = Strategy(p,n,i)
现在来计算State(P,n,i)下某一个人的生存概率。
计算方法其实是和引理1类似的。
为此，先按照上面的方法，计算出每个人的策略。
而这个策略成功的概率是他在第一轮中成功的概率 * 1/（1 - M(1-Pi))
（其中M表示连乘符号，i从1变到n,一轮射击是指从第一个开始射击的人起，每个人都射击一次。
实际上1/（1 - M(1-Pi))可以看作一个归一化因子。）
计算出每个人的策略成功概率，我们可以说：
处在State(P,n,i)状态的系统，
有P1的概率过渡到状态 State( { P-P[Strategy(p,n,1)]}, n-1, Next(1) ),
有(1-P1)*P2的概率过渡到状态 State( { P-P[Strategy(p,n,2)]}, n-1, Next(2) ),
...
显然，状态State(P,n,i)下某个人生存的概率
= E（第j个人的策略成功后的状态下这个人生存的概率 * 第j个人的策略成功的概率）; j= 1 to n
至此，已经可以写程序了。程序代码如下：
（到8个人时就已经很慢了。时间紧迫，没办法，各位看看能不能改成个动态规划的什么的：）
2、对可以放空枪的情况，如果一个人放空枪，那么系统状态变为
State(P,n,Next(i) )；即人数不变，第二个人先射时的状态。
考虑第二个人的策略时，他还是有放空枪的选择，故又要计算第二个人先射时的状态...
这样总人数没有减少，递归就找不到出口了。
我也不知道怎么做了，穷举？证明？大家都来想想啊，争取把这个难题完整解决掉！
问题点数：100、回复次数：18Top
1 楼BlueSky2008（懒惰是程序员的美德）回复于 2003-09-04 19:57:15 得分 0
//程序
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
struct state{
short s;
char num;
char first;
};
double accuracy[10];
int max_num;
inline state remove(state s,int i)
{
s.s &= ~(0x01<<i);
s.num--;
return s;
}
inline state restore(state& s,int i)
{
s.s |= 0x01<<i;
s.num++;
return s;
}
inline int next(state s,int current)
{
while(1){
++current;
if(current > 10) current =1;
if(s.s & (0x01<<current) )
return current;
};
}
double Cal_alive(state s, int id);
//当前状态下先射的人的策略
int Strategy(state s)
{
int shoot;//返回值，射谁
if(s.num==2)
{
shoot = next(s,s.first);
}
else
{
double max_alive = 0.0;
double alive;
int current = next(s,s.first);
state ss;
do{
ss = remove(s,current);
ss.first = next(ss,s.first);
alive = Cal_alive(ss, s.first);
if(alive > max_alive){
max_alive = alive;
shoot = current;
}
current = next(s,current);
}while(current != s.first);
}
return shoot;
}
//计算当前状态下某人的生存概率
double Cal_alive(state s, int id)
{
double dead;
double alive = 0.0;
double occur=1.0;
int shoot;
state ss;
if(s.num == 2)
{
double P1 = accuracy[s.first];
double P2 = accuracy[next(s,s.first)];
alive = P1/(1-(1-P1)*(1-P2));
if(id == s.first)
return alive;
else
return 1.0 - alive;
}
for(int i = 0;i<s.num;i++)
{
shoot = Strategy(s);
if(shoot != id){
dead = occur * accuracy[s.first];
occur *= 1.0 - accuracy[s.first];
ss = remove(s,shoot);
ss.first = next(ss,s.first);
alive += Cal_alive(ss, id) * dead;
}
s.first = next(s,s.first);
}
alive /= (1 - occur);
return alive;
}
main()
{
state s;
int i;
for(i = 1; i<=10; i++){
accuracy[i] = i/10.0;
}
cout<<"Input: How many people?";
cin>>max_num;
if(max_num>10)
{
cout<<"too big. I use 7 as default";
max_num =7;
}
for(int num = 2;num <max_num;num++)
{
s.num=num;
s.s = (0x01<<(num+1) )-1;
for(int first = 1;first<= num;first++)
{
s.first =first;
printf("%d person, %d first, he want to kill %d \n",
num,first,Strategy(s));
}
}
return 0;
}
Top
2 楼WYlslrt（WY.lslrt(http://www.wyos.net)）回复于 2003-09-05 11:44:59 得分 10
不知你发此贴干吗
呵呵。
不过这种精神值得赞扬。
upTop
3 楼warton（创业群13734424 http://www.anywhy.cn）回复于 2003-09-05 13:02:57 得分 10
好，支持！！！Top
4 楼iicup（双杯献酒）回复于 2003-09-05 14:09:26 得分 20
假设最后剩下3个:
A8 A9 A10
任何一个都不愿意打死其中一个，
而面对另一个高达80%以上的攻击。
所以必然是不了之局。Top
5 楼HUNTON（追求完美）回复于 2003-09-05 17:35:46 得分 10
看到这么多的文字就头晕了。Top
6 楼hqulyc（（vc++++++++...死循环了））回复于 2003-09-18 22:49:25 得分 0
头晕，，，每个人开枪时要杀哪个人都是任意的，怎么算！！！，这样还能算出生存的概率，佩服！·~Top
7 楼stillwater123（南楠）回复于 2003-09-19 12:37:52 得分 0
没等算完了，就玩完了Top
8 楼stillwater123（南楠）回复于 2003-09-19 13:03:48 得分 10
好，好象看明白了，偶帮你改改，
偶想把它作成个智力游戏，可以是网络版的，
有想法的可以加我撒 qq：34631358Top
9 楼BlueSky2008（懒惰是程序员的美德）回复于 2003-09-19 20:37:49 得分 0
总的思想就是：
每个人选择一个人，使得他打死这个人后，他的生存概率比他打死其他人后生存概率都大。
一个状态下，某个人a的生存概率，是每个人的策略成功后，（a的生存概率 乘以 这个人的策略成功的概率） 求和。
现在就是放空枪的问题。
iicup(双杯献酒)说的那种情况是完全可能的。现在要解决的就是何时会产生循环，怎样确定循环。
stillwater123(南楠) ：
作成个智力游戏后，别忘了让我先玩玩啊：）Top
10 楼xmmmj（可笑）回复于 2003-09-22 00:29:50 得分 10
关键是求射击的策略Strategy(p,n,i)
只能递归，求Strategy(p,n,i) 必须知道所有的Strategy(p－1,n－1,所有的i)
只能从任意两个人开始计算，然后构造出所有的Strategy(p,n,i)Top
11 楼xmmmj（可笑）回复于 2003-09-22 00:30:53 得分 0
允许放空枪也是一样的Top
12 楼stillwater123（南楠）回复于 2003-09-22 03:33:12 得分 0
BlueSky2008() 一定一定！饮水思源嘛~Top
13 楼SnHnBn（大可达）回复于 2003-09-22 10:49:58 得分 30
楼主，关于 iicup(双杯献酒) 说的情况，我有另一种意见：
假设，他们都不开枪，则得到钻石的机会是0。而问题是要求得到钻石的概率最大，而且不要忘记这些强盗都是不怕死的（否则就不会用这种方式解决问题了）。
另外，题目只是求概率，剩下A8, A9, A10的概率恐怕太低了，这几个家伙是最容易完蛋的几个。开始的时候，大家肯定先攻击A10，然后是A9，然后是A8。第一轮攻击中，A10存活的几率是0.9x0.8x0.7x...x0.1。
当然，如果iicup(双杯献酒) 说的情况会出现，那么一定是开枪者考虑到在剩下的人数中，如果他射杀某个人之后，他被下一个开枪者选中的机会x开枪者的命中率（=射杀之后的死亡概率）要比当前它放空枪，由下一个人开枪的死亡几率要大，那么它就会放空枪。所以放空枪的条件是根据 被下一个开枪者选中的机会x开枪者的命中率 来判断，本来剩下的人数越多，那么被下一个开枪者选中的机会越小。但是，似乎命中率高的应该成为被射杀的目标。
因此判断条件就变成要考虑到自己是否属于剩下的人中命中率最高的。
仅仅从上述条件考虑，A10一定不会放空枪，所以第一轮中如果他不死一定会把A9先干掉，所以A10、A9、A8存活的情况一定不会出现。因此，第一轮射击中，A10和A9必定有一人被杀死。
***因为命中率高的总是成为大家射击的目标，因此每杀一个人之后，下一个死的必定是剩下的命中率最高的两人之一。****
所以，如果最后剩下两个人，其中一个必定是A1。剩下的事情就好办了，可以递归计算另一个人的生存概率和导致当前命中率最高的人的死亡概率，因为A10总是可以计算的，所以递归总会完成。
以上的推论全部基于“命中率高的总是成为大家射击的目标”这一假设，是否成立？有人能够证明吗？
Top
14 楼shu_shu（）回复于 2003-09-22 11:54:45 得分 0
gzTop
15 楼BlueSky2008（懒惰是程序员的美德）回复于 2003-09-22 13:14:46 得分 0
to SnHnBn(大可达):
"他们都不开枪，则得到钻石的机会是0"
如果你从另一个角度考虑：“最终有人得到钻石”的概率是1，
也就是每个人得到钻石的概率相加： P1+P2+...+Pn = 1
“命中率高的总是成为大家射击的目标”这一假设，不能成立。
eg:3人命中率：A:0.1, B:0.9, C:1.0
策略可能是 A放空枪,B射C，C射B
Top
16 楼SnHnBn（大可达）回复于 2003-09-22 16:56:57 得分 0
关于第一点，都放空枪的话，永远不会发产生“有人得到钻石”这个状态。先抛开程序不谈，如果现实情况，楼主你认为这种情况可能吗？
第二点，没有违背我说的情况，A是考虑到了它的生存情况，如果他要射击的话，他肯定会选C而不是B，没有违背“命中率高的总是成为大家射击的目标”这一假设。而B一定会射C，C也一定会射B。因此最后还是“如果最后剩下两个人，其中一个必定是A1”的情况。Top
17 楼SnHnBn（大可达）回复于 2003-09-22 17:27:49 得分 0
说完上面的话，感觉答案可能更靠近了：A为什么放空枪呢？因为它若射杀了C的话，他将成为命中率最高的两个人之一，这时候他就要考虑放空枪和不放空枪的两种生存概率。
至于第一点，要么不可能发生，若是发生了也可以在程序中很容易的排除和检测：一轮射击，若所有人都放了空枪，则将该轮得到钻石的概率设为0，若是求生存概率则设为1，不过该题不是求生存概率。Top
18 楼SnHnBn（大可达）回复于 2003-09-22 17:55:08 得分 0
话说回来，若是不用递归方式做，问题就统统解决了——用广度搜索法。Top
