optimal way in graph? - Graphics

CC.TUDresden@gmail.com schrieb:
> want to find a way from a start vertice to visit the other vertices in
> a graph.
> constraints:
> 1. a way with min. edges
This ist the travelling salesman problem which is NP complete. Look at
http://www.ameisenalgorithmus.de/
> 2. need not to visit all the vertices of this graph, but the unvisit
> vertices should have max. 2 edges to one of the visited vertices on
> this way
>

Steffen Koehler 写道：

> CC.TUDresden@gmail.com schrieb:
> > want to find a way from a start vertice to visit the other vertices in
> > a graph.
> > constraints:
> > 1. a way with min. edges
> This ist the travelling salesman problem which is NP complete. Look at
> http://www.ameisenalgorithmus.de/
> > 2. need not to visit all the vertices of this graph, but the unvisit
> > vertices should have max. 2 edges to one of the visited vertices on
> > this way
> >

but this is not a salesman problem, while the vertices can be visited
many times, and the edges have the same length, the vertices can only
visit its neighbor vertices

<CC.TUDresden@gmail.com> wrote in message
news:1156506126.828145.166490@m79g2000cwm.googlegroups.com...

> but this is not a salesman problem, while the vertices can be visited
> many times, and the edges have the same length, the vertices can only
> visit its neighbor vertices

Is it a special tree you are trying to build?

Uffe Kousgaard 写道：

> <CC.TUDresden@gmail.com> wrote in message
> news:1156506126.828145.166490@m79g2000cwm.googlegroups.com...
>
> > but this is not a salesman problem, while the vertices can be visited
> > many times, and the edges have the same length, the vertices can only
> > visit its neighbor vertices
>
> Is it a special tree you are trying to build?

it is a ad-hoc network, like a mesh topology. e.g.the salesman visits a
vercites 4 edges away, he must travel through 3 vertices, can not
direct visit the distination