作者FRAXIS (喔喔)
看板Prob_Solve
标题Re: [问题] 人生成就问题
时间Wed Apr 21 09:37:44 2010
※ 引述《ECZEMA (加油!)》之铭言：
: (我知道如果只考虑小学 国中，是 bipartite matching 或说是 指派问题，因为没有
: 提供两个阶段的人生成就分数，不能用 bipartite matching 两阶段两阶段串联来解，
: 人生成就分数只有四个阶段一起考虑才有)
: 若各阶段学校数目为 1000 所时，还能用吗? 告诉我可以参考哪一种演算法就好了…
: 给我几个明确的关键字…谢谢大家… 希望听到 「这不就是典型的 _____ 问题吗？」
: XD
把图建成4分图，就是分成小学、国中、高中、大学四部分，同一部分之中互不相连。
然後加上一个s点连向小学，大学连向t点。
要找出5个人都没有当过同学，就等於是判断这个图是不是5-vectex-connected。
利用Network Flow算法就可以判断了。
但是现在还有一个目标函数，是希望人生成就的总和最高。如果人生成就
可以只要看两个阶段之间，那麽只要把边加上权重，用Minimum Cost Maximum Flow
演算法来解，我想应该就可以找到解答了。
但是现在人生成就却需要4个阶段一起考量，我就不知道该怎麽用Network Flow了。
这个问题可以用数学规划表示成这样
Objective function: Σ f(x, y, z, w)
f是人生成就的函数
Constraints: 总共有m个人，针对第i个人有xi, yi, zi, wi四个变数
xi, yi, zi, wi 是 1 ~ n 之间的整数，n是学校数目
且对於i != j, xi != xj, yi != yj, zi != zj, wi != wj
本问题本身就是Interger Programming，如果f函数有特殊性质，像是Convex，
那应该可以用Convex Optimization的技巧来寻找解答。
当然，如果f有更强烈的性质可以使用，可能就不用那麽麻烦了..
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：推 ECZEMA:你得到我了! 如果可以知道两点连线间的权重且线性可加，我 04/21 11:42
2F：→ ECZEMA:找得到类似题，但人生成就分数是统计多个同样升学管道学生 04/21 11:43
3F：→ ECZEMA:所决定的 我就卡关了…可是 flow 的例子又很像这题目 04/21 11:47
4F：→ ECZEMA:如果 分数可以用 函数 f(x,y,z,w) 拟合出来，就又变成要讨 04/21 11:57
5F：→ ECZEMA:论不同函数问题有没有精确解… 我先去了解一下 convex... 04/21 12:00
6F：推 ECZEMA:ILP 这关键字很有用耶! 不过看到是 NP-hard 心凉了一半~ 04/21 12:23
7F：→ FRAXIS:就算是NP-Hard还是可以解 只是看速度够不够而已.. 04/21 12:51
8F：→ FRAXIS:不然你就把f换成一个比较容易算的函数.. 找近似 04/21 12:51