3 ms·
A fine example of the fact that brute force is often a powerful heuristic. I believe I recall hearing from the MIT OCW Algorithms course that they often rely on
by andrewstuart2 10y ago
A fine example of the fact that brute force is often a powerful heuristic. I believe I recall hearing from the MIT OCW Algorithms course that they often rely on computer time doing exhaustive search (i.e. brute force) to "not disprove" some algorithm they develop before sinking too much time into developing a mathematical proof.
- Waterluvian 10y agoI find it beautiful that some things in math are so easily and convincingly disprovable that brute force is a valid approach. Once you have the numbers, it's easily reproducible.
- waterhouse 10y agoI think "exhaustive search" is a misnomer here, as one obviously cannot exhaustively search the integers. (Unless we might say the machine gets exhausted.)
- andrewstuart2 10y agoI think the particular quote I'm remembering was in the context of graph algorithms, where exhaustive search is more appropriate a term. :-)
- reubenmorais 10y agoI believe this is the quote you're referring to, by Erik Demaine on 6.006: "I use BFS a lot, myself, to check mathematical conjectures. [...] You think something is true, you can imagine some graph of all possible inputs to that theorem and you'd need to check them. Typical way of doing that is BFS through that entire graph of states. Usually we're testing finite special cases of a general conjecture, but if we find a counterexample, we're done, don't have to work on it anymore. If we don't find a counterexample then we have to do the mathematics." https://www.youtube.com/watch?v=s-CYnVz-uh4&t=8m51s https://www.youtube.com/watch?v=s-CYnVz-uh4&t=8m51s
- deleted 10y ago[deleted]