主观题：Voting Tree
Given two 2-dimentional shapes A and B which are represented as closed polygons, our goal is to find the optimal correspondences (or "match") between points in A and B. A simple example is illustrated below.
An optimal correspondence (match) between the two shapes are {(a,q),(b,r),(c,p)}.
In this project, you are supposed to solve the aforementioned problem with a combination of various data structures including arrays and voting trees. The basic idea is to build trees, where each pair of points in A and B can form a treenode. Starting from a node (as a root node), you can expand a tree by adding another tree node conditional on that the expanded child node contributes to a valid match between A and B. For example, if you start from $$(m_1,n_1)$$ and extend it with $$(m_2,n_2)$$, then the following conditions must hold: $$m_1\ne m_2$$, $$n_1\ne n_2$$, and more importantly the match should be monotonic, that is, the list of indices of { $$m_1,m_2,m_3,\cdots$$ } should be monotonically increasing or decreasing, so is true with { $$n_1,n_2,n_3,\cdots$$ }. All these extensions lead to a set of trees within which each tree path represents a potential match between A and B. Then your task is to let these paths **vote** for the confidences of possible matches.
Obviously, if we simply aggregate all valid paths, the search will quickly grow to an exponential complexity (count how many possible paths out there!). Thus, an efficient expanding strategy is required to stop tree expansion if some requirements are violated. If the current tree path is obviously a bad match, for example, the match {(a,p),(c,r)} in the above figure has a large variance measure in terms of path lengths and interior angles, the tree expansion from that node should be terminated. We leave here for you to design and experiment out the stopping conditions. These conditions also determine how efficient your algorithm will be. So, take your risk.
After the tree expansion, we start the voting process, which operates as follows: for each tree path $$P = {(m_1,n_1), (m_2,n_2),\cdots ,(m_k,n_k)}$$, each pair within the path will receive a vote. To implement this, we can put all elements in shape A and all elements in shape B into a vote table. Take the above example for an instance, the table will look like the following:
Each element in the table stores the total votes of that pair. If a pair $$(m_i,n_i)$$ appears in a tree path, then the corresponding score in the table will increase by 1. A pair with higher votes indicates a more reliable match. Finally, our task is to search for the best match between A and B.
Various approaches can be taken here to solve the problem. Bonus points (+2 pts.) would be given if you could experiment out at least 2 different solutions to find an optimal match from the table and compare their performances in the report. Make sure that your best solution does not violate the monotonicity property of the match.
### Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers $$M$$ and $$N$$ ($$3\le M,N \le 100$$) which are the total number of points in shape A and B respectively. The next $$M+N$$ lines each contains the $$x$$ and the $$y$$ coordinates (in float type) of a point in shape A and B, respectively, in clockwise order. Hence for each shape, the $$i$$-th point given is indexed as $$i$$ ($$i=1,\cdots , M$$ or $$N$$).
### Output Specification:
For each test case, print the correspondence points in the best match in the format "$$(i_1, i_2)$$", where $$i_1$$ is the index of a point in shape A, and $$i_2$$ in shape B. Each pair in a line, given in increasing order of shape A indices.
### Sample Input:
in
3 4
0 4
3 0
0 0
8 4
8 1
4.25 6
8 6
### Sample Output:
out
(1, 2)
(2, 3)
(3, 4)
**Remarks:** an interesting observation you may find in this problem is that if there is a good set of good matches at the root level, then the expansion may quickly lead to an explosion as the node number is large and there will be many repeated tree paths participating in the voting process. In this project you are not required to solve this issue. But you can think on it. Another thing to consider is how to extend this technique to solve graph matching problems, in which cases you may require that the graphs do not contain nodes with degree of 2.
### Grading Policy:
- Chapter 1: Introduction (6 pts.)
- Chapter 2: Algorithm Specification (12 pts.)
- Chapter 3: Testing Results (20 pts.)
- Chapter 4: Analysis and Comments (10 pts.)
- Write the program (50 pts.) with sufficient comments.
- Overall style of documentation (2 pts.)
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
- the cover page is not complete (-1)
- the introduction is a simple copy + paste of the assignment statement (-3)
- the introduction is not very clear -- in this chapter one is supposed to make it clear WHAT is to be done, besides why one is doing it (-1 ~ -2)
- others - please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of all the key algorithms involved (+3 pts. for the data structures; +7 pts. for the algorithms), plus a sketch of the main program (+2 pts.). Deduct points if:
- the algorithm specification is not complete – the data structure description is missing (-2)
- the algorithm specification is not complete –the key algorithm is missing (-3 ~ -7)
- not making one's algorithm easier to understand than a simple program (-2)
- only a program + comments, which is not acceptable (-4)
- others - please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points if:
- the document looks messy - some of the data in the charts and tables are missing (-1)
- the hand-in is not zipped with proper folders (-1)
- the hand-in is not complete - some files are missing (-1)
- others - please specify in the final comments.
Item 4: 20 points
A complete table of test cases with testing purposes must be given in Chapter 3. A minimum of 3 test cases must be given (+10 pts.). Besides at least one comprehensive test (+6 pts.), the cases with the smallest or the largest sizes, and some extreme cases must be covered (+4 pts.). Deduct points if:
- the testing results contain some test cases, however with no specification on their purposes (-3)
- the testing results contain some test cases, but there are still bugs missed (-1 ~ -10)
- the testing results contain too few cases and hence is too simple to be considered as being complete (-4 ~ -10)
- others - please specify in the final comments.
Item 5: 10 points
Analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms are supposed to be given in Chapter 4. Bonus point for discussing more than just one algorithm (+2 pts.). Deduct points if:
- analysis of the complexities of time and/or space is missing -- one must show how one has reached the conclusions, instead of simply listing them (-4)
- others - please specify in the final comments.
Item 6: 50 points
For the programming work, deduct points if:
- the programs are not working properly (-1 ~ -20)
- the programs are not well-commented (-50)
- the programming style is too messy to be judged (-1 ~ -5)
- others - please specify in the final comments.
An optimal correspondence (match) between the two shapes are {(a,q),(b,r),(c,p)}.
In this project, you are supposed to solve the aforementioned problem with a combination of various data structures including arrays and voting trees. The basic idea is to build trees, where each pair of points in A and B can form a treenode. Starting from a node (as a root node), you can expand a tree by adding another tree node conditional on that the expanded child node contributes to a valid match between A and B. For example, if you start from $$(m_1,n_1)$$ and extend it with $$(m_2,n_2)$$, then the following conditions must hold: $$m_1\ne m_2$$, $$n_1\ne n_2$$, and more importantly the match should be monotonic, that is, the list of indices of { $$m_1,m_2,m_3,\cdots$$ } should be monotonically increasing or decreasing, so is true with { $$n_1,n_2,n_3,\cdots$$ }. All these extensions lead to a set of trees within which each tree path represents a potential match between A and B. Then your task is to let these paths **vote** for the confidences of possible matches.
Obviously, if we simply aggregate all valid paths, the search will quickly grow to an exponential complexity (count how many possible paths out there!). Thus, an efficient expanding strategy is required to stop tree expansion if some requirements are violated. If the current tree path is obviously a bad match, for example, the match {(a,p),(c,r)} in the above figure has a large variance measure in terms of path lengths and interior angles, the tree expansion from that node should be terminated. We leave here for you to design and experiment out the stopping conditions. These conditions also determine how efficient your algorithm will be. So, take your risk.
After the tree expansion, we start the voting process, which operates as follows: for each tree path $$P = {(m_1,n_1), (m_2,n_2),\cdots ,(m_k,n_k)}$$, each pair within the path will receive a vote. To implement this, we can put all elements in shape A and all elements in shape B into a vote table. Take the above example for an instance, the table will look like the following:
Each element in the table stores the total votes of that pair. If a pair $$(m_i,n_i)$$ appears in a tree path, then the corresponding score in the table will increase by 1. A pair with higher votes indicates a more reliable match. Finally, our task is to search for the best match between A and B.
Various approaches can be taken here to solve the problem. Bonus points (+2 pts.) would be given if you could experiment out at least 2 different solutions to find an optimal match from the table and compare their performances in the report. Make sure that your best solution does not violate the monotonicity property of the match.
### Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers $$M$$ and $$N$$ ($$3\le M,N \le 100$$) which are the total number of points in shape A and B respectively. The next $$M+N$$ lines each contains the $$x$$ and the $$y$$ coordinates (in float type) of a point in shape A and B, respectively, in clockwise order. Hence for each shape, the $$i$$-th point given is indexed as $$i$$ ($$i=1,\cdots , M$$ or $$N$$).
### Output Specification:
For each test case, print the correspondence points in the best match in the format "$$(i_1, i_2)$$", where $$i_1$$ is the index of a point in shape A, and $$i_2$$ in shape B. Each pair in a line, given in increasing order of shape A indices.
### Sample Input:
in
3 4
0 4
3 0
0 0
8 4
8 1
4.25 6
8 6
### Sample Output:
out
(1, 2)
(2, 3)
(3, 4)
**Remarks:** an interesting observation you may find in this problem is that if there is a good set of good matches at the root level, then the expansion may quickly lead to an explosion as the node number is large and there will be many repeated tree paths participating in the voting process. In this project you are not required to solve this issue. But you can think on it. Another thing to consider is how to extend this technique to solve graph matching problems, in which cases you may require that the graphs do not contain nodes with degree of 2.
### Grading Policy:
- Chapter 1: Introduction (6 pts.)
- Chapter 2: Algorithm Specification (12 pts.)
- Chapter 3: Testing Results (20 pts.)
- Chapter 4: Analysis and Comments (10 pts.)
- Write the program (50 pts.) with sufficient comments.
- Overall style of documentation (2 pts.)
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
- the cover page is not complete (-1)
- the introduction is a simple copy + paste of the assignment statement (-3)
- the introduction is not very clear -- in this chapter one is supposed to make it clear WHAT is to be done, besides why one is doing it (-1 ~ -2)
- others - please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of all the key algorithms involved (+3 pts. for the data structures; +7 pts. for the algorithms), plus a sketch of the main program (+2 pts.). Deduct points if:
- the algorithm specification is not complete – the data structure description is missing (-2)
- the algorithm specification is not complete –the key algorithm is missing (-3 ~ -7)
- not making one's algorithm easier to understand than a simple program (-2)
- only a program + comments, which is not acceptable (-4)
- others - please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points if:
- the document looks messy - some of the data in the charts and tables are missing (-1)
- the hand-in is not zipped with proper folders (-1)
- the hand-in is not complete - some files are missing (-1)
- others - please specify in the final comments.
Item 4: 20 points
A complete table of test cases with testing purposes must be given in Chapter 3. A minimum of 3 test cases must be given (+10 pts.). Besides at least one comprehensive test (+6 pts.), the cases with the smallest or the largest sizes, and some extreme cases must be covered (+4 pts.). Deduct points if:
- the testing results contain some test cases, however with no specification on their purposes (-3)
- the testing results contain some test cases, but there are still bugs missed (-1 ~ -10)
- the testing results contain too few cases and hence is too simple to be considered as being complete (-4 ~ -10)
- others - please specify in the final comments.
Item 5: 10 points
Analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms are supposed to be given in Chapter 4. Bonus point for discussing more than just one algorithm (+2 pts.). Deduct points if:
- analysis of the complexities of time and/or space is missing -- one must show how one has reached the conclusions, instead of simply listing them (-4)
- others - please specify in the final comments.
Item 6: 50 points
For the programming work, deduct points if:
- the programs are not working properly (-1 ~ -20)
- the programs are not well-commented (-50)
- the programming style is too messy to be judged (-1 ~ -5)
- others - please specify in the final comments.
