Skip to main content
14 votes

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 ...
Carlos Linares López's user avatar
9 votes
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 ...
John L.'s user avatar
  • 39k
8 votes
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 ...
D.W.'s user avatar
  • 161k
6 votes
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 ...
Carlos Linares López's user avatar
6 votes
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.
J. Schmidt's user avatar
5 votes

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') $$...
dtt's user avatar
  • 558
5 votes
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 ...
aelguindy's user avatar
  • 1,807
5 votes

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, ...
Stuart Robertson's user avatar
5 votes
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 ...
Sriram's user avatar
  • 275
4 votes

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 ...
Mo Azim's user avatar
  • 41
4 votes

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 "...
elkrari's user avatar
  • 71
4 votes

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 ...
Carlos Linares López's user avatar
4 votes
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 ...
Caleb Stanford's user avatar
4 votes
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 "...
LighT's user avatar
  • 103
4 votes
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 ...
DirkT's user avatar
  • 991
3 votes

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)...
elkrari's user avatar
  • 71
3 votes
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 ...
D.W.'s user avatar
  • 161k
3 votes

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'...
Aayush Kucheria's user avatar
3 votes
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 ...
Ori's user avatar
  • 146
3 votes

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 ...
ratchet freak's user avatar
3 votes
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 ...
Philippe Olivier's user avatar
3 votes
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....
Philippe Olivier's user avatar
3 votes

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. ...
ratchet freak's user avatar
3 votes
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 ...
Juho's user avatar
  • 22.6k
3 votes
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$...
John L.'s user avatar
  • 39k
3 votes

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 ...
Yuval Filmus's user avatar
3 votes

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 ...
j_random_hacker's user avatar
3 votes
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 &...
D.W.'s user avatar
  • 161k
3 votes

One-dimensional packing problem: Optimal decomposition of music structure

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)$ ...
Steven's user avatar
  • 29.5k
3 votes

What is a heuristic in human computer interaction?

you might aswell ask this qustion over at https://ux.stackexchange.com/. But you are a CS guy so you probably didn't touch that UX part yet. Heuristics as defined by Nielson et al. can be used to ...
htho's user avatar
  • 131

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