Highest voted questions tagged heuristics - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T15:34:50Z https://cs.stackexchange.com/feeds/tag?tagnames=heuristics&sort=votes http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/407 27 Measuring the difficulty of SAT instances Artem Kaznatcheev https://cs.stackexchange.com/users/55 2012-03-15T05:00:23Z 2019-06-02T17:52:41Z <p>Given an instance of SAT, I would like to be able to estimate how difficult it will be to solve the instance.</p> <p>One way is to run existing solvers, but that kind of defeats the purpose of estimating difficulty. A second way might be looking a the ratio of clauses to variables, as is done for phase transitions in random-SAT, but I am sure better methods exist.</p> <p>Given an instance of SAT, are there some fast heuristics to measure the difficulty? The only condition is that these heuristics be faster than actually running existing SAT solvers on the instance.</p> <hr> <h3>Related question</h3> <p><a href="https://cstheory.stackexchange.com/q/4375/1037">Which SAT problems are easy?</a> on cstheory.SE. This questions asks about tractable sets of instances. This is a similar question, but not exactly the same. I am really interested in a heuristic that given a single instance, makes some sort of semi-intelligent guess of if the instance will be a hard one to solve.</p> https://cs.stackexchange.com/q/12325 17 When to use SAT vs Constraint Satisfaction? D.W. https://cs.stackexchange.com/users/755 2013-05-28T04:15:12Z 2016-05-23T17:55:37Z <p>If I have a hard problem, one standard approach is to express it as a SAT instance and try running a SAT solver on it. Another standard approach is to express it as a constraint satisfaction problem, and try using a CSP solver. The two feel somehow vaguely similar in what sorts of problems can be naturally expressed in their input format.</p> <p>Are there any guidelines or rules of thumb for how to recognize, for a given problem, which approach is more likely to yield good results? Is there any guidance anyone can offer about which sorts of problems can be handled better by SAT solvers than by CSP solvers, or vice versa?</p> <p>(Obviously, there are some easy problems that can be solved by both approaches. There are also some hard problems that can't be usefully solved by either approach. Let's set those aside. The case where guidance is most helpful are problems where either SAT solvers perform better than CSP solvers, or where CSP solvers perform better than SAT solvers. How do I recognize when a SAT solver is likely to be a better fit than a CSP solver, or when a CSP solver is likely to be a better fit than a SAT solver -- i.e., which approach to try first?)</p> https://cs.stackexchange.com/q/16065 16 How does an admissible heuristic ensure an optimal solution? Ashwin https://cs.stackexchange.com/users/4341 2013-10-14T06:34:42Z 2019-02-24T14:59:35Z <p>When using A* (or any other best path finding algorithm), we say that the heuristic used should be <strong>admissible</strong>, that is, it should never overestimate the actual solution path's length (or moves).</p> <p>How does an admissible heuristic ensure an optimal solution? I am preferably looking for an intuitive explanation.</p> <p>If you want you can explain using the <strong>Manhattan</strong> distance heuristic of the <strong>8-puzzle.</strong></p> https://cs.stackexchange.com/q/11126 14 Initial temperature in simulated annealing algorithm Undefined https://cs.stackexchange.com/users/7636 2013-04-08T01:23:34Z 2013-04-09T23:24:51Z <p>I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm.</p> <p>Is there any way of calculating a good initial temperature?</p> https://cs.stackexchange.com/q/63481 12 How does consistency imply that a heuristic is also admissible? user58348 https://cs.stackexchange.com/users/58348 2016-09-15T04:29:32Z 2016-09-15T13:12:16Z <p>A heuristic function $h (n)$ is...</p> <ul> <li><em>Consistent</em> if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the goal. </li> <li><em>Admissible</em> if $h(n)$ never overestimates the true cost to the goal state. </li> </ul> <p>The textbook for my Artificial Intelligence course states that consistency is stronger than admissibility but does not prove it, and I'm having trouble coming up with a mathematical explanation. </p> https://cs.stackexchange.com/q/10182 8 Difference between heuristic and approximation algorithm? user6697 https://cs.stackexchange.com/users/6697 2013-03-01T18:37:47Z 2017-05-05T20:46:54Z <p>i have a problem regarding the following situation. </p> <p>I have two arrays of numbers like this:</p> <pre><code>index/pos 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Array 1(i): 1 2 3 4 7 5 4 3 7 6 5 1 2 3 4 2 Array 2(j): 4 4 8 10 10 7 7 10 10 11 7 4 7 7 4 </code></pre> <p>now suppose the second array is very hard to compute but I have noticed that if I add </p> <p>A[i] + A[i+1]</p> <p>in the array 1 I get the number very close to the number A[j] in the array 2. </p> <ol> <li><p>Is my solution a heuristic or approximation?</p></li> <li><p>If I had a reason to believe that I will never overshoot the value of A[j] by +-x with this algorithm and can prove it, would then my solution be a heuristic or approximation?</p></li> </ol> <p>Is there any literature that deals with heuristic vs. approximation questions for P class problems where the solution can be achieved in polynomial time but the input is just too big for a poly time algorithm to be practical.</p> <p>thank you </p> https://cs.stackexchange.com/q/23651 8 Maximum Stacking Height Problem user16652 https://cs.stackexchange.com/users/0 2014-04-10T17:14:32Z 2014-06-09T18:58:41Z <p>Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it?</p> <blockquote> <p><strong>Problem ("Maximum Stacking Height Problem")</strong></p> <p>Given $n$ polygons, find their stable, non-overlapping arrangement that <strong>maximizes their stacking height</strong> on a fixed floor under the influence of gravity.</p> </blockquote> <p><br></p> <h2>Example</h2> <p>Three polygons:</p> <p><img src="https://i.stack.imgur.com/SbCt3.png" alt="enter image description here"></p> <p>and three of their infinitely many stable, non-overlapping arrangements, with different stacking heights:</p> <p><img src="https://i.stack.imgur.com/h938i.png" alt="enter image description here"></p> <p><br></p> <h2>Clarifications</h2> <ul> <li>All polygons have uniform mass and equal density</li> <li>Friction is zero</li> <li>Gravity is acting on every point into the downwards direction (i.e. the force vectors are all parallel)</li> <li>A configuration is not considered stable if it rests on an unstable equilibrium point (for example, the green triangle in the pictures can not balance on any of its vertices, even if the mass to the left and the right of the balance point is equal)</li> <li>To further clarify the above point: A polygon is considered unstable ("toppling") <em>unless</em> it rests on at least one point <em>strictly to the left</em> <strong>and</strong> at least one point <em>strictly to the right</em> of its center of gravity (this definition greatly simplifies simulation and in particular makes position integration etc. unnecessary for the purpose of evaluating whether or not an arrangement is stable.</li> <li>The problem in its "physical" form is a continuous problem that can only be solved approximately for most cases. <strong>To obtain a discrete problem that can be tackled algorithmically, constrain both the polygon vertices and their placement in the arrangement to suitable lattices.</strong></li> </ul> <p><br></p> <h2>Notes</h2> <ul> <li>Brute force approaches of any kind are clearly infeasible. Even with strict constraints on the placement of polygons inside the lattice (such as providing a limited region "lattice space") the complexity simply explodes for more than a few polygons.</li> <li>Iterative algorithms must bring some very clever heuristics since it is easy to construct arrangements where removing any single polygon results in the configuration becoming unstable and such arrangements are unreachable by algorithms relying on every intermediate step being stable.</li> <li>Since the problem smells at least NP- but more likely EXPTIME-complete in the total number of vertices, even heuristics would be of considerable interest. <strong>One thing that gives hope is the fact that most humans will recognize that the third arrangement in the example is optimal.</strong></li> </ul> https://cs.stackexchange.com/q/30778 7 Why is the A* search heuristic optimal even if it underestimates costs? statBeginner https://cs.stackexchange.com/users/22558 2014-10-09T05:19:00Z 2017-11-03T09:00:36Z <p>A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus on being admissible at the moment). </p> <p>But why does it always find the optimal solution if the heuristic underestimates? For example, if it underestimates a non optimal path by more than what it underestimates the optimal one, isn't that equivalent to over estimating?</p> https://cs.stackexchange.com/q/21758 7 What is the no free lunch theorem? Casebash https://cs.stackexchange.com/users/644 2014-02-18T10:48:00Z 2014-02-18T13:02:10Z <p>I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser exists". On the other hand, the <a href="https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization" rel="noreferrer">Wikipedia article</a> talks about 'candidate solutions" that are "evaluated one by one" - if we only consider algorithms of a particular form, then that is a much more limited claim.</p> <p>Can anyone explain what this theorem actually claims?</p> https://cs.stackexchange.com/q/1084 7 How to implement the details of shotgun hill climbing to make it effective? Sim https://cs.stackexchange.com/users/78 2012-04-06T19:13:39Z 2012-09-02T20:52:19Z <p>I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a <em>shotgun</em> (or <em>random-restart</em>) <a href="http://en.wikipedia.org/wiki/Hill_climbing" rel="nofollow">hill climbing</a> algorithmic idea seems to be the best fit, as I have no clue how the best start value can be found.</p> <p>But there is not a lot of information about this type of algorithm except the <a href="http://en.wikipedia.org/wiki/Hill_climbing#Variants" rel="nofollow">rudimentary idea</a> behind it:</p> <blockquote> <p>[Shotgun] hill climbing is a meta-algorithm built on top of the hill climbing algorithm. It iteratively does hill-climbing, each time with a random initial condition $x_0$. The best $x_m$ is kept: if a new run of hill climbing produces a better $x_m$ than the stored state, it replaces the stored state.</p> </blockquote> <p>If I understand this correctly, this means something like this (assuming maximisation):</p> <pre><code>x = -infinity; for ( i = 1 .. N ) { x = max(x, hill_climbing(random_solution())); } return x; </code></pre> <p>But how can you make this really effective, that is better than normal hill climbing? It is hard to believe that using random start values helps a lot, especially for huge search spaces. More precisely, I wonder:</p> <ul> <li>Is there a good strategy for choosing the $x_0$ (that is implementing <code>random_solution</code>), in particular knowing (intermediate) results of former iterations?</li> <li>How to choose $N$, that is how many iterations are needed to be quite certain that the perfect solution is not missed (by much)?</li> </ul> https://cs.stackexchange.com/q/19808 7 How does the 3-opt algorithm for TSP work? u3l https://cs.stackexchange.com/users/12945 2014-01-18T16:42:44Z 2016-10-26T23:09:02Z <p>I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers that mention that when three edges are removed, there remain only 2 possible ways to recombine the tour - this doesn't make sense to me.</p> <p>For example, I found a paper  that says:</p> <blockquote> <p>The 3-opt algorithm works in a similar fashion, but instead of removing two edges we remove three. This means that we have two ways of reconnecting the three paths into a valid tour1 (ﬁgure 2 and ﬁgure 3). A 3-opt move can actually be seen as two or three 2-opt moves.</p> </blockquote> <p>However, I count 3 different ways to reconnect the tour. What am I missing here?</p> <p>Also, can someone link me to an algorithm for 3-opt if possible? I'm just trying to understand it, but I haven't come across any clear algorithms yet: all resources I find simply say "remove three edges, reconnect them". That's it, which is sort of vague.</p> <p>Here are the 3 tours that seem to me to be 3-opt moves after removing three edges.</p> <p><img src="https://i.stack.imgur.com/KynPB.png" alt="enter image description here"></p> <hr> <ol> <li><a href="http://web.tuke.sk/fei-cit/butka/hop/htsp.pdf" rel="nofollow noreferrer">Heuristics for the Traveling Salesman Problem</a> by C. Nilsson</li> </ol> https://cs.stackexchange.com/q/3052 7 Problem similar to set packing charles.y.zheng https://cs.stackexchange.com/users/1937 2012-08-05T21:50:03Z 2012-09-04T04:54:39Z <p>Call a family of sets $\mathcal{F} = \{S_1, \dotsc, S_k\}$ "diverse" if each set $S_i \in \mathcal{F}$ has at least one unique element. What are possible approaches for finding the largest diverse set $S$ in a family of sets $\mathcal{F}$?</p> <p>One approach is to solve a modified set packing problem. Suppose $\mathcal{F}=\{S_1,\dotsc,S_k\}$. Let $K$ be a subset of elements, $K \subset \bigcup S_i$, and let $\mathcal{F}_{-K}=\{S_1 \setminus K,\dotsc, S_k \setminus K\}$. Then the maximal diverse set $S$ corresponds to the largest maximal set packing obtained from $\mathcal{F}_{-L}$ where $L$ is the set of all non-unique elements in $\mathcal{F}$.</p> <p>But, what's a good heuristic for choosing $K$? Or are there better approaches altogether?</p> https://cs.stackexchange.com/q/13453 6 Trying to improve minimax heuristic function for connect four game in JS Chad https://cs.stackexchange.com/users/9365 2013-07-26T14:27:09Z 2013-07-27T07:38:13Z <p>I have made a connect four game in JS and currently have a functioning minimax algorithm. The problem I'm having is that it is very, very easy to beat, even with a large depth. This is leading me to believe that I need a better heuristic function, but I cannot come up with much better than what I already have. So, I thought I would ask if anyone has any experience, or just a good idea, for a very good heuristic to use. I would also accept improvement ideas on my current heuristic below. Thank you in advance!</p> <p>EDIT: I'm going to go ahead and post my total minimax in here (3 functions total), because I have added disjoints and made my 4-in-a-row higher, but my AI is still terrible. I know my 2,3 and 4-in-a-rows work because I tested them, but I can't pin-point why I'm still having trouble even at high depths.</p> <pre><code> function getBestMove(currBoard,depth,who) { var opp; //Get opponent for next piece if(who == 'a') { opp = 'p'; } else { opp = 'a'; } var tBoard = new Array(rows); for(var i=0; i&lt;tBoard.length; i++) { tBoard[i] = new Array(cols); } var moves = new Array(aiOpenCols.length); //Drop each piece and use minimax function until depth == 0 for(var i=0; i&lt;aiOpenCols.length; i++) { for(var j=0; j&lt;rows; j++) { for(var k=0; k&lt;cols; k++) { tBoard[j][k] = currBoard[j][k]; } } tBoard = dropPiece(aiOpenCols[i],who,tBoard); moves[i] = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]); } var bestAlpha = -100000; //Large negative //Use random column if no moves are "good" var bestMove;// = Math.floor(Math.random() * aiOpenCols.length); //bestMove = +aiOpenCols[bestMove]; //Get largest value from moves for best move for(var i=0; i&lt;aiOpenCols.length; i++) { if(+moves[i] &gt; bestAlpha) { bestAlpha = moves[i]; bestMove = aiOpenCols[i]; } } bestMove++; //Offset by 1 due to actual drop function return bestMove; } function minimax(currBoard,depth,who,col) { //Drop current piece, called from getBestMove function currBoard = dropPiece(col,who,currBoard); //When depth == 0 return heuristic/eval of board if(+depth == 0) { var ev = evalMove(currBoard); return ev; } var alpha = -100000; //Large negative var opp; //Get opponent for next piece if(who == 'a') { opp = 'p'; } else { opp = 'a'; } //Loop through all available moves for(var i=0; i&lt;aiOpenCols.length; i++) { var tBoard = new Array(rows); for(var i=0; i&lt;tBoard.length; i++) { tBoard[i] = new Array(cols); } for(var j=0; j&lt;rows; j++) { for(var k=0; k&lt;cols; k++) { tBoard[j][k] = currBoard[j][k]; } } //Continue recursive minimax until depth == 0 var next = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]); //Alpha = max(alpha, -minimax()) for negamax alpha = Math.max(alpha, (0 - +next)); } return alpha; } function evalMove(currBoard) { //heuristic function //AI = # of 4 streaks + # of 3 streaks + # of 2 streaks - # of 3 streaks opp - # of 2 streaks opp var fours = checkFours(currBoard,'b'); //If win return large positive if(fours &gt; 0) return 100000; var threes = checkThrees(currBoard,'b') * 1000; var twos = checkTwos(currBoard,'b') * 10; var oppThrees = checkThrees(currBoard,'r') * 1000; var oppTwos = checkTwos(currBoard,'r') * 10; var scores = threes + twos - oppThrees - oppTwos; //If opponent wins, return large negative var oppFours = checkFours(currBoard,'r'); if(+oppFours &gt; 0) { return -100000; } else { return scores; } } </code></pre> https://cs.stackexchange.com/q/1579 6 Is using a more informed heuristic guaranteed to expand fewer nodes of the search space? Alexander Suraphel https://cs.stackexchange.com/users/1304 2012-04-29T19:28:57Z 2017-06-24T15:37:33Z <p>I'm reading through the <a href="http://www.cs.rmit.edu.au/AI-Search/Courseware/Slides1/" rel="nofollow">RMIT course notes on state space search</a>. Consider a state space $S$, a set of nodes in which we look for an element having a certain property. A <a href="http://www.cs.rmit.edu.au/AI-Search/Courseware/Slides1/07ImprovedMethods/07bHeurFunctions/" rel="nofollow">heuristic function</a> $h:S\to\mathbb{R}$ measures how promising a node is.</p> <p>$h_2$ is said to <em>dominate</em> (or to be more informed than) $h_1$ if $h_2(n) \ge h_1(n)$ for every node $n$. How does this definition imply that using $h_2$ will lead to expanding fewer nodes? - not only fewer but subset of the others.</p> <p>In Luger '02 I found the explanation:</p> <blockquote> <p>This can be verified by assuming the opposite (that there is at least one state expanded by $h_2$ and not by $h_1$). But since $h_2$ is more informed than $h_1$, for all $n$, $h_2(n) \le h_1(n)$, and both are bounded above by $h^*$, our assumption is contradictory. </p> </blockquote> <p>But I didn't quite get it.</p> https://cs.stackexchange.com/q/13219 6 Classification of job shop scheduling problems Martin Janiczek https://cs.stackexchange.com/users/9122 2013-07-11T03:03:06Z 2015-07-05T08:06:38Z <p>I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory.</p> <ul> <li>The factory has several types of machines (say, <code>locksmith, miller, welding</code>)</li> <li>There are few machines of each type. (say, <code>3 locksmiths, 2 millers, 3 welders</code>)</li> <li>There are several types of operations (some machines do more than one operation on the job, say, <code>locksmith does soldering and assembling</code>).</li> <li>The jobs on the machines have different times, all known beforehand.</li> <li>The jobs have dependencies on jobs done before (say, <code>a product's made of 10 screws and 4 subparts, each of which needs 4 screws</code>).</li> </ul> <p>From what I searched, this looks sort of like a Flow Shop problem. The difference is in the dependencies and in the same machine doing different operations with different times on a job.</p> <hr> <h2>My main question is:</h2> <p><strong>Is there some kind of a classification of these problems?</strong> A summary telling the differences?</p> <p>For example, I don't understand much of how do these differ: Open Shop, Job Shop, Flow Shop, Permutation Flow Shop. And whether or not I missed something similar that could fit better to my problem.</p> <hr> <p>As a side question, what approach do you think could help me best with the unusual requirements I've posted above? I'm writing my current approach below.</p> <p>So far I've been able to work with the tree of dependencies without regard to the makespan times: just making a plan - a list of IDs, really - of what comes after what, from looking at the tree of what's been done so far and what are the leaves (nodes having done all their dependencies).</p> <p>This allows for fast creation of meaningful individuals in the Genetic Algorithm population, but there seems to be no computationally cheap way to learn the individual's makespan time (which I have as the fitness function).</p> <p>For that I have to create a calendar, or Gantt chart, if you will, to which I put the operations on the jobs in the earliest place possible, in the machine queue that's free at that moment, etc. The whole plan has to materialize and that seems the most costly computation of the whole problem.</p> https://cs.stackexchange.com/q/9923 6 A Good Resource for Christofides' Heuristic user6422 https://cs.stackexchange.com/users/0 2013-02-19T06:37:03Z 2013-02-19T23:46:33Z <p>Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound?</p> <p>To be specific: (Disclaimer : I am an engineer who knows very little about graph theory but need this for a logistics course)</p> <ul> <li>I understand that I first create an MST. So far, so good.</li> <li>Now, I need to find a perfect minimum weight matching on all odd degree nodes. I have no clue what this is; googling this tells me this is a set of edges containing maximum $n/2$ edges such that no node is shared by 2 sets. I don't see why I am doing this..... I am not even sure I understand what this statement means.</li> <li>Now, I need to merge the MST and the matchings to create a "multigraph" and then find an Eulerian tour on this. No clue what I am doing here.</li> <li>Run the shortcut algorithm exploiting the triangle inequality. (No clue what happened till now and this obviously then makes no sense either)</li> </ul> <p>Can someone point me to a good resource with possible examples and illustrations for why Christofides works in a language that isn't full of graph theory terms (or alternately, provide me an answer here)?</p> <p>I have already looked at :</p> <ul> <li><a href="http://ieor.berkeley.edu/~kaminsky/ieor251/notes/2-16-05.pdf" rel="nofollow">A Berkeley PDF</a></li> <li>Wikipedia</li> </ul> https://cs.stackexchange.com/q/103610 6 Optimal partitioning of n-tuples Jendas https://cs.stackexchange.com/users/6541 2019-01-30T13:21:02Z 2019-02-02T08:05:15Z <p><strong>Motivation</strong> </p> <p>Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into solving the problem but I'm still unsatisfied with my solution.</p> <p><strong>Problem formulation</strong></p> <p>You are given a list of unique sets <span class="math-container">$X_1,\dots,X_n$</span>, each containing four integers. You are also given an integer <span class="math-container">$k$</span>. The goal is to partition the sets into <span class="math-container">$k$</span> groups, so that every group has between <span class="math-container">$0.8n/k$</span> and <span class="math-container">$1.2n/k$</span> sets, in a way that minimizes the number of different integers in each group. Formally, the goal is to find a function <span class="math-container">$f:\{1,\dots,n\} \to \{1,\dots,k\}$</span> that minimizes</p> <p><span class="math-container">$$\Phi(f) = \sum_j \left|\bigcup_{i \in f^{-1}(j)} X_i\right|.$$</span></p> <p><strong>Example</strong></p> <p>If instead of sets of four integers we considered sets of two integers, we could give the following example: for the sets</p> <pre><code>{1, 2}, {2, 3}, {1, 3}, {3, 4}, {4, 5}, {3, 5} </code></pre> <p>the optimal partitioning for <span class="math-container">$k=2$</span> would be <code>{1, 2}, {2, 3}, {1, 3}</code> and <code>{3, 4}, {4, 5}, {3, 5}</code> with unique elements <span class="math-container">$|\{1, 2, 3\}|=3$</span>, <span class="math-container">$|\{3, 4, 5\}|=3$</span> and <span class="math-container">$\Phi = 6$</span>.</p> <p><strong>My attempts so far</strong></p> <p>So far I've attempted to solve this problem by modeling it as a graph partitioning problem and using <a href="http://algo2.iti.kit.edu/kahip/" rel="nofollow noreferrer">KaHIP</a> library to do the computation. I thought of two methods of how to model this problem as a graph.</p> <ol> <li>Each set is a vertex, and we have an edge between two vertices if they share an integer. The number of shared integers determines the weight of the edge. The graph partitioning tool then directly yields some solution to our problem.</li> <li>Each unique integer that occurs in any set is a vertex, and we put an edge between two integers if they are both contained in the same set. The number of such cases determines the weight of the edge. Having the integers partitioned like this we can assign each set a partition of some of its integers. Resulting partitions can be too large, but that can be resolved by applying the first approach to these now relatively small partitions.</li> </ol> <p>The first model in my case turned out to be very space-consuming. I have approximately 2 millions of these sets and the first model produced over 74M edges. The second approach helps a great deal and yields results of similar quality.</p> <p>The problem is that neither of these models is the exact model of my original problem. Notably, the number of cut edges will not correspond with the number of duplicated integers across partitions. Can you think of a better graph model or an altogether different approach to this problem that would yield better results? </p> https://cs.stackexchange.com/q/65600 5 Heuristic algorithms for the dense assignment problem nbubis https://cs.stackexchange.com/users/23263 2016-11-05T18:52:29Z 2016-11-05T19:49:24Z <p>Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or variants.</p> <p>However, if $n$ is large, $O(n^3)$ may not be feasible from a timing perspective. Moreover, storing the complete $n^2$ cost matrix may require a prohibitive amount of memory.</p> <p>Are there heuristic algorithms that give "good enough" solutions, with are significantly faster? I have seen some algorithms that claim to be faster, but they assume the number of edges is smaller than $O(n^2)$, which is not true in the dense case.</p> https://cs.stackexchange.com/q/71424 5 Heuristic Repair and N-Queens Problem Regan Koopmans https://cs.stackexchange.com/users/61268 2017-03-12T06:47:45Z 2017-03-12T06:47:45Z <h1>Problem:</h1> <p>I am trying to solve the $N$-Queens problem using <strong>Constraint Satisfaction</strong> and <strong>Heuristic Repair</strong> (also known as <strong>Min-Conflicts</strong>). I wrote a program to do this for any given $N$ queens and $N * N$ board.</p> <p>I observed that a solution should be found in $N$ passes or less (since we need to find $N$ non-conflicting locations, for which we might need to rearrange all queens at most $N$ times in one pass).</p> <p>I noticed that, given a random start, some starting states would not be able to resolve to a solution. This was due to circular behaviour where two or three queens would alternate positions, always moving to positions where:</p> <p>$$conflict(new-pos) \le conflict(old-pos)$$ </p> <p>but never decreasing global conflicts.</p> <p>The presence of these states seems to increase as $N$ increases. So 64-queens seems more likely to have "cycles" than 4-queens (which never seems to have cycles).</p> <p>I would like to know how I can reason about these difficult states, and what extension of the algorithm could be made such that the algorithm will always obtain a solution, provided one exists?</p> <h1>What I have tried so far:</h1> <ul> <li>I have tried to randomise the board state after $N$ unsuccessful passes. This probably guarantees an <em>eventual</em> solution, but does not solve the fact that the likelihood of these states seems to increase exponentially, and so a solution becomes intractable quickly. </li> </ul> <p>For those interested you can find my program <a href="https://github.com/Regan-Koopmans/n-queens/blob/master/src/main.rs" rel="noreferrer">here</a>. It is not fantastically documented, but it is not terribly long, and I believe most of the names are self-documenting.</p> https://cs.stackexchange.com/q/70128 5 How to apply ant colony optimization to the TSP but repeating nodes and edges Fylux https://cs.stackexchange.com/users/66149 2017-02-10T10:33:58Z 2017-02-16T16:01:14Z <p>I'm learning the <a href="https://en.wikipedia.org/wiki/Ant_colony_optimization" rel="nofollow noreferrer">Ant Colony Optimization Algorithm</a> and I would like to apply it to a variation of the <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">TSP problem</a> (find the path that start from a node, crosses all nodes and finish in the initial node) where you can cross a node or edge more than once. Actually, my problem wouldn't have solution for the TSP because some nodes only have one edge.</p> <p>Basically, I see two problems:</p> <ol> <li><p>In most of examples I've seen, nodes are represented by (X,Y) positions and they suppose that is a complete graph, so from every node you can go to every node, which involves that an ant will always have a edge to go to a node that hasn't been visited yet. But in this problem, it may happen that an ant arrives to a node where al the adjacents nodes have already been visited, so, how would it decide the way to go? The worst case would be that there is only one node left to visit and it is the one farthest from the current node.</p></li> <li><p>What repeating edges involves to pheromones. If and edge is crossed several times in the tour, it could or could not have much more pheromones, depending on the implementation, and I'm not sure if it could have a negative impact.</p></li> </ol> <p>This is a very simple example, where red edges mean that the cost is 1 and blue that is very big, for example 20. As you can see for the best path you need to repeat edges.</p> <p><a href="https://i.stack.imgur.com/NoiTW.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NoiTW.jpg" alt="enter image description here"></a></p> <p>Regards.</p> <p>EDIT2:</p> <p>I want to add that my particular problem has around 1000 nodes and 2000 edges.</p> <p>I have some new ideas. First of all it looks like I must have a way to find the distance and the path between cities, so that each ant can decide which is the next city to go. The main option is the <a href="https://en.wikipedia.org/wiki/Johnson&#39;s_algorithm" rel="nofollow noreferrer">Johnson's Algorithm</a> which offers good performance for this sparse graph.</p> <p>To store all the possible paths I could use a triangular matrix where each element is a vector of nodes. If we suppose that the mean of the paths is 50 nodes (represented with 2 bytes integers) the memory needed would be around (N: nº nodes) N*N/2*50*2 bytes so more or less 50Mb.</p> <p>The other option is to have the same structure but in each element of the matrix I would have only one node, and to find the path I would have to access the position of that node and so on until I find the one I'm looking for. Because if the shortest path from node A to node C crosses B, the path is the shortest path from A to B joined with the one from B to C. This option need N*N/2*2 bytes more or less 1Mb. But it will probably have worse performance because it needs much more access to memory and I doesn't take advantage of space locality so it will have many cache misses.</p> <p>About ACO, maybe I can use an algorithm like <a href="https://en.wikipedia.org/wiki/Minimum_spanning_tree" rel="nofollow noreferrer">Minimun Spanning Tree</a> or something like that to put some extra initial pheromones, but I'm not sure if that will be positive.</p> https://cs.stackexchange.com/q/63955 5 Why are the conditions for optimality different for A* tree and graph search? Conor Igoe https://cs.stackexchange.com/users/58968 2016-09-27T12:23:28Z 2016-09-28T00:05:13Z <p>I am unclear as to why the conditions for optimality for A* search are different for graph search and tree search. When discussing conditions for optimality for A* search in Russell and Norvig's <em>Artificial Intelligence: A Modern Approach</em> they say:</p> <blockquote> <p>The first condition we require for optimality is that $h(n)$ be an admissible heuristic. </p> <p>...</p> <p>A second, slightly stronger condition called <strong>consistency</strong> (or sometimes <strong>monotonicity</strong>) is required only for applications of A* to graph search.</p> </blockquote> <p>Why is consistency only required for A* graph search and not A* tree search? Why are the conditions for optimality different for the two types of search?</p> https://cs.stackexchange.com/q/37795 4 Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'? justin https://cs.stackexchange.com/users/21045 2015-01-31T06:43:57Z 2017-10-17T08:04:56Z <p>Consider two heuristics $h_1$ and $h_2$ defined for the 15 puzzle problem as:</p> <ol> <li>$h_1(n)$ = number of misplaced tiles</li> <li>$h_2(n)$ = total Manhatten distance</li> </ol> <p><img src="https://i.stack.imgur.com/0TKFh.png" alt="15 Puzzle"></p> <p>Could anyone tell why $h_2$ is a better heuristic than $h_1$? I would like to know why the number of nodes generated for $h_1$ is greater than that for $h2$. Also why going deeper into the state space the number of nodes increase drastically for both heuristics.</p> <p>Source: <a href="http://1drv.ms/1zpYA3l" rel="nofollow noreferrer">Informed Search</a></p> https://cs.stackexchange.com/q/20126 4 A heuristic for finding a maximum disjoint set Erel Segal-Halevi https://cs.stackexchange.com/users/1342 2014-01-30T18:29:37Z 2016-01-30T02:56:54Z <p><strong>Background</strong></p> <p>I need to find a largest set of non-overlapping axis-parallel squares, out of a given collection of candidate squares.</p> <p>This problem is NP-complete. Many papers suggest approximation algorithms (see <a href="https://en.wikipedia.org/wiki/Maximum_disjoint_set" rel="nofollow">Maximum Disjoint Set in Wikipedia</a>), but I need an exact algorithm. </p> <p>My current solution uses the following divide-and-conquer strategy:</p> <ul> <li>Calculate all horizontal and vertical lines that pass through corners of the candidate squares. Each such line separates the candidates into three groups: candidates that are entirely at one side of the line, candidates that are entirely at the other side of the line, and candidates that are intersected by the line. Now there are two cases: <ul> <li><em>Easy Case</em>: There is a separator line $L$ that does not intersect any candidate square. Then, recursively calculate the maximum-disjoint-set among the squares on one side of $L$, recursively calculate the maximum-disjoint-set among the squares on the other side of $L$, and return the union of these two sets. The separator line guarantees that the union is still a disjoint set.</li> <li><em>Hard Case</em>: All separator lines intersect one or more candidate squares. Select one of the separator lines, $L$; suppose that $L$ intersects $k$ squares. Calculate all $2^k$ subsets of these intersected squares. For each subset $X$ that is in itself a disjoint set, calculate the maximum-disjoint-set recursively as in the Easy Case, under the assumption that $X$ is in the set. I.e., recursively calculate the maximum-disjoint-set among the squares on one side of $L$ that do not intersect $X$, recursively calculate the maximum-disjoint-set among the squares on the other side of $L$ that do not intersect $X$, and calculate the union of these two sets with $X$. Out of all $2^k$ unions, return the largest one.</li> </ul></li> </ul> <p><strong>Question</strong></p> <p>My question is: <em>What is the best way to select the separator line $L$</em>?</p> <p>There are two conflicting considerations: On one hand, we want $L$ to intersect as few squares as possible, so that the power set is not too large. On the other hand, we want $L$ to separate the candidate squares to subsets of balanced size, preferrably equal size, so that the recursion ends as fast as possible. What is the best way to balance these conflicting considerations?</p> <p>EDIT: <strong>Additional details</strong></p> <p>My current heuristic is to pick the separator line that intersects the least number of squares. This heuristic allows the algorithm to process input sets with up to $n=30$ candidates, in several seconds. The optimal solution in these cases has about 10 squares. In general, the number of squares in the optimal solution is near $2\cdot\sqrt{n}$.</p> <p>When the input grows beyond 30 candidates, the running time becomes much slower (several minutes and more). My goal is to find a heuristic that will allow me to process larger sets of candidates.</p> https://cs.stackexchange.com/q/2120 4 Forward checking vs arc consistency on 3-SAT Mark https://cs.stackexchange.com/users/1556 2012-05-28T07:03:31Z 2017-04-17T17:38:59Z <p>If I were to let the variables be the propositions and, constraint be all clauses being satisfied, which technique would be more effective in solving 3-SAT? <a href="http://en.wikipedia.org/wiki/Look-ahead_%28backtracking%29#Look_ahead_techniques" rel="nofollow">Forward checking</a> or <a href="http://en.wikipedia.org/wiki/Arc_consistency#Arc_consistency" rel="nofollow">arc consistency</a>? From what I gathered forward-checking is $O(n)$, while Arc consistency is about $O(8c)$ where c is the number of constraints (According to this <a href="http://www.cs.ubc.ca/~kevinlb/teaching/cs322%20-%202006-7/Lectures/lect11.pdf" rel="nofollow">page</a>). So perhaps forward -checking is faster somehow? How should I determine which to use?</p> https://cs.stackexchange.com/q/37940 4 Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$ fiftyeight https://cs.stackexchange.com/users/26638 2015-02-04T02:46:21Z 2015-12-15T19:15:28Z <p>I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their weights is maximum (The weights are positive), under the constraint that every pair is not connected by an edge, i.e $\forall\ v_i,v_j \in S:(v_i,v_j) \not\in E$.</p> <p>A common problem instance would be a graph with around $2 \times 10^5$ nodes, up to around $5 \times 10^5$. The degree of a node is bounded by ~$100$, and the number of edges will be around $10^6$.</p> <p>Can anyone recommend a heuristic algorithm for finding a near-optimal solution? A runtime of hours or even days is acceptable.</p> <p>I've been looking so far at articles about Tabu search and that is the current direction I am going towards.</p> https://cs.stackexchange.com/q/79811 4 Does this A-Star heuristic already exist? Narrateur du chaos https://cs.stackexchange.com/users/75825 2017-07-29T22:43:39Z 2018-11-20T13:43:02Z <p>I've been thinking about <a href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="nofollow noreferrer">the A* algorithm</a> recently. For context, A* is a graph-navigating algorithm most often used to solve problems that go "What is the shortest path from point A to point B?". It's based on a distance-estimating heuristic you provide to it. The heuristic you provide must be able to tell the program, for any given position: 'This position is <em>at least</em> this far away from the destination'. The most simple heuristic being to use Pythagoras's theorem to get the distance "as the crow flies" between said point and a destination.</p> <p>Now, the thing that interested me is that A* efficiency is tied to the preciseness of your 'getMinDistance' function. If it returns a value too low, the algorithm takes longer. If it returns a value too high, A* may return a non-optimal path. If it always returns 0, you have Dijkstra's algorithm. (also the heuristic must be monotonic, read the wikipedia articles for more details)</p> <hr> <p>The heuristic I thought about goes like this:</p> <ul> <li><p>Using any method of your choosing, split the graph into regions. Designate a node of each region as the region's center (ideally, its centroid). The graph traversal distance between any node and its region's center should be trivially computable (or cached).</p></li> <li><p>Store the exact graph traversal distance between the centers of every single region. If you have N regions, you should end up with N² distances.</p></li> <li><p>For any two points A and B, and their respective region's centers Ra and Rb, the graph traversal distance AB is superior or equal to <code>RaRb - (RaA+RbB)</code></p></li> </ul> <p>The smaller the regions are, the closer this heuristic gets to the actual traversal distance AB.</p> <hr> <p>My questions are:</p> <ul> <li><p>Is this algorithm actually admissible? I have no idea how to formally prove it.</p></li> <li><p>How efficient is this heuristic? My guess would be "Very if you have a lot of small groups, because A* only examines nodes within the groups that include the optimal path", but again, I'm not sure it's true and I don't know how to prove it.</p></li> <li><p>Was this idea ever published before? If so, what is it called and where can I read about it?</p></li> <li><p>In the same vein, are there video games which are known to use this heuristic?</p></li> </ul> https://cs.stackexchange.com/q/81939 4 Comparing A* search to Simulated Annealing noob https://cs.stackexchange.com/users/78044 2017-10-01T20:24:59Z 2018-03-31T23:22:32Z <p>Good Afternoon,</p> <p>I am comparing A* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my answer, and was wondering if someone could give me some input.</p> <p>A*: Optimal, finds path of shortest distance to goal state based on heuristic. </p> <p>SA: Complete, stochastic, randomly selects next state and either rejects/accepts based on change in energy state. If it is a bad move (less energy than previous state) then it either accepts/rejects based on probability. </p> <p>Now, I understand that A* requires bookkeeping in order to track the path from goal state to start state. This is why I think that the memory requirements would be linear, where there are n nodes in the path from start to finish. </p> <p>On the other hand SA doesn't require bookkeeping, since it's trying to find the state with the maximum "energy". Could someone explain exactly what "energy" would mean? Also, I am confused about comparing the functions of these two algorithms. A* is good at finding the path to a goal state (which is already known) with the lowest cost, whereas SA only finds a state that is most desirable. what is the point of comparing A* to SA when they seem to have two different purposes?</p> https://cs.stackexchange.com/q/57549 4 Evolutionary algorithm in stochastic environment madison54 https://cs.stackexchange.com/users/0 2016-05-14T14:23:15Z 2016-05-17T08:55:57Z <p>Consider the following model problem:</p> <p>I want to use an <strong>evolutionary algorithm</strong> to optimize the starting point of particles for which it is apriori clear where they would start in state space, but not <strong>when</strong>. Once a particle is placed, it is part of the dynamics, which is <strong>stochastic</strong>, i.e. whether certain particles interact is modeled by a random variable. A <em>mutation</em> of the evolutionary algorithm corresponds to slightly changing the time when the particle is introduced in the system.</p> <p>I have now two choices: </p> <p>1) I let the stochastic dynamics evolve <em>while</em> the evolutionary algorithm is optimizing, i.e. after every mutation I <em>draw</em> a new interaction environment from the distribution. That means, the algorithm is evaluating every situation with a different environment (drawn from one fixed distribution).</p> <p>2) I draw an interaction pattern for every particle <em>apriori</em> to have one fixed environment (we assume they can be drawn independently). Then I let the algorithm optimize my problem in that deterministic environment. I do that for <em>several</em> environments and take some statistic over the solution. </p> <p>Does someone have experience with those two approaches and can tell me their advantages and disadvantages from a practical point of view?</p> https://cs.stackexchange.com/q/12310 4 How approximate are "approximate" nearest neighbor (ANN) search algorithms? friedmud https://cs.stackexchange.com/users/8395 2013-05-27T20:13:40Z 2013-05-28T17:44:30Z <p>Starting to use <a href="https://code.google.com/p/nanoflann/" rel="nofollow">nanoflann</a> to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are.</p> <p>If I have a (more or less) randomly distributed point cloud what is the likelihood that I get the exact nearest neighbor given a target point within the clouds bounding box? I know that it is dataset dependent... but does anyone have a good numerical study somewhere that shows trends?</p> https://cs.stackexchange.com/q/102110 4 Heuristics vs meta-heuristics vs hyper-heuristics? user626625 https://cs.stackexchange.com/users/97876 2018-12-28T06:45:45Z 2019-06-20T03:51:12Z <p><a href="https://en.wikipedia.org/wiki/Metaheuristic" rel="nofollow noreferrer">The wikipedia page on <strong>meta</strong>-heuristics</a> states that they are "heuristics designed to find, generate, or select a heuristic".</p> <p><a href="https://en.wikipedia.org/wiki/Hyper-heuristic" rel="nofollow noreferrer">The wikipedia page on <strong>hyper</strong>-heuristics</a> states that they are "heuristic search methods that seeks to automate [...] the process of selecting, combining, generating or adapting several simpler heuristics".</p> <p>Moreover, it also states that "The fundamental difference between <strong>metaheuristics</strong> and <strong>hyper-heuristics</strong> is that most implementations of metaheuristics search within a search space of problem solutions, whereas hyper-heuristics always search within a search space of heuristics."</p> <p><strong>This leaves me confused</strong>: it seems like the hyper heuristic page is contradicting the meta-heuristic page. How can a meta-heuristic search for heuristics, if its search space is the problem space rather than the space of heuristics?</p> <p><strong>What really is the difference between metaheuristics and hyperheuristics?</strong></p>