Timeline for Is there any strategy to brute force search?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 20, 2015 at 8:11 | comment | added | Michael Wehar | This post discusses the complexity of brute force search: cstheory.stackexchange.com/questions/14404/… | |
| Oct 16, 2015 at 7:23 | comment | added | Mark Hurd | For your specific example, you've got sum and product of roots that can make simplify the search. | |
| Oct 14, 2015 at 16:42 | comment | added | Michael Wehar | @MSalters You made a good point with your comment. I called it brute force search because if there is no solution then you would still try each element of the search space (little to no pruning). However, you may use previous knowledge that you've gained to intelligently determine the order in which you enumerate through the search space. Also, as you mentioned, by changing the enumeration order you could make parallelization more difficult. | |
| Oct 14, 2015 at 11:39 | comment | added | TLW | A tidbit - I've calculated optimal rocket staging for Kerbal Space Program a few times with an alpha/beta/heuristic search (basically directed brute force that prunes search trees that cannot be the best answer), and manual tweaking of priorities can make it orders of magnitude faster. In particular, occasionally expanding a node with a good heuristic as opposed to best alpha seems to help significantly, as there's no inexpensive but good way to calculate alpha that I've found. So the answer is yes to question A. | |
| Oct 14, 2015 at 9:38 | comment | added | MSalters | Do you mean "brute force" in the strict sense of trying every possible input, using no information gained from one input to choose future inputs ? This particular definition of brute force is relevant because it is trivially parallelized, yet it's compatible with all your suggested strategies. OTOH, Juho's answer talks about "pruning the search space" which excludes multiple inputs based on the information gained from just one input. | |
| Oct 14, 2015 at 8:37 | history | tweeted | twitter.com/StackCompSci/status/654214318507081728 | ||
| Oct 14, 2015 at 7:23 | answer | added | user16034 | timeline score: 3 | |
| Oct 14, 2015 at 7:18 | answer | added | Juho | timeline score: 5 | |
| Oct 14, 2015 at 4:55 | history | edited | Michael Wehar | CC BY-SA 3.0 |
added 11 characters in body
|
| Oct 14, 2015 at 4:43 | history | edited | Michael Wehar |
edited tags
|
|
| Oct 14, 2015 at 4:38 | review | First posts | |||
| Oct 14, 2015 at 10:50 | |||||
| Oct 14, 2015 at 4:34 | history | asked | Michael Wehar | CC BY-SA 3.0 |