请教一道算法题，各位大牛麻烦指导指导 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道算法题，各位大牛麻烦指导指导

请教一道算法题，各位大牛麻烦指导指导# JobHunting - 待字闺中

i*d2016-11-07 08:11

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*d2016-11-07 08:11

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*62016-11-07 08:11

3 楼

正路看著像back tracking的題，只有不斷遍歷找解，類似於soduku的變種。

i*d2016-11-07 08:11

4 楼

不断遍历的话这个时间复杂度是不是就挺高的了？

【在 z*****6 的大作中提到】

: 正路看著像back tracking的題，只有不斷遍歷找解，類似於soduku的變種。

s*g2016-11-07 08:11

5 楼

backtrack的复杂度向来都高
指数级不是梦

【在 i*****d 的大作中提到】

:
: 不断遍历的话这个时间复杂度是不是就挺高的了？

i*d2016-11-07 08:11

6 楼

嗯...那不知道这个有没有更优的解法呢。

【在 s**********g 的大作中提到】

: backtrack的复杂度向来都高
: 指数级不是梦

s*g2016-11-07 08:11

7 楼

表面上看的确是backtrack的长相啊。。

【在 i*****d 的大作中提到】

:
: 嗯...那不知道这个有没有更优的解法呢。

N*G2016-11-07 08:11

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*62016-11-07 08:11

9 楼

優化在於如何剪枝，把不合適的剪掉或只遍歷可能的combination。不過坐等看有沒有
其他更優解法。

：不断遍历的话这个时间复杂度是不是就挺高的了？

【在 i*****d 的大作中提到】

:
: 嗯...那不知道这个有没有更优的解法呢。

c*t2016-11-07 08:11

10 楼

是要找出所有的选法吗？

【在 i*****d 的大作中提到】

l*u2016-11-07 08:11

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*d2016-11-07 08:11

12 楼

只需要找出一个就好了

【在 c********t 的大作中提到】

: 是要找出所有的选法吗？

i*d2016-11-07 08:11

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*d2016-11-07 08:11

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*u2016-11-07 08:11

15 楼

那是求最优解。这个题目求个可行解就行了，可以relax成linear programming，然后
再round up/down，应该可以比较快解出来（polynomial）

：不大懂integer programming...搜了一下有可能是NP-Hard?

【在 i*****d 的大作中提到】

:
: 不大懂integer programming...搜了一下有可能是NP-Hard?

b*s2016-11-07 08:11

16 楼

感觉有点象8皇后

z*62016-11-07 08:11

17 楼

题目要求最优解……

：那是求最优解。这个题目求个可行解就行了，可以relax成linear programming，然后
：再round up/down，应该可以比较快解出来（polynomial）

【在 l****u 的大作中提到】

: 那是求最优解。这个题目求个可行解就行了，可以relax成linear programming，然后
: 再round up/down，应该可以比较快解出来（polynomial）
:
: ：不大懂integer programming...搜了一下有可能是NP-Hard?

l*u2016-11-07 08:11

18 楼

题目没要求最优解。。。
都没有objective function，怎么最优。。

然后

【在 z*****6 的大作中提到】

: 题目要求最优解……
:
: ：那是求最优解。这个题目求个可行解就行了，可以relax成linear programming，然后
: ：再round up/down，应该可以比较快解出来（polynomial）

i*d2016-11-07 08:11

19 楼

回楼上两位，最优只是说时间上最优，因为有很多种选择，选中其中一个符合条件的就
ok了。但是不知道ILP能优化到什么复杂度啊