# Tag Info

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

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

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

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

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

### 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')$$...

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

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