A stupid thought about Hamilton Path problem - Theory

The flaw seems to be that only two-vertex swaps are not sufficient. For
example, a three-vertex swap:

s -...-> i -...-> j -...-> k -...-> t
=>
s -...-> j -...-> k -...-> i -...-> t

is not accomplishable by a series of two-vertex swaps.



On Dec 4, 5:04 am, "Booted Cat" <yaoziy...{}> wrote:
> Hamilton Path: to find a shortest path in graph G from vertex s to
> vertex t through all the other vertices once and only once.
>
> My thought:
>
> First find a random path P from s to t.
>
> Then do this loop until no change happens in a pass:
>
> Do
> For Each vertex pair i, j, (note that i and j are not necessarily
> adjacent vertices)
> if a swap of i and j in path P can lead to a shorter path, then
> swap them and the new path becomes P
> Loop
>
> Any counterexample to this algorithm?
>
> Regards,
> Yao Ziyuan

On 3 Dec 2006 13:04:13 -0800, "Booted Cat" <yaoziyuan{}>
wrote:

>Hamilton Path: to find a shortest path in graph G from vertex s to
>vertex t through all the other vertices once and only once.
>

For definition of Hamiltonian path look here

http://en.wikipedia.org/wiki/Hamiltonian_path


>My thought:
>
>First find a random path P from s to t.
>
>Then do this loop until no change happens in a pass:
>
>Do
> For Each vertex pair i, j, (note that i and j are not necessarily
>adjacent vertices)
> if a swap of i and j in path P can lead to a shorter path, then
>swap them and the new path becomes P
>Loop
>
>
>Any counterexample to this algorithm?

Run google on Travelling Salesman Problem. You can start from here

http://en.wikipedia.org/wiki/Traveling_Salesman_Problem

and check teh section "iterative improvement"

A.L.

Forgot Wikipedia is one's friend...

On Dec 4, 7:20 am, A.L. <alewa...{}fala2005.com> wrote:
> On 3 Dec 2006 13:04:13 -0800, "Booted Cat" <yaoziy...{}>
> wrote:
>
> >Hamilton Path: to find a shortest path in graph G from vertex s to
> >vertex t through all the other vertices once and only once.For definition of Hamiltonian path look here
>
> http://en.wikipedia.org/wiki/Hamiltonian_path
>
> >My thought:
>
> >First find a random path P from s to t.
>
> >Then do this loop until no change happens in a pass:
>
> >Do
> > For Each vertex pair i, j, (note that i and j are not necessarily
> >adjacent vertices)
> > if a swap of i and j in path P can lead to a shorter path, then
> >swap them and the new path becomes P
> >Loop
>
> >Any counterexample to this algorithm?Run google on Travelling Salesman Problem. You can start from here
>
> http://en.wikipedia.org/wiki/Traveling_Salesman_Problem
>
> and check teh section "iterative improvement"
>
> A.L.

On 3 Dec 2006 16:11:56 -0800, "Booted Cat" <yaoziyuan{}>
wrote:

>Forgot Wikipedia is one's friend...

That what?...

A.L.

> The flaw seems to be that only two-vertex swaps are not sufficient. For
> example, a three-vertex swap:
>
> s -...-> i -...-> j -...-> k -...-> t
> =>
> s -...-> j -...-> k -...-> i -...-> t
>
> is not accomplishable by a series of two-vertex swaps.
>
Huh?

xijky
xjiky
xjkiy

Because in order to successfully swap i and j, the pairwise swap must
lead to a shorter path; and this may not be satisfied.

On Dec 6, 11:13 pm, "d...{}comcast.net" <d...{}comcast.net> wrote:
> > The flaw seems to be that only two-vertex swaps are not sufficient. For
> > example, a three-vertex swap:
>
> > s -...-> i -...-> j -...-> k -...-> t
> > =>
> > s -...-> j -...-> k -...-> i -...-> t
>
> > is not accomplishable by a series of two-vertex swaps.Huh?
>
> xijky
> xjiky
> xjkiy

Booted Cat wrote:
> Because in order to successfully swap i and j, the pairwise swap must
> lead to a shorter path; and this may not be satisfied.

Shorter path? You didn't give them lengths.

It gets worse. You stated the key step of the algorithm:

if a swap of i and j in path P can lead to a shorter path

What does that mean? "Can lead to a shorter path" does not
necessarily mean that the immediately resulting path is shorter.

Plus, as A.L. pointed out, "Hamiltonian path" means, as near as
anyone can tell, the same problem as "Hamiltonian Circuit".
Shorter? What does that even have to do with the problem?


--
--Bryan

Bryan Olson wrote:
....
> What does that mean? "Can lead to a shorter path" does not
> necessarily mean that the immediately resulting path is shorter.
....

This is the essential problem, so far, with hill-climbing approaches to
NP-complete problems. They tend to have local optima, where any single
small change makes things worse, but improvement would be possible with
a large change.

Patricia

On Thu, 07 Dec 2006 13:04:13 GMT, Patricia Shanahan <pats{}acm.org>
wrote:

>Bryan Olson wrote:
>...
>> What does that mean? "Can lead to a shorter path" does not
>> necessarily mean that the immediately resulting path is shorter.
>...
>
>This is the essential problem, so far, with hill-climbing approaches to
>NP-complete problems. They tend to have local optima, where any single
>small change makes things worse, but improvement would be possible with
>a large change.
>
>Patricia

Don't pay attention, someone Booted Cat generates nonsense not only
in this thread but also in others

A.L.