20 votes
Accepted

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

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 ...
user avatar
12 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 ...
user avatar
9 votes
Accepted

Given two heuristic values how do I tell which one is admissible?

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 ...
user avatar
  • 808
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 ...
user avatar
  • 140k
7 votes
Accepted

Aren’t most constraining variable and least constraining value the exact opposite?

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 ...
user avatar
  • 32.9k
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.
user avatar
5 votes
Accepted

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

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 ...
user avatar
  • 140k
5 votes
Accepted

What makes a metaheuristic meta?

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 ...
user avatar
  • 29.1k
5 votes
Accepted

Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

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 ...
user avatar
  • 22k
5 votes
Accepted

Algorithm A vs Algorithm A*: What's the difference?

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....
user avatar
5 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 ...
user avatar
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 ...
user avatar
  • 1,777
4 votes
Accepted

Ant colony optimization for continuous functions

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 ...
user avatar
4 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, ...
user avatar
4 votes
Accepted

Why do heuristic functions only approximate the real value of the cost?

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 ...
user avatar
  • 808
4 votes
Accepted

Heuristic for sokoban puzzle problem

Hi there CoderInNetwork, That ain't an easy question and any advances regarding a good heuristic function would be very welcome. Indeed, I will refer in my answer to Andreas Junghanns' PhD written in ...
user avatar
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 ...
user avatar
  • 41
4 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') $$...
user avatar
  • 548
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 "...
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 ...
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 ...
user avatar
  • 5,144
3 votes
Accepted

How can I fill bookcases with shelves of books using the least number of bookcases?

I'm not clear on whether you have one bookcase or multiple bookcases, so I'll explain how to handle both cases below. Multiple bookcases If you have multiple bookcases, and you need to put each ...
user avatar
  • 140k
3 votes
Accepted

Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

A* expands the search tree by expanding the node for which the past cost ($d(n)$; cost of path from the start point to the node) plus the heuristic value ($h(n)$) is minimum. Because the heuristic $h(...
user avatar
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'...
user avatar
3 votes
Accepted

Longest Path A*, Admissible Heuristics, and Optimalness

It seems to me (and correct me if I'm wrong) that a regular A* algorithm would work absolutely fine with your problem. The problem is that you're confused about the word underestimates. When we're ...
user avatar
  • 146
3 votes
Accepted

Is there a name for algorithms which detect nearly-similar structures?

The search terms you're probably looking for are "similarity measure", "dissimilarity", "distance function", or "metric"... applied to trees. One approach to your probem is to invent a similarity ...
user avatar
  • 140k
3 votes

Monotone property of heuristic in $A^*$ algorithm

When is a node visited twice? Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$. ...
user avatar
  • 674
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 ...
user avatar
  • 140k
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)...
user avatar
  • 71
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 ...
user avatar
  • 146

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