一个掘金游戏的最值求解
各位好，问题如下说明：
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)
有一点需特别提醒，当先选者选择后面的人时，在满足自己最大的同时，可能消除了后面被选的人得到更多金子的机会（也就是说，如果被选的没有被选中，这个人可能有一个得到更多金子的组合） 遗传算法。 在百度数学吧找到一张贴子：
http://tieba.baidu.com/p/1166414706
有人回复了一个链接，可惜打不开。
根据回贴的内容，去百度学术上搜索Gabow和Tajan的算法，可以找到这篇文献：
https://core.ac.uk/download/pdf/54846440.pdf
但这篇论文比较长，我简单快速地扫了一遍，初步断定他们的算法是可以解决楼主的问题的。 aimisiyou 发表于 2018-6-4 22:04
遗传算法。
能说细一点吗？如何建模？ KeyTo9_Fans 发表于 2018-6-4 22:11
在百度数学吧找到一张贴子：
http://tieba.baidu.com/p/1166414706
谢谢！
资料已经下完，正在看，但以我的能力，要领悟可能得至少2个礼拜了。。。。。。
能麻烦您简要说一下这个算法，给我一个简单的模型吗？
感谢！ 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）……。 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对一共）在那种配对组合下得金数的最大最小值。
本题的随机，是先随机赋予一定的值后，求最值，没有分别指定是想求得更通用的算法。
我不太明白您的意思？ 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）所得的金币数。 aimisiyou 发表于 2018-6-5 14:55
个体的对应值就是个体中第一位和第二位配对，第三位和第四位配对……，如个体（3 7 2 4 5 8 10 9 1 6） ...
这个算法，接下去N的大小如何选择，M如何选，还有适应度函数是什么？
抱歉，我对遗传算法只能说是了解皮毛。。。。。:L 你可以先看看遗传算法的相关内容，很好理解，只是参数设置需凭经验，运行效率不高，还容易陷入局部最优解。
页:
[1]
2