一个掘金游戏的最值求解

peter1977

各位好，

问题如下说明：
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

遗传算法。

KeyTo9_Fans

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

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

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

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

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

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

peter1977

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

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

peter1977

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

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

谢谢！

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

感谢！

aimisiyou

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

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

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

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

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

aimisiyou

你可以先看看遗传算法的相关内容，很好理解，只是参数设置需凭经验，运行效率不高，还容易陷入局部最优解。