티스토리 뷰

Comp Sci/Tips

How to Design - Case by Case

jeongtaebang 2017.12.18 00:00

When designing an algorithm, ask yourself : 


For which cases does the obvious method work?


Then find a new way to tackle the remaining cases!



예제)


Find a hamiltonian path through a tournament graph.


Using a more-of-input approach, we claim to have a solution while pretending that the nodes we have processed so far is the entire input instance.


We want to maintain the Loop Invariant by adding a new node and finding a new hamiltonian path through this new input instance (sub-instance).


How to do this? Case Analysis


We established that we have a hamiltonian path through 

.


To get a new solution with added to form a new sub-instance, pretended to be the entire input,





댓글
댓글쓰기 폼