Tag Info

How does consistency imply that a heuristic is also admissible?

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 ...
• 3,463
Accepted

Arenâ€™t most constraining variable and least constraining value the exact opposite?

Yes, these two heuristics 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 ...
• 39k
Accepted

Are there practical methods for solving ILP?

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 ...
• 161k
Accepted

Are depth-first/breadth-first considered special cases of best-first?

The answer to your question is, in both cases, No. The reason is as follows: Both depth-first search and breadth-first search are uninformed search algorithms. A distinctive feature of these ...
• 3,463
Accepted

Why doesn't 2-opt return an optimal solution?

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

Prove consistency of maximum of two consistent heuristic functions?

Proof (Show consistency property of $h_3$): $$h_3(n) = \max(h_1(n), h_2(n)) \\ \leq max(h_1(n')+c(n,a,n'), \ h_2(n')+c(n,a,n')) \\ \leq \max(h_1(n'), \ h_2(n')) + c(n,a,n') = h_3(n') + c(n,a,n')$$...
• 558
Accepted

Heuristic algorithms for the dense assignment problem

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 ...
• 1,807

Why is the A* search heuristic optimal even if it underestimates costs?

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

Applicability of approximation algorithms vs meta-heuristics in practice

Well, practitioners, as far as I have noticed, do not show a very stark difference between heuristics and approximation algorithms. The upside that the approximation algorithms community provides with ...
• 275

Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'?

The current answers are good, but I think I have a simpler way to understand it. The Manhattan Distance heuristic approximates the actual distance better than the misplaced tiles heuristic. So, you ...
• 41

Implement multi-fragment heuristics for the traveling salesman problem

there are almost no other information regarding this algorithm online [...] I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm. I invite you to read my paper "...
• 71

Heuristics for the $n$-puzzle

First of all, a heuristic is said to be admissible if and only if $h(n)\leq h^*(n)$ for every state $n$, where $h(n)$ is your heuristic function and $h^*(n)$ is the cost of an optimal path from $n$ to ...
• 3,463
Accepted

Warnsdorff's rule: more errors with odd sized boards

For odd-sized boards, a knight's tour must start and end on the same color as the corner squares of the board. It follows that for about half (50%) of starting squares, there is no possible knight's ...
• 7,088
Accepted

Difference between cost and the heuristic function in A* search

Necessary heuristic function is needed for 2nd image, I can't tell why it's so in that image. But for the common A star algorithm, heuristic is an "Oracle" that guide algorithm to make "...
• 103
Accepted

How far out can one determine a program is halting?

What you are describing is indistinguishable from: making a (free) copy of the Turing machine (in its current state) running it for $n$ steps seeing if it halted. I fail to see how this gives you ...
• 991

Is a two-opt move guaranteed to produce a non-worse tour?

2-Opt is a move that doesn't guarantee to give a better tour. We use such moves ($k$-Opt, swap, insertion,..) in local searches to look for a better tour in the neighbor of the input (which is a tour)...
• 71
Accepted

Find a string that covers many sets of binary strings with don't-cares

Your problem is NP-hard. It's basically a variant of SAT. You shouldn't expect any algorithm that is provably efficient. Instead, I recommend you use an off-the-shelf SAT solver; since your problem ...
• 161k

How does an admissible heuristic ensure an optimal solution?

I'd like to expand upon Anton's comment in his answer, and provide an explicit answer to the situation posed by Ashwin in the comments. I think it'll be helpful to answering the primary question. Let'...
Accepted

Does this A-Star heuristic already exist?

This idea is called True Distance Heuristics and as you suspected, it can be very efficient. True Distance Heuristics True Distance Heuristics (as well as "Pattern Database") is a technique ...
• 146

Best heuristic for A*?

The best possible heuristic for A* is the actual length of the shortest path to the target that way A* can always select the next node in the optimal path. This is usually not possible to get so a ...
• 4,506
Accepted

Greedy Heuristic for the Traveling Salesperson Problem

First let's name your points $P_A$, $P_B$, $P$, $P_C$, and $P_D$ (from left to right). With the first heuristic you start at one point ($P$) and move to the closest point. From that new point, you ...
Accepted

How does the nearest insertion heuristic for TSP work?

I think that by "insertion heuristic" you mean "nearest insertion heuristic". If this is the case, here is how it works: We're looking to construct a cycle $C$ containing all the nodes of our problem....

Choosing heuristic for A* algorithm where cost is less than absolute distance

The simple options are to either multiply all path costs such that minimum cost is 1. Or multiply the heuristic such that the min cost is more or equal than the heuristic tells you for the same path. ...
• 4,506
Accepted

Overall time complexity of Heuristical Algorithm for travelling salesman problem [TSP]

Any algorithm that first does $A$ of work and then $B$ of work will have done a total of $A+B$ of work. It doesn't matter what the algorithm is, or what $A$ or $B$ are. You might be getting confused ...
• 22.6k
Accepted

Does an optimal path imply the heuristic is admissible?

No. Let us consider an extreme example. Let graph $G$ contain only two nodes, the starting node $s$ and the destination node $t$. The distance of edge $(s,t)$ is 1. We have a heuristic function $h$...
• 39k

Greedy Heuristics with an Altered Subset Sum/Partition Problem

Suppose that a set $S$ of size more than 2 can be partitioned into two subsets of identical sum. One of these subsets contains at least two elements. If you merge these two elements (that is, replace ...
• 278k

Algorithm to create dense style crossword puzzles

There may simply be no solution to some of these problem instances. And the fact that the problem is NP-hard means that you cannot expect to find any efficient algorithm to find solutions for large ...
• 5,479
Accepted

How important is initial state for local search optimisation?

A good initial state can often be helpful. I would guess that there is a significant chance that spending extra time to find a good initial state will be useful. All we can say in general is that &...
• 161k
If $n'$ is the number of groups, this problem admits no $2^{o(n')}$-time algorithm for any choice of a constant $\epsilon > 0$, unless the exponential time hypothesis (ETH) fails. Let $G = (V, E)$ ...