i*****d
发帖数: 962 | 1 一个NxN的matrix，每个cell里面存的是integer, 0到k之间，这个matrix的每行每列的
和都等于k（k是odd），现在要从matrix里面选出一些cell，满足以下条件：
1. 如果一个cell的值是c （0
示该cell不可选；若c=1则表示该cell只能被选一次。
1. 每行必须选中两次（两个不同的cell各选一次，或者同一个cell选两次）。
2. 每列必须选中两次（两个不同的cell各选一次，或者同一个cell选两次）。
图中的例子圈着的是两个例子（k=3）的solution，一个圈代表选了一次，两个圈代表
选了两次。这个最优的解法是什么？ |
i*****d
发帖数: 962 | 2
【在 i*****d 的大作中提到】
: 一个NxN的matrix，每个cell里面存的是integer, 0到k之间，这个matrix的每行每列的
: 和都等于k（k是odd），现在要从matrix里面选出一些cell，满足以下条件：
: 1. 如果一个cell的值是c （0: 示该cell不可选；若c=1则表示该cell只能被选一次。
: 1. 每行必须选中两次（两个不同的cell各选一次，或者同一个cell选两次）。
: 2. 每列必须选中两次（两个不同的cell各选一次，或者同一个cell选两次）。
: 图中的例子圈着的是两个例子（k=3）的solution，一个圈代表选了一次，两个圈代表
: 选了两次。这个最优的解法是什么？
|
z*****6
发帖数: 16 | 3 正路看著像back tracking的題，只有不斷遍歷找解，類似於soduku的變種。 |
i*****d
发帖数: 962 | 4
不断遍历的话这个时间复杂度是不是就挺高的了？
【在 z*****6 的大作中提到】
: 正路看著像back tracking的題，只有不斷遍歷找解，類似於soduku的變種。
|
s**********g
发帖数: 14942 | 5 backtrack的复杂度向来都高
指数级不是梦
【在 i*****d 的大作中提到】
:
: 不断遍历的话这个时间复杂度是不是就挺高的了？
|
i*****d
发帖数: 962 | 6
嗯...那不知道这个有没有更优的解法呢。
【在 s**********g 的大作中提到】
: backtrack的复杂度向来都高
: 指数级不是梦
|
s**********g
发帖数: 14942 | 7 表面上看 的确是backtrack的长相啊。。
【在 i*****d 的大作中提到】
:
: 嗯...那不知道这个有没有更优的解法呢。
|
N******G
发帖数: 33 | 8 网络流吧，建立源点S，汇点T
每个行一个点Xi，每个列一个点Yj
S->Xi capacity=2
Yj->T capacity=2
Xi->Yj capacity=min(2,cell_ij's value)
Has solution if and only if max flow (2N) is reached |
z*****6
发帖数: 16 | 9 優化在於如何剪枝，把不合適的剪掉或只遍歷可能的combination。不過坐等看有沒有
其他更優解法。
：不断遍历的话这个时间复杂度是不是就挺高的了？
【在 i*****d 的大作中提到】
:
: 嗯...那不知道这个有没有更优的解法呢。
|
c********t
发帖数: 5706 | 10 是要找出所有的选法吗？
【在 i*****d 的大作中提到】
: 一个NxN的matrix，每个cell里面存的是integer, 0到k之间，这个matrix的每行每列的
: 和都等于k（k是odd），现在要从matrix里面选出一些cell，满足以下条件：
: 1. 如果一个cell的值是c （0: 示该cell不可选；若c=1则表示该cell只能被选一次。
: 1. 每行必须选中两次（两个不同的cell各选一次，或者同一个cell选两次）。
: 2. 每列必须选中两次（两个不同的cell各选一次，或者同一个cell选两次）。
: 图中的例子圈着的是两个例子（k=3）的solution，一个圈代表选了一次，两个圈代表
: 选了两次。这个最优的解法是什么？
|
|
|
l****u
发帖数: 1764 | 11 这是一个operations research的问题吧，用integer programming 解：
Maximize/minimize： sum(Xij)
Subject to:
sum(Xij, i=1..n) == 2, for each j in 1..m
sum(Xij, j=1..m) == 2, for each i in 1..n
Xij <= Cij for all i, j
Objective function不重要，找到feasible solution就行了 |
i*****d
发帖数: 962 | 12
只需要找出一个就好了
【在 c********t 的大作中提到】
: 是要找出所有的选法吗？
|
i*****d
发帖数: 962 | 13
嗯，谢谢。网络流算是其中一个解法，想看看还有没有其他的更优的
【在 N******G 的大作中提到】
: 网络流吧，建立源点S，汇点T
: 每个行一个点Xi，每个列一个点Yj
: S->Xi capacity=2
: Yj->T capacity=2
: Xi->Yj capacity=min(2,cell_ij's value)
: Has solution if and only if max flow (2N) is reached
|
i*****d
发帖数: 962 | 14
不大懂integer programming...搜了一下有可能是NP-Hard?
【在 l****u 的大作中提到】
: 这是一个operations research的问题吧，用integer programming 解：
: Maximize/minimize： sum(Xij)
: Subject to:
: sum(Xij, i=1..n) == 2, for each j in 1..m
: sum(Xij, j=1..m) == 2, for each i in 1..n
: Xij <= Cij for all i, j
: Objective function不重要，找到feasible solution就行了
|
l****u
发帖数: 1764 | 15 那是求最优解。这个题目求个可行解就行了，可以relax成linear programming，然后
再round up/down，应该可以比较快解出来（polynomial）
：不大懂integer programming...搜了一下有可能是NP-Hard?
【在 i*****d 的大作中提到】
:
: 不大懂integer programming...搜了一下有可能是NP-Hard?
|
b***s
发帖数: 117 | |
z*****6
发帖数: 16 | 17 题目要求最优解……
：那是求最优解。这个题目求个可行解就行了，可以relax成linear programming，然后
：再round up/down，应该可以比较快解出来（polynomial）
【在 l****u 的大作中提到】
: 那是求最优解。这个题目求个可行解就行了，可以relax成linear programming，然后
: 再round up/down，应该可以比较快解出来（polynomial）
:
: ：不大懂integer programming...搜了一下有可能是NP-Hard?
|
l****u
发帖数: 1764 | 18 题目没要求最优解。。。
都没有objective function，怎么最优。。
然后
【在 z*****6 的大作中提到】
: 题目要求最优解……
:
: ：那是求最优解。这个题目求个可行解就行了，可以relax成linear programming，然后
: ：再round up/down，应该可以比较快解出来（polynomial）
|
i*****d
发帖数: 962 | 19 回楼上两位，最优只是说时间上最优，因为有很多种选择，选中其中一个符合条件的就
ok了。但是不知道ILP能优化到什么复杂度啊 |
