- 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?"