Re: TSP and A-star

On Jan 31, 4:00 am, king...@xxxxxxxxxxx wrote:
Hi to all,

how would you model the state space of a Traveling Salesman Problem in
order to use the A* algorithm?

Use the Held-Karp lower bound as your estimator. It won't be fast.

I have in mind only one representation:
1]
Represent all possible permutations of the number 1..n, where n is the
number of the cities, with a tree. See for example http://www.techuser.net/randpermgen.html

The tree has n! leaves, so the representation should probably be
implicit, rather than explicit.

.

Relevant Pages

  • LOS Optimization Using Binary Tree Structures (with demo)
    ... fast way to calculate LOS using a binary tree (properly called a binary ... describe the visibility-dependency between tiles - as in describing ... Using octants ... The cool thing about using a relational-based LOS algorithm is that you ...
    (rec.games.roguelike.development)
  • Re: How come Ada isnt more popular?
    ... beneficial for the memory-management aspect of such an algorithm. ... When the GC hits it just traverses the tree ... E.g a chess playing program (any ... Furthermore generational garbage collection AFAIK has ...
    (comp.lang.ada)
  • Re: Question about decision tree algorithm in sqlserver2000
    ... If your target, on the other hand, is continuous, the algorithm will build regression trees that have regression formulae in nodes and leaves. ... if your target is continuous (i.e. a regression tree) than the lift chart is replaced by a scatter plot ...
    (microsoft.public.sqlserver.datamining)
  • Re: Question about decision tree algorithm in sqlserver2000
    ... if my target is discrete, the algorithm will ... build a classification tree. ... if your target is continuous (i.e. a regression tree) than the lift chart is replaced by a scatter plot ...
    (microsoft.public.sqlserver.datamining)
  • Ultimate, God-like Algorithm
    ... An infinite tree is described by including "self references" in place ... self reference makes the tree infinite. ... believe that I have an algorithm that can show equality in m * n time. ...
    (sci.math)