6 ms·
Random Solutions are Often Good Enough
- swayvil 12y agoGet the depth (distance from edge to deepest point) of an irregular polygon. At first I was doing all kinds of crazy geometry and the future looked bleak. Then I was "fuck it" and did a randomsample, reduce, randomsample, reduce thing. It's fast and precise.
- timdumol 12y agoIn case you're still interested in an exact solution, I think computing the Voronoi diagram for the polygon (treating each vertex as a point) should help in finding the answer. The deepest point should lie on one of the edges of the Voronoi diagram.
- lifeformed 12y agoI had a similar experience. I was writing a polygon intersection algorithm, heavily optimized for the domain of inputs, but kept having issues when vertices were coincident or when edges were colinear. I spent days trying to fix it, until I decided to just truncate the vertex values to some good-enough level of precision, and add a random unique jitter to each value (past the truncated precision). This made sure that there were never coincident or colinear situations. Then I just truncated the resulting intersection points again to remove the jitter. It was trivial to add, and it was faster than all the extra checks I'd have to do for the edge cases. Also, it gave me peace of mind, since I knew it worked in theory, instead of my other feeble attempts which worked most of the time, but always failed in some new edge case.
- leeoniya 12y agoi'm currently working on a box-packing algo that attempts to find likely-to-be-used boxes to pack an order for shipping cost estimation. (variant of the knapsack problem [1]). "close enough" is the name of the game here :) http://en.wikipedia.org/wiki/Knapsack_problem http://en.wikipedia.org/wiki/Knapsack_problem
- deleted 12y ago[deleted]
- qnaal 12y agolots of algorithms use entropy in clever and powerful ways see: http://en.wikipedia.org/wiki/Monte_Carlo_method http://en.wikipedia.org/wiki/Monte_Carlo_method
- jchonphoenix 12y agoPerhaps you should actually read the paper and you'll understand. It's less daunting than it looks and is not very theoretical.
- swehner 12y agoAnother angle: totally inefficient solutions can be useful too. I put this sample up a while ago, Ridiculous Adding, https://gist.github.com/stephanwehner/11227766 https://gist.github.com/stephanwehner/11227766
- ajtulloch 12y agoThis seems to be a specific case of the more general principle of "concentration of measure". Terence Tao at [1] has some useful notes. From a quick scan of the paper at http://arxiv.org/pdf/1402.0423v1.pdf http://arxiv.org/pdf/1402.0423v1.pdf, Theorem 1 seems to essentially be a CoM result for the order statistics of symmetric RVs. This same principle can be applied in other contexts [2] - e.g. Johnson-Lindestrauss is essentially a statement that random projections are "often" nearly isometries. [1]: http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/ http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concen... [2]: https://news.ycombinator.com/item?id=7971188 https://news.ycombinator.com/item?id=7971188
- thanatropism 12y agoWhere is those people "programming isn't math" God now, eh?
- deleted 12y ago[deleted]
- ISL 12y ago"Offered the choice between mastery of a five-foot shelf of analytical statistics books and middling ability at performing statistical Monte-Carlo simulations, we would surely choose to have the latter skill." -- Numerical Recipes in C++, 2nd ed. p.696.
- brockrockman 12y agoa good reminder that the TSP optimization problem is only NP-hard, not NP-complete -- http://www.nomachetejuggling.com/2012/09/14/traveling-salesman-the-most-misunderstood-problem/ http://www.nomachetejuggling.com/2012/09/14/traveling-salesm...
- sidww2 12y ago"only" NP-hard? You know that NP-hard problems are equal to order harder than NP-complete ones, right?
- Strilanc 12y agoProbably referring to the definition, not the difficulty.
- codeflo 12y agoYes, NP-complete is a subset of NP-hard. Grandparent states that NP-completeness only applies to decision problems (which is correct), but seems to think that NP-hardness applies to optimization problems (which is incorrect; NP-hard too is a class of decision problems).
- brockrockman 12y agodidn't mean to imply "only" as a less-than comparison -- just a distinction.
- pdonis 12y agoI wonder about one statement in the article: he says that Sudoku is NP-hard. I wonder about this since Peter Norvig has written a Sudoku solver: http://norvig.com/sudoku.html http://norvig.com/sudoku.html Of course, this solver is for the standard Sudoku game on a 9 x 9 grid. Perhaps the claim in the article refers to "Sudoku" in the sense of the generalized problem of solving n x n Sudoku, for any n?
- rach3 12y agoNP-hard does not mean unsolvable. I don't see that solver claiming to be polynomial?
- matchu 12y agoThe solver doesn't obviously negate the puzzle's NP-completeness. It first reduces the solution space, then starts brute-forcing what's left. I don't have a proof on hand, but that just smells nonpolynomial. You could argue that, if we consider "Sudoku" to be the instance of the puzzle where n=9, then the puzzle isn't NP-hard because it has the constant-time solution of trying all 6.67e21 solutions, but the result is so uninteresting that it's understood that the author means the more general problem.
- jimmaswell 12y agoDepends on the initial state of the puzzle. Sometimes there's always a deterministic set of correct next moves to make. I guess this refers to cases that aren't like that?
- pjscott 12y agoRight; we're talking about upper bounds here. Assume that the boards are chosen by some kind of wily, malevolent demon with an obsessive desire to embed tricky 3SAT problems in everything.
- matchu 12y agoSimilarly, sometimes your sorting algorithm takes linear time because the input was a sorted list. That's the lower bound, but lower bounds usually aren't as interesting as upper bounds.
- jwecker 12y agoIn the context of clever startup solutions, this brings to mind the quote from George S Patton: "A good plan, violently executed now, is better than a perfect plan executed next week." Even if they didn't approach optimal solutions, the fact that generating random feasible solutions can be much easier and result in more tractable mental models (and therefore easier to maintain code etc.) means you can be 'violently executing' in the field of battle much earlier. The fact that they approach optimality is gravy.
- bshimmin 12y agoSlightly worthless comment, but I think that is the first web site I've ever seen typeset in Computer Modern. Strangely, it looks rather nice to me (not that I think Computer Modern is particularly an attractive font, but my massive exposure to it over the years has given it a certain quality of reassurance).
- zwieback 12y agoIt's not very readable but lends instant gravitas to the material, sort of like the anti-Comic Sans
- brucehauman 12y agoThe last line is priceless. "So the moral of the story is: Sometimes quickly and mindlessly choosing a random solution isn't half bad!"
- JacobEdelman 12y agoActually, with the constant of approximation being two, its almost exactly half good.
- coldcode 12y agoAs long as it isn't half-ass.
- iandanforth 12y agoThis page is awesome, I love it. The author presents the material clearly and carefully. So many authors dealing with mathematical concepts are lazy and just throw up equations. Yuk! Here we see a careful progression of complexity supported with complete visual examples and numerical values, using the equations, worked out. I wish this were not so unusual, but huge thanks for having done it!
- nicholas73 12y agoI built my sudoku site using a pseudo random puzzle generator. I don't know the best algorithm to generate puzzles, so with some basic parameters for good puzzles, I let the puzzles fill out randomly. I generate, then test them for unique solutions and difficulty level. If the puzzle is invalid, I toss it. What I lack in algorithmic knowledge, I make up for with server resources :) http://sudokuisland.com http://sudokuisland.com I'm not a CS guy so reading this article made me feel a bit better, especially since it mentions sudoku.
- Terr_ 12y agoMy gut-feeling is that building Sudoku puzzles shouldn't be too hard to generate, because every random choice you make reduces the space you need to pull from for the next choice. Whether they're "hard enough to solve", though....
- nicholas73 12y agoThe difficulty comes from multiple solutions to your puzzles (which would force the player to guess). As it turned out, a purely randomly selected puzzle would 99.9%* of the time give you a puzzle with multiple solutions. I would have settled for 99%, but more was too much server resources to hog! And then add the screening for difficulty levels. *Not an exact figure =)
- PeterisP 12y agoThe sudoku difficulty can be very varied, but it doesn't rely on multiple solutions - a grid where multiple solutions are possible simply isn't a valid sudoku puzzle; a minimalistic puzzle is one where no numbers can be eliminated without losing uniqueness of the solution, but adding extra numbers to that minimalistic puzzle makes it easier.
- nicholas73 12y agoAll my puzzles have unique solutions. I said the difficulty of generating is from multiple solutions, not that the puzzles are difficult because of them.
- LeicaLatte 12y agoTotally tangential but, Marco points out in latest ATP how he randomizes the lists of podcasts every time the list is shown. Neat!