peter1977 发表于 2018-6-4 20:15:41

一个掘金游戏的最值求解

各位好,

问题如下说明:
1-10为10个人,每两个人组成一对掘金,每对都能掘得一定数量的金子。每个人和其他人组合可得到的一定的金子数(金子数1-5内的整数随机分配)。下表中每一行、列都代表某人和其他人组合时能得到的金子数。

人   1         2         3      4      5         6            7            8            9          10
1    0         随机   随机   随机    随机   随机       随机       随机      随机       随机
2    随机   0       随机   随机    随机   随机       随机       随机      随机       随机
3    随机   随机   0       随机    随机   随机       随机       随机      随机       随机
4    随机   随机   随机   0      随机   随机       随机       随机      随机       随机
5    随机   随机   随机   随机    0         随机       随机       随机      随机       随机
6    随机   随机   随机   随机    随机   0         随机       随机      随机       随机
7    随机   随机   随机   随机    随机   随机       0         随机      随机       随机
8    随机   随机   随机   随机    随机   随机      随机       0             随机       随机
9    随机   随机   随机   随机    随机   随机      随机       随机         0         随机
10随机   随机   随机   随机    随机   随机      随机       随机         随机       0

规则:
A,按1-10的顺序逐次进行组合选择,第一个(1)选择的可以任选剩余9人中的一个,且必须选择一名伙伴,第二个可以任选剩余7人中的一个,且必须选择一名伙伴。。。。。。以此类推,直到全部成对组合(5对);
B,每次只能1对1组合;

问题:
那种组合方案(5对各自如何组合)可以得到最少或最多的金子?

要求:
A,,不使用穷举法,10人只是例子,人数可设为N,偶数;
B,给出具体的算法。

补充说明:
这个问题,可能存在歧义,我再说详细一些:
1-10个号码,按1-10的顺序选择伙伴组合,比如1可以选2-9内任一个,比如选了2,则1-2为一个组合,可以得到一定的金子,金子数量我们可以任意指定为G1,
接下来,第二对选择,由于2已经被1选中,则从3开始(如果1没选2,则从2开始),此时剩余为4,5,6,7,8,9,10.。。。。。。。。。。假如3选了5,则3-5组合得到金子数为G2;
同理,第三对开始选择,从4开始,....................................................................................G3, 接下来,G4, G5,   ............................直到所有人组合成功。
其中,G1-G5的值(一个人和其他一人组合的到的金数)我们可以任意随机指定,这个在于探讨算法,而不是具体的值。
最后的最值的问题是在所有可能的组合中找到MAX或min(G1+G2+......G5)

有一点需特别提醒,当先选者选择后面的人时,在满足自己最大的同时,可能消除了后面被选的人得到更多金子的机会(也就是说,如果被选的没有被选中,这个人可能有一个得到更多金子的组合)

aimisiyou 发表于 2018-6-4 22:04:50

遗传算法。

KeyTo9_Fans 发表于 2018-6-4 22:11:03

在百度数学吧找到一张贴子:

http://tieba.baidu.com/p/1166414706

有人回复了一个链接,可惜打不开。

根据回贴的内容,去百度学术上搜索Gabow和Tajan的算法,可以找到这篇文献:

https://core.ac.uk/download/pdf/54846440.pdf

但这篇论文比较长,我简单快速地扫了一遍,初步断定他们的算法是可以解决楼主的问题的。

peter1977 发表于 2018-6-5 09:15:21

aimisiyou 发表于 2018-6-4 22:04
遗传算法。

能说细一点吗?如何建模?

peter1977 发表于 2018-6-5 09:17:22

KeyTo9_Fans 发表于 2018-6-4 22:11
在百度数学吧找到一张贴子:

http://tieba.baidu.com/p/1166414706


谢谢!

资料已经下完,正在看,但以我的能力,要领悟可能得至少2个礼拜了。。。。。。
能麻烦您简要说一下这个算法,给我一个简单的模型吗?

感谢!

aimisiyou 发表于 2018-6-5 09:51:25

peter1977 发表于 2018-6-5 09:15
能说细一点吗?如何建模?

随机生成2N(设定种群容量2N)个1-10的排列,如其中一个个体(3 7 2 4 5 8 10 9 1 6),求得每个个体的对应值,保存最优个体pbest1,根据归一化的结果做为下一代中此个体出现的概率进行选择、交叉(设定交叉概率p)、变异(设定变异概率q)生成下一代2N个个体,求出下一代最优个体pbest2,若pbest2优于pbest1则替换,否则保留pbest1;循环遗传下去(设定遗传代数M)……。

peter1977 发表于 2018-6-5 14:29:02

aimisiyou 发表于 2018-6-5 09:51
随机生成2N(设定种群容量2N)个1-10的排列,如其中一个个体(3 7 2 4 5 8 10 9 1 6),求得每个个体的 ...

个体(3 7 2 4 5 8 10 9 1 6)对应值是什么?如何求出?

原题的意思是,按1-10的顺序选择配对组合,每两个配对后可得到一定的金数,从1开始往下选择配对,本题是共选5对,但这5对有不同的可能性,比如说1为第一个选的,9种可能性,同时,得金数也因配对组合的人不同而变化,对1来说,选2或3或4......或9的得金数是不同的。。。。。。,以下类似,第二个选的有7种可能性。。。。
最后的问题是,求这10个人(也就是这5对一共)在那种配对组合下得金数的最大最小值。
本题的随机,是先随机赋予一定的值后,求最值,没有分别指定是想求得更通用的算法。

我不太明白您的意思?

aimisiyou 发表于 2018-6-5 14:55:24

peter1977 发表于 2018-6-5 14:29
个体(3 7 2 4 5 8 10 9 1 6)对应值是什么?如何求出?

原题的意思是,按1-10的顺序选择配对组合,每 ...

个体的对应值就是个体中第一位和第二位配对,第三位和第四位配对……,如个体(3 7 2 4 5 8 10 9 1 6)的对应值就是V(3-7)+V(2-4)+V(5-8)+V(10-9)+V(1-6)所得的金币数。

peter1977 发表于 2018-6-5 16:15:55

aimisiyou 发表于 2018-6-5 14:55
个体的对应值就是个体中第一位和第二位配对,第三位和第四位配对……,如个体(3 7 2 4 5 8 10 9 1 6) ...

这个算法,接下去N的大小如何选择,M如何选,还有适应度函数是什么?
抱歉,我对遗传算法只能说是了解皮毛。。。。。:L

aimisiyou 发表于 2018-6-5 16:26:59

你可以先看看遗传算法的相关内容,很好理解,只是参数设置需凭经验,运行效率不高,还容易陷入局部最优解。
页: [1] 2
查看完整版本: 一个掘金游戏的最值求解