# Questions tagged [heuristics]

Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.

203 questions
Filter by
Sorted by
Tagged with
1k views

### Heuristics for the $n$-puzzle

An admissible heuristic for an n-puzzle is the Manhattan distance. Now if the cost of a transition is equal to the number of the piece that is moved, is it true that the Manhattan distance is still an ...
478 views

### Simulated Annealing for graph coloring

I am working on a simulated annealing algorithm for graph coloring. The model I follow is the following: http://riad.pk.edu.pl/~zk/pubs/PPAM07_2.pdf. I have troubles understanding the cooling schedule ...
137 views

### Path cover with paths of bounded length, in the plane

I have a weighted, undirected, Euclidean complete graph $G$, a special vertex $r$, and an upper bound $b$. I want to find a minimum-cost path cover that covers all vertices of $G$, subject to the ...
135 views

### Why max heuristic is inacurrate?

H_max() algorithms work by considering a state in the planning graph, and using all applicable actions to make every atom in that state true. The h_max() for a given state is the cost of the most ...
488 views

### How to tell if a Heuristic is monotonic

I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,...
497 views

### Heuristic algorithms for the dense assignment problem

Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or ...
1k views

### Implement multi-fragment heuristics for the traveling salesman problem

I would like to implement the multi-fragment heuristics algorithm for finding a solution to the traveling salesman problem. The algorithm is described here as follows: This seriation method re-...
2k views

### Prove consistency of maximum of two consistent heuristic functions?

Suppose we have two heuristic functions $h_1$ and $h_2$ which are both consistent, that is, $$h_i(n) \leq c(n,a,n') + h_i(n')\qquad \ i\in\{1,2\}\,,$$ where $c(n,a,n')$ denotes cost of reaching the ...
513 views

### Why are the conditions for optimality different for A* tree and graph search?

I am unclear as to why the conditions for optimality for A* search are different for graph search and tree search. When discussing conditions for optimality for A* search in Russell and Norvig's ...
4k views