o****i
发帖数: 142 | 1 我知道怎么做两组的：比如一组A有2个成员：A1，A2； 另一组B有3个成员：B1，B2，
B3
对A组的每个成员，要从B组找一个成员组成一对 (without replacement),最后要求这
两对的总距离最短。这个问题可以用 netflow 来解决。使用SAS PROC ASSIGN 能找到
符合要求的配对。
我现在的问题是多组（>2)，比如还有一组C，有4个成员。要为A组的两个成员在B和C里
分别找一个，共组成两"对"。比如 A1-B2-C2 和 A2-B3-C1。 要使这两对的距离之和最
小。注意，其中每一"对"的距离是指 A-B, A-C, and B-C 距离之和.
我觉得应该有现成的理论和算法能解决这个问题。请知道的指点一下如何做，最好能指
明如何用SAS 做。或者指出参考文献也行。多谢！ | l******e
发帖数: 470 | 2 这个叫3-dimentional matching
这个问题NPC,没有有效方法解
或者你找个integer programming solver 来解，数据不多应该够用了。
【在 o****i 的大作中提到】
: 我知道怎么做两组的：比如一组A有2个成员：A1，A2； 另一组B有3个成员：B1，B2，
: B3
: 对A组的每个成员，要从B组找一个成员组成一对 (without replacement),最后要求这
: 两对的总距离最短。这个问题可以用 netflow 来解决。使用SAS PROC ASSIGN 能找到
: 符合要求的配对。
: 我现在的问题是多组（>2)，比如还有一组C，有4个成员。要为A组的两个成员在B和C里
: 分别找一个，共组成两"对"。比如 A1-B2-C2 和 A2-B3-C1。 要使这两对的距离之和最
: 小。注意，其中每一"对"的距离是指 A-B, A-C, and B-C 距离之和.
: 我觉得应该有现成的理论和算法能解决这个问题。请知道的指点一下如何做，最好能指
: 明如何用SAS 做。或者指出参考文献也行。多谢！
| o****i
发帖数: 142 | 3 多谢 lapordge。我的数据从几百到几千，有时上万。不知算不算大？有时需做 4-
dimentional matching. 需要找到相应的配对。
能否推荐个具体的软件或算法来做？
多谢！
另外，啥是 NPC 啊？
没有有效方法解没关系，能permutation 也行啊。
【在 l******e 的大作中提到】
: 这个叫3-dimentional matching
: 这个问题NPC,没有有效方法解
: 或者你找个integer programming solver 来解，数据不多应该够用了。
| l******e
发帖数: 470 | 4 几万肯定算大，几千都不知道
我前面说的integer program你稍微看看
比如3-d matching,你可以设变量 x_{ijk}=1就是{i,j,k}配到一起了
x_{ijk}=0就是没配到一起
可以解integer program的软件很多，你搜搜吧
商用的速度快，免费的也可以凑合用
啥叫permutation？
【在 o****i 的大作中提到】
: 多谢 lapordge。我的数据从几百到几千，有时上万。不知算不算大？有时需做 4-
: dimentional matching. 需要找到相应的配对。
: 能否推荐个具体的软件或算法来做？
: 多谢！
: 另外，啥是 NPC 啊？
: 没有有效方法解没关系，能permutation 也行啊。
| o****i
发帖数: 142 | 5 分你一半财产 （10个包子）。多谢回答问题。
查了下 integer program, 还是没搞明白怎么处理这个问题。能否再解释清楚些？
比如：
A组：a1=6,a2=7
B组：b1=3,b2=4,b3=6
C组：c1=4,c2=7,c3=8
最短距离组合应该是：(a1,b2,c1),(a2,b3,c2)。即，(6,4,4), (7,6,7).
我的问题就是怎么把这两“对”找出来。我要知道具体的配对，而不是最短距离 （6）。
Permutation 是一种笨办法，去试各种可能性的组合，再找个最小的。数据小还好，数
据大就完蛋了。所以我想应该有好的算法解决这个问题。
【在 l******e 的大作中提到】
: 几万肯定算大，几千都不知道
: 我前面说的integer program你稍微看看
: 比如3-d matching,你可以设变量 x_{ijk}=1就是{i,j,k}配到一起了
: x_{ijk}=0就是没配到一起
: 可以解integer program的软件很多，你搜搜吧
: 商用的速度快，免费的也可以凑合用
: 啥叫permutation？
| D******r
发帖数: 25 | 6 seti={a1,a2}
setj={b1,b2,b3}
setk={c1,c2,c3}
C_ijk=i,j,k配对的距离
x_ijk=1 当i,j,k配对 =0 otherwise
min sum{i in seti}{j in setj}{k in setk}C_ijk*x_ijk
s.t. sum{i in seti}{j in setj}{k in setk}x_ijk=2
x_ijk 是integer所以是integer programming
）。
【在 o****i 的大作中提到】
: 分你一半财产 （10个包子）。多谢回答问题。
: 查了下 integer program, 还是没搞明白怎么处理这个问题。能否再解释清楚些？
: 比如：
: A组：a1=6,a2=7
: B组：b1=3,b2=4,b3=6
: C组：c1=4,c2=7,c3=8
: 最短距离组合应该是：(a1,b2,c1),(a2,b3,c2)。即，(6,4,4), (7,6,7).
: 我的问题就是怎么把这两“对”找出来。我要知道具体的配对，而不是最短距离 （6）。
: Permutation 是一种笨办法，去试各种可能性的组合，再找个最小的。数据小还好，数
: 据大就完蛋了。所以我想应该有好的算法解决这个问题。
| o****i
发帖数: 142 | 7 多谢 Dejeuner！我感觉是懂了，还要找软件试。
剩下的伪币也转给你了。
（我还有马甲他妈、马甲他妈的马甲，伪币还有 ：）
【在 D******r 的大作中提到】
: seti={a1,a2}
: setj={b1,b2,b3}
: setk={c1,c2,c3}
: C_ijk=i,j,k配对的距离
: x_ijk=1 当i,j,k配对 =0 otherwise
: min sum{i in seti}{j in setj}{k in setk}C_ijk*x_ijk
: s.t. sum{i in seti}{j in setj}{k in setk}x_ijk=2
: x_ijk 是integer所以是integer programming
:
: ）。
|
|
