What is the best heuristic for solve problems not based in cartesian coordinates?, for example in the travelling salesman problem, in whichyou have only the value of the distance between cities.

Well, the purpose of the heuristic is to estimate the cost to move from one state to the next. In the traveling salesman problem, you already have that cost expressed as a distance, so you could just use a lookup table.

maybe I am confused in terms, what I want is the estimated cost to go from one node, to the goal node.

I want to use:
g = estimated cost to the end (this is what I don''t know how to get)
h = distance between one node, and the following
f = g + h

You''re right, my mistake. Not sure what I was thinking. Sorry, I really don''t have any idea how to help =-/

By convention, actually, h is the estimated cost to the end (from Heuristic), and g is the distance travelled so far from the start node.

I don't know if A* is the most accurate algorithm to use for such a problem. I think you're better of using Dijkstra, and it's even simpler.

But, if you really want to know the cost from start to goal, you can use the Roy-Floyd algorithm:
considering that COST is the cost matrix between cities, where COST(i,j) is the cost between city i and city j, and COST(j,i) is the cost from city j to city i (not necessarily the same as from i to j if you don't want to - maybe a city is uphill, the other downhill ), and
N is the number of cities:

int i, j, k;
for (k = 0; k < N; k++)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (COST(i,k) + COST(k,j) < COST(i,j))
// if we find a city k trough wich going from
// i to j has a lower cost than the
// already known cost from i to j...

COST(i,j) = COST(i,k) + COST(k,j);
// then that is the lowest known
// cost so far from i to j

It's pretty simple, I doubt you didn't know this. And now, after applying this algorithm on the COST matrix, you transformed it from the matrix with the cost from going directly from i to j, to the matrix where COST(i,j) is the lowest known cost of travelling through some cities or directly from i to j. So now, COST(i,j) is your exact h from city i to city j, any city i or j you want.
NOTE: As you can see, in the first COST matrix, when there isn't a road between two cities, the cost should be pretty high, teoretically infinite. This was just an example, you should handle this special case better. And be careful, you still need the first matrix to calculate g.

But I still think Dijkstra is the best for this problem.

Is this what you asked?

[edited by - madu on July 14, 2003 4:15:51 PM]

>

[edited by - KV on July 14, 2003 5:46:20 PM]

I don''t understand too good what you told, madu, but I think that is not what I want, I have posted the graph, the cost g between cities is the only data avaliable, then I have to use an heuristic method that tell me the estimated distance between any node and the goal node. In the draw, the start node is A, and the goal node is F, I know that the h value of the goal node should be 0, and the value of h for the rest of nodes > 0. How the nodes aren''t determinded by an x,y coordinates, I can''t use Manhatthan, line distance ... heuristic methods.

Thanks for your replys

I forgot to tell that I want to use A* to solve it, not Dijkstra or other methods, and that the heuristic have to be admisible (if not it would be A alhorithm, not A*)

Judging from your graph picture, where all the cities are linked together, isn't h the direct distance from each node to F?
But suppose that the graph is not that simple and the nodes are not all linked together.
The heuristic (h) is supposed to be an estimated distance from a node to a goal. But here you have nothing to estimate. You have to calculate it. So you reduce the problem of estimating h to calculating the shortest distance between points (distance, not path yet, although I think you could in the process).

(A)
| | \5
10 | \ 20
| (C)------------(E)
|
(B)------(D)
16

E is the final node :h = 0, C: h = 20, A: H = 25; B: h = 35; D: h = 51;

Sorry for using parantheses instead of brackets for the matrix, but gamedev has some weird format tags. See?

1. Build the distance (cost) matrix:

const int infinite = 999999999;
int COST(max,max);

COST matrix:

A B C D E

A | 0 10 5 i i |
B |10 0 i 16 i |
C | 5 i 0 i 20 |
D | i 16 i 0 i |
E | i i 20 i 0 |

where i is infinite

2. Apply Roy-Floyd to calculate the shortest distances:

int i, j, k;
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if ((COST(i,k) != infinite) && (COST(k,j) != infinite))
if (COST(i,k) + COST(k, j) < COST(i, j))
COST(i,j) = COST(i,k) + COST(k,j);

3. COST(i,j) is now the h from i to j
H is the exact cost between cities, so it is admisible.

This is the only way i can think of for calculating h.

I don't know how you store the distances between nodes, how many nodes you have or anything else for that matter about your problem.

Sorry if I couln't help you!
Crap, this formating! There goes all my beautiful artwork!

[edited by - madu on July 14, 2003 6:57:14 PM]

now I understand you , its a good way and I''ll try to test it.
I have to tell you that the graph is suposed to be all interconnected, but path like A to F would be greater (long distance) than others like B to D, by this way, the shortest path could be for example ABEF, althought can be seem that is AF.