- hello,

I am asking "why is there a requirement for a complete graph?"

kind regards/chenyu

--- In aima-talk@yahoogroups.com, "Brandon Corfman" <bcorfman@a...>

wrote:> Are you asking "why is there a requirement for a complete graph?"

wrote:

> or "why is the check-tsp-map function called where it is?"

>

> Brandon

>

> --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...>

> > Hello,

every

> > I am studying "/search/domains/tsp.lisp" source code, which is

> > about "Travelling salesperson Problem".

> >

> > In the source code, there is a requirement to the city map,

> that's,

> > the map should be complete graph. Every city is connected to

> > other city, in the function ( check-tsp-map?).

> >

> > I don't know why the requirement should be added here? What's the

> > reason behind it. Could you help me?

> >

> >

> > Thank you for your attention.

> > kind regards/chenyu - A TSP does not require a complete graph, but it becomes more difficult

to solve it otherwise**. For instance, a fast but effective algorithm

like 2-Opt (that hill-climbs by inverting subsequences along the path)

would be rendered ineffective if the graph was not complete. You would

have to start checking constraints on the path at each exchange, which

requires different techniques (perhaps a constraint satisfaction

problem).

Best regards,

Brandon

** Source: Michalwicz, Zbigniew and Fogel, David B.; How to Solve It:

Modern Heuristics, Springer-Verlag, 1999.

--- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...> wrote:

> hello,

> I am asking "why is there a requirement for a complete graph?" - I understand your meaning now. Thank you very much.

Best regards/chenyu

--- In aima-talk@yahoogroups.com, "Brandon Corfman" <bcorfman@a...>

wrote:> A TSP does not require a complete graph, but it becomes more

difficult

> to solve it otherwise**. For instance, a fast but effective

algorithm

> like 2-Opt (that hill-climbs by inverting subsequences along the

path)

> would be rendered ineffective if the graph was not complete. You

would

> have to start checking constraints on the path at each exchange,

which

> requires different techniques (perhaps a constraint satisfaction

It:

> problem).

>

> Best regards,

> Brandon

>

> ** Source: Michalwicz, Zbigniew and Fogel, David B.; How to Solve

> Modern Heuristics, Springer-Verlag, 1999.

wrote:

>

>

> --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...>

> > hello,

> > I am asking "why is there a requirement for a complete graph?"