# Tag Info

24

In general, this is a very relevant and interesting research question. "One way is to run existing solvers..." and what would this even tell us exactly? We could see empirically that an instance seems hard for a specific solver or a specific algorithm/heuristic, but what does it really tell about the hardness of the instance? One way that has been pursued ...

18

A* maintains a priority queue of options that it's considering, ordered by how good they might be. It keeps searching until it finds a route to the goal that's so good that none of the other options could possibly make it better. How good an alternative might be is based on the heuristic and on actual costs found in the search so far. If the heuristic ...

12

If the heuristic function is not admissible, than we can have an estimation that is bigger than the actual path cost from some node to a goal node. If this higher path cost estimation is on the least cost path (that we are searching for), the algorithm will not explore it and it may find another (not least cost) path to the goal. Look at this simple example....

11

So it seems you are intrigued about the relationship between the informedness of a heuristic function and its pruning power. This is a well-known relationship established in the literature from the 80s (see for example Pearl, Judea. Heuristics, Addison-Wesley, 1984 who, by the way, has been awarded this year with the Alan Turing award). As you already ...

11

To proof the statement in your question, let us proof that consistency implies admissibility whereas the opposite is not necessarily true. This would make consistency a stronger condition than the latter. Consistency implies admissibility: Let me start by emphasizing that $h(t)=0$ if the heuristic function $h$ is admissible (where $t$ is a goal) since edge ...

10

A heuristic is essentially a hunch, i.e., the case you describe ("I noticed it is near", you don't have a proof it is so) is a heuristic. As is solving the traveling salesman problem by starting at a random vertex and going to the nearest not yet visited each step. It is a plausible idea, that should not give a too bad solution. In this case, it can be shown ...

10

In searching around for an online presence for one of the classics in this field (Coffman, Denning: Operating Systems Theory, Prentice Hall, 1983) I came upon what looks like a comprehensive textbook with a Google books preview Pinedo: Scheduling: Theory, Algorithms, and Systems, Springer 2008. The author's homepage also has pages devoted to each of his ...

10

The No Free Lunch theorem (NFL) was established to debunk claims of the form: My optimisation strategy X is always best. In particular, such claims arose in the area of genetic/evolutionary algorithms. The statement is, roughly: every optimisation strategy performs badly on many problems. Therefore, there can be no always-best strategy and your claim ...

9

As noted by Thomas Klimpel in the comments, a certain acceptance probability is often used, which is equal to say $0.8$. The following is a simple iterative method to find a suitable initial temperature, proposed by Ben-Ameur in 2004 [1]. In the following, $t$ is a strictly positive transition, $\max_t$ and $\min_t$ are the states after and before the ...

8

The general idea behind doing multiple climbs is to try to avoid local optima. This is the reason shotgun climbing might work better than just a plain hill climbing method. Usually one starts with a random value. On the other hand if one can guess something better, that can be used as a initial value as well. If there is no knowledge of what a good start ...

8

I think this is a very good question. You could also ask: when to use a SMT solver? I have a feeling it might be hard to determine before modeling the problem and actually running the CSP/SAT/SMT solvers and finding out. It is well known that even different solvers perform very differently on the same instances! My intuition also comes from the fact that ...

8

Some ILPs can be solved rapidly (to an exact solution) in practice; some cannot. Usually when we are talking about solving an ILP, we are looking for an exact solution, though some ILP solvers can find an approximate solution as well (find the best solution they can within the time constraints). There are no hard-and-fast rules. Of course, ILP is NP-hard, ...

7

While Anton's answer is absolutely perfect let me try to provide an alternative answer: being admissible means that the heuristic does not overestimate the effort to reach the goal, i.e., $h(n) \leq h^*(n)$ for all $n$ in the state space (in the 8-puzzle, this means just for any permutation of the tiles and the goal you are currently considering) where $h^*(... 7 Consider a ladder a----b----c | | | d----e----f Say length of a-b is$2$and length of a-d is$1$. The optimal route is a-b-c-f-e-d-a,$10$units long. Starting at a, NN would produce a-d-e-b-c-f-a which is$7 + \sqrt{17} > 11$units long. There is actually a four node example, a rhombus A /|\ B-+-C \|/ D Say length of B-C is$10$, length ... 7 A heuristic function$h$is admissible, if it never overestimates the cost for any given node. Formally speaking, let$h^{*}$map each node to its true cost of reaching the goal. The heuristic function$h$is admissible, if for all nodes$nin the search tree the following inequality holds: \begin{align} h(n) \leq h^*(n). \tag{\star} \end{align} That ... 6 All white tiles must be moved all the way to the left. Call the left most position 0. Then, in the final position, the sum of white distances from the axis is 0+1+...(N - 1). Calculate this value, the "solution distance" of the tiles up front. As a heuristic, add the zero-based positions of white tiles up, and subtract from this sum the "solution ... 6 Both forward checking (FC) and arc consistency (AC) are methods of inference. Regardless of the problem you are solving, choosing a specific method of inference is always a tradeoff. Basically, the more you are willing to pay in terms of time, the more you gain in terms of strength of inference. So yes, it is faster to perform forward checking than arc ... 6 In the long run, it's really better to understand the graph theory terminology, but for now, here is an explanation of Christofides's algorithm. I'm not an expert in this area so I can't offer much by way of intuition. Also, I should note that by now, better algorithms are known for some variants, see for example the recent survey by Vygen. We denote the ... 6 You can see this very interesting answer about Heuristic in Wikipedia: " a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow. The objective of a heuristic is to produce quickly enough a solution that is good enough for solving the problem at hand. ". Heuristic could derive from theory or experimental ... 6 Connect 4 is a solved game - under perfect play, white wins. Victor Allis's thesis contains a winning algorithm for white. The game had been solved a few weeks earlier by James D. Allen. Later on, John Tromp came up with a strategy that will win the game from any position, if possible, and thus solved the game strongly. 6 You missed the footnote — these ways are "not including the connections being identical to a single 2-opt move". Indeed, there are only two permutations inS_3$without fixed points (also known as derangements), namely$(123)$and$(132)$. More generally, for a$k$-opt move it is enough to consider permutations without fixed points, since those with$...

5

Disclaimer: I'm assuming your minimax works perfectly and your logic of who wins when and when to apply your heuristic how is sound (mainly because you only gave part of your program and partly because it's been a while since I last implemented one of these, so I won't exactly know what to look for) and thus I'm only commenting on your heuristic. Don't ...

5

Most beginners in the field see heuristics construction more as an art than a science. While I am not claiming here that there is a truly scientific (or even computable) method to derive them, I am sure they are not an art and we know about specific procedures to derive them (some of which are truly computable). In any case, we do not consider the ...

5

Rather than your approach, I suggest you formulate this as an integer linear program and feeding it to an off-the-shelf ILP solver. Alternatively, formulate it as a SAT problem and feed it to a SAT solver: you'll probably need to take the decision problem version, where you ask whether there exists a subset of $k$ non-overlapping squares, and then use ...

5

Unfortunately, (weighted) maximum independent set is very hard to approximate. You might be able to do a bit better if you can analyze the graphs in your application (perhaps they are not truly arbitrary). In any case, luckily your graphs are quite small (200 thousand vertices or so). A naive algorithm (say a greedy one) will run quite fast, but might be ...

5

The distinguishing factor is that meta-heuristics are problem independent. Look at something like Travelling Salesman. You have 2-OPT, 3-OPT, Nearest Neighbour heuristics. These are all things that really don't carry much meaning outside the specific problem of Travelling Salesman. A Meta-heuristic, on the other hand, assumes no prior knowledge of the ...

5

This paper has a painfully detailed table on what you can achieve using (currently known) deterministic, randomized and $\epsilon$-approximation algorithms. To summarize, for the bipartite case (all assuming integer weights bounded by $N$): Deterministic time $O(n^2 \sqrt n \log N)$. Randomized $O(n^{2.373} N)$. $(1 - \epsilon)$-approximation in $O(n^2 \... 5 I think I understand now after trying some examples as Yuval Filmus suggested. In the example below, we can get stuck on the local optimum using 2-opt, but as we can see the global optimum is better. 4 As for your last question, there is no separate theory for approximation algorithms for problems that are solvable in polynomial time. In fact, it might be that$\mathsf{P}=\mathsf{NP}$. Some examples of approximation algorithms for problems in$\mathsf{P}\$ include algorithms for numerical linear algebra and computational geometry. See the question ...

4

The following answer is to give an intuition of how a situation can look that fails. Karolis Juodelė's answer is much better than this, but I find the following example to give a nice intuition. Let's say that we look for shortest TSP path, and not cycle, with predefined starting vertex, consider the graph below with X being the starting vertex, one dash ...

Only top voted, non community-wiki answers of a minimum length are eligible