Algorithm for polygon with weight on vertices and

Question

I am thinking about the algorithm for the following problem (found on carrercup):

Given a polygon with N vertexes and N edges. There is an int number(could be negative) on every vertex and an operation in set(*,+) on every edge. Every time, we remove an edge E from the polygon, merge the two vertexes linked by the edge(V1,V2) to a new vertex with value: V1 op(E) V2. The last case would be two vertexes with two edges, the result is the bigger one. Return the max result value can be gotten from a given polygon.

I think we can use just greedy approach. I.e. for polygon with k edges find a pair (p, q) which produces the maximum number when collapsing: (p ,q) = max ({i operation j : i, j - adjacent edges)

Then just call a recursion on polygons: 1. Let function CollapseMaxPair( P(k) ) - gets polygon with k edges and returns 'collapsed' polygon with k-1 edges 2. Then our recursion:

 P = P(N);
 Releat until two edges left
     P =  CollapseMaxPair( P )
 maxvalue = max ( two remained values)

What do you think?

algorithm language-agnostic polygon

share | improve this question | follow |

标签：

举报

3条回答

冷血范

2楼-- · 2020-07-23 05:22

I don't think the greedy algorithm works. Let the vertices be A = 0, B = 1, C = 2, and the edges be AB = a - 5b, BC = b + c, CA = -20. The greedy algorithm selects BC to evaluate first, value 3. Then AB, value, -15. However, there is a better sequence to use. Evaluate AB first, value -5. Then evaluate BC, value -3. I don't know of a better algorithm though.

查看更多

0人赞 添加讨论(0) 举报

•  加载中...

Animai°情兽

3楼-- · 2020-07-23 05:25

Here's a case where your greedy algorithm fails:

Imagine your polygon is a square with vertices A, B, C, D (top left, top right, bottom right, bottom left). This gives us edges (A,B), (A,D), (B,C), and (C, D).

Let the weights be A=-1, B=-1, C=-1, and D=1,000,000.

A (-1) ------ B (-1)  
|             |  
|             |  
|             |  
|             |  
D(1000000) ---C (-1)  

Clearly, the best strategy is to collapse (A,B), and then (B,C), so that you may end up with D by itself. Your algorithm, however, will start with either (A,D) or (D,C), which will not be optimal.

A greedy algorithm that combines the min sums has a similar weakness, so we need to think of something else.

I'm starting to see how we want to try to get all positive numbers together on one side and all negatives on the other.

If we think about the initial polygon entirely as a state, then we can imagine all the possible child states to be the subsequent graphs were an edge is collapsed. This creates a tree-like structure. A BFS or DFS would eventually give us an optimal solution, but at the cost of traversing the entire tree in the worst case, which is probably not as efficient as you'd like.

What you are looking for is a greedy best-first approach to search down this tree that is provably optimal. Perhaps you could create an A*-like search through it, although I'm not sure what your admissable heuristic would be.

查看更多

0人赞 添加讨论(0) 举报

•  加载中...

做个烂人

4楼-- · 2020-07-23 05:45

I have answered this question here: Google Interview : Find the maximum sum of a polygon and it was pointed out to me that that question is a duplicate of this one. Since no one has answered this question fully yet, I have decided to add this answer here as well.

As you have identified (tagged) correctly, this indeed is very similar to the matrix multiplication problem (in what order do I multiply matrixes in order to do it quickly).

This can be solved polynomially using a dynamic algorithm.

I'm going to instead solve a similar, more classic (and identical) problem, given a formula with numbers, addition and multiplications, what way of parenthesizing it gives the maximal value, for example 6+1 * 2 becomes (6+1)*2 which is more than 6+(1*2).

Let us denote our input a1 to an real numbers and o(1),...o(n-1) either * or +. Our approach will work as follows, we will observe the subproblem F(i,j) which represents the maximal formula (after parenthasizing) for a1,...aj. We will create a table of such subproblems and observe that F(1,n) is exactly the result we were looking for.

Define

F(i,j)

 - If i>j return 0 //no sub-formula of negative length
 - If i=j return ai // the maximal formula for one number is the number
 - If i<j return the maximal value for all m between i (including) and j (not included) of:
     F(i,m) (o(m)) F(m+1,j) //check all places for possible parenthasis insertion

This goes through all possible options. TProof of correctness is done by induction on the size n=j-i and is pretty trivial.

Lets go through runtime analysis:

If we do not save the values dynamically for smaller subproblems this runs pretty slow, however we can make this algorithm perform relatively fast in O(n^3)

We create a n*n table T in which the cell at index i,j contains F(i,j) filling F(i,i) and F(i,j) for j smaller than i is done in O(1) for each cell since we can calculate these values directly, then we go diagonally and fill F(i+1,i+1) (which we can do quickly since we already know all the previous values in the recursive formula), we repeat this n times for n diagonals (all the diagonals in the table really) and filling each cell takes (O(n)), since each cell has O(n) cells we fill each diagonals in O(n^2) meaning we fill all the table in O(n^3). After filling the table we obviously know F(1,n) which is the solution to your problem.

Now back to your problem

If you translate the polygon into n different formulas (one for starting at each vertex) and run the algorithm for formula values on it, you get exactly the value you want.

查看更多

0人赞 添加讨论(0) 举报

•  加载中...

登录 后发表回答

相关问题

查看全部

相关文章

• 敏捷开发在互联网时代里的价值
• PL2586|替代FE1.1S|替代MA8601|USB2.0HUB集线器芯片|旺玖
• 力软快速开发平台，帮助中小企业躲过数字化“踏浪出海”的“暗礁”
• 软件开发：站在风口上的低代码
• TYPEC转HDMI方案|TYPEC扩展坞方案|CS5265设计4K60HZ TYPEC转HDMI方
• DP转HDMI2.0|DP转HDMI和VGA输出|CS5262AN方案应用|瑞奇达CS5262设计电
• Capstone瑞奇达|台湾瑞奇达|一级代理商|台湾瑞奇达科技有限公司
• CH7511B替代方案|CS5211设计方案|CS5211替代CH7511B|eDP转LVDS转接板

查看全部

收藏的人(4)

• 
• 
• 
• 

Answer 1

I don't think the greedy algorithm works. Let the vertices be A = 0, B = 1, C = 2, and the edges be AB = a - 5b, BC = b + c, CA = -20. The greedy algorithm selects BC to evaluate first, value 3. Then AB, value, -15. However, there is a better sequence to use. Evaluate AB first, value -5. Then evaluate BC, value -3. I don't know of a better algorithm though.

Answer 2

Here's a case where your greedy algorithm fails:

Imagine your polygon is a square with vertices A, B, C, D (top left, top right, bottom right, bottom left). This gives us edges (A,B), (A,D), (B,C), and (C, D).

Let the weights be A=-1, B=-1, C=-1, and D=1,000,000.

A (-1) ------ B (-1)  
|             |  
|             |  
|             |  
|             |  
D(1000000) ---C (-1)  

Clearly, the best strategy is to collapse (A,B), and then (B,C), so that you may end up with D by itself. Your algorithm, however, will start with either (A,D) or (D,C), which will not be optimal.

A greedy algorithm that combines the min sums has a similar weakness, so we need to think of something else.

I'm starting to see how we want to try to get all positive numbers together on one side and all negatives on the other.

If we think about the initial polygon entirely as a state, then we can imagine all the possible child states to be the subsequent graphs were an edge is collapsed. This creates a tree-like structure. A BFS or DFS would eventually give us an optimal solution, but at the cost of traversing the entire tree in the worst case, which is probably not as efficient as you'd like.

What you are looking for is a greedy best-first approach to search down this tree that is provably optimal. Perhaps you could create an A*-like search through it, although I'm not sure what your admissable heuristic would be.

Answer 3

I have answered this question here: Google Interview : Find the maximum sum of a polygon and it was pointed out to me that that question is a duplicate of this one. Since no one has answered this question fully yet, I have decided to add this answer here as well.

As you have identified (tagged) correctly, this indeed is very similar to the matrix multiplication problem (in what order do I multiply matrixes in order to do it quickly).

This can be solved polynomially using a dynamic algorithm.

I'm going to instead solve a similar, more classic (and identical) problem, given a formula with numbers, addition and multiplications, what way of parenthesizing it gives the maximal value, for example 6+1 * 2 becomes (6+1)*2 which is more than 6+(1*2).

Let us denote our input a1 to an real numbers and o(1),...o(n-1) either * or +. Our approach will work as follows, we will observe the subproblem F(i,j) which represents the maximal formula (after parenthasizing) for a1,...aj. We will create a table of such subproblems and observe that F(1,n) is exactly the result we were looking for.

Define

F(i,j)

 - If i>j return 0 //no sub-formula of negative length
 - If i=j return ai // the maximal formula for one number is the number
 - If i<j return the maximal value for all m between i (including) and j (not included) of:
     F(i,m) (o(m)) F(m+1,j) //check all places for possible parenthasis insertion

This goes through all possible options. TProof of correctness is done by induction on the size n=j-i and is pretty trivial.

Lets go through runtime analysis:

If we do not save the values dynamically for smaller subproblems this runs pretty slow, however we can make this algorithm perform relatively fast in O(n^3)

We create a n*n table T in which the cell at index i,j contains F(i,j) filling F(i,i) and F(i,j) for j smaller than i is done in O(1) for each cell since we can calculate these values directly, then we go diagonally and fill F(i+1,i+1) (which we can do quickly since we already know all the previous values in the recursive formula), we repeat this n times for n diagonals (all the diagonals in the table really) and filling each cell takes (O(n)), since each cell has O(n) cells we fill each diagonals in O(n^2) meaning we fill all the table in O(n^3). After filling the table we obviously know F(1,n) which is the solution to your problem.

Now back to your problem

If you translate the polygon into n different formulas (one for starting at each vertex) and run the algorithm for formula values on it, you get exactly the value you want.