Content deleted Content added
→Basic algorithm: ahsan warraich |
|||
Line 12:
===Basic algorithm===
In order
# ''valid'' (''P'', ''c''): check whether candidate ''c'' is a solution for ''P''.
# ''output'' (''P'', ''c''): use the solution ''c'' of ''P'' as appropriate to the application.
Line 23:
'''end while'''
For example, when looking for the divisors of an integer ''n'', the instance data ''P'' is the number ''n''. The call ''first''(''n'') should return the integer 1 if ''n'' ≥ 1, or Λ otherwise; the call ''next''(''n'',''c'') should return ''c'' + 1 if ''c'' < ''n'', and Λ otherwise; and ''valid''(''n'',''c'') should return '''true''' if and only if ''c'' is a divisor of ''n''. (In fact, if we choose Λ to be ''n'' + 1, the tests ''n'' ≥ 1 and ''c'' < ''n'' are unnecessary.)The brute-force search algorithm above will call ''output'' for every candidate that is a solution to the given instance ''P''. The algorithm is easily modified to stop after finding the first solution, or a specified number of solutions; or after testing a specified number of candidates, or after spending a given amount of [[central processing unit|CPU]] time.
==Combinatorial explosion==
| |||