a***a
发帖数: 149 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: tidybear (tidybear1), 信区: JobHunting
标 题: 算法问题
发信站: BBS 未名空间站 (Fri May 2 17:25:14 2008)
一个图，node有三种状态,0,1,-1,每个边有weight，现在找到状态为0的node，把它转
化为1或者-1，使得该图所有weight的总和最大。每条边weight=node1状态*node2状态*
weight。是不是贪婪算法？多谢. |
m********7
发帖数: 37 | |
m********7
发帖数: 37 | 3 No, greedy algorithm does not work.
As it exhibits the sub-structure property, you can use dynamic programming
technique to solve it in O(m) time, where m is the number of edges.
Give me email and I can send you the solution. |
h*******e
发帖数: 225 | 4 h*******[email protected]. Thanks!
【在 m********7 的大作中提到】
: No, greedy algorithm does not work.
: As it exhibits the sub-structure property, you can use dynamic programming
: technique to solve it in O(m) time, where m is the number of edges.
: Give me email and I can send you the solution.
|
m********7
发帖数: 37 | 5 "现在找到状态为0的node", which implies that we can not re-set the node whose
values are 1 or -1, right? i.e., we are allowed to change the value 0? |
t******r
发帖数: 209 | 6 yes, exactly.
my email is w********[email protected], thanks. |
t******r
发帖数: 209 | 7 yes, exactly.
my email is w********[email protected], thanks. |
m********7
发帖数: 37 | 8 Max sum of all edges
= max {sum of all edges whose two nodes are positive (1)
+ sum of all edges whose two nodes are negative (2)
- sum of all edges whose two nodes are positive and negative (3)}
As we are allowed to change all 0 nodes, then the problem is reduced to how
to find the max radius from all negative nodes. Acrossing the next edge,
all nodes will be positive. So we only consider (2) and (3).
For any negative node, u, we let d the distance between u to v where v is a
positive and all |
c*****t
发帖数: 1879 | 9 I think that this problem is NPC (similar to hypergraph partitioning).
I don't quite understand you solution, but here is a possible counter
example for your algorithm:
+ -
\ /
0 0
\ /
0-0-0
/ \
0 0
/ \
+ -
All edges in the graph have the weight of 1. One of the optimal
solutions to this graph is to have all nodes to the left of the
center one as + and all the nodes to the right as -.
how
a
【在 m********7 的大作中提到】
: Max sum of all edges
: = max {sum of all edges whose two nodes are positive (1)
: + sum of all edges whose two nodes are negative (2)
: - sum of all edges whose two nodes are positive and negative (3)}
: As we are allowed to change all 0 nodes, then the problem is reduced to how
: to find the max radius from all negative nodes. Acrossing the next edge,
: all nodes will be positive. So we only consider (2) and (3).
: For any negative node, u, we let d the distance between u to v where v is a
: positive and all
|
m********7
发帖数: 37 | 10 If you use FFT, you can solve it also efficiently. It should be no worse
than DP method and more elegant. |
m********7
发帖数: 37 | 11 If you use FFT, you can solve it also efficiently. It should be no worse
than DP method and more elegant. |
h*******e
发帖数: 225 | 12 how to use FFT to solve it?
【在 m********7 的大作中提到】
: If you use FFT, you can solve it also efficiently. It should be no worse
: than DP method and more elegant.
|
