Randomized extension for continuous refinement of the solution
Registered by
Vamsi Kundeti
As we know the hierarchical BLM solver solves the problem bottom up and works on the entire square. In this feature to further refine the solution we implement the following.
1. Solve the problem bottom-up for the first time
2. Randomly pick a location, and randomly choose a
width of the square, now apply the randomization for that
sub-square.
3. continue the process.
If we model this as a simple Random-walk on a solution graph, we can analytically
prove that the we can indeed hit the optimial solution enventually (with high probability).
Similar to Drunkard-walk.
This extension is of atmost importance from the practice.
Blueprint information
- Status:
- Started
- Approver:
- Vamsi Kundeti
- Priority:
- Essential
- Drafter:
- Vamsi Kundeti
- Direction:
- Approved
- Assignee:
- Vamsi Kundeti
- Definition:
- Approved
- Series goal:
- Accepted for trunk
- Implementation:
- Beta Available
- Milestone target:
- None
- Started by
- Vamsi Kundeti
- Completed by
Related branches
Related bugs
Sprints
Whiteboard
Revision 13 contains the implementation of this feature
(?)