# Tag Info

19

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 ...

16

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....

12

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 ...

12

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

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 ...

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 ...

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

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^*(... 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 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 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

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

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

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 ...

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

There probably will be no formal proof; probably the only way to tell which is better is through experiments. But some intuition seems possible. $h_1$ only takes into account whether a tile is misplaced or not, but it doesn't take into account how far away that tile is from being correct: a tile that is 1 square away from its ultimate destination is ...

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

Both A and A* algorithm use a best-first search to find the least cost path from a start state to a goal state. Best-first search applies a heuristic evaluation on the states to find the 'best' state. Consider the evaluation function f, f(n) = g(n) + h(n) where g(n) measures the cost of reaching any state n from the start state and h(n) is a heuristic ...

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. 5 Yes, these two heuristics does sound like inconsistent. Most Constrained Variable (MCV) (also called MRV for Minimum Remaining Values) tries to reduce the size of the next branch to search while Least Constraining Values tries to enlarge the size of the next branch to branch. However, if you take a close a look, they both serve the same goal, which is, given ... 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

No, discretizing solution space is not necessary I read page 14 of paper you provided and then went googling. I found this 2014 paper: A unified ant colony optimization algorithm for continuous optimization that mentioned a bit of history of ACO on continuous function. Tracing from that, I think the best paper to begin is this 2008 paper Ant colony ...

4

It is true that if it underestimates a non-optimal path by more than it underestimates the optimal one, then it will explore down those paths before exploring down the optimal one. What is important, and this is what admissibility guarantees, is that while it is exploring down those non-optimal paths it will not find the goal and finish the search before ...

4

If you create a heuristic that returns the exact cost for each node in the search tree, you can find the optimal solution easily: Start at the initial state and generate all successor states. Take the state with the best heuristic value and repeat, until you find the goal state. Because the estimated cost (from the heuristic) for each node in the search tree ...

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