Most of you heard about ‘Seven Millennium Prize Problems’ established by (The Clay Mathematics Institute of Cambridge) with $1 million allocated to the solution of each problem. It seems that one of these problems was solved by professor (Lizhi Du), Wuhan University of Science, China.
I read his article a year ago, but could not decipher the logic of the algorithm (and for sure, I doubted the real success). Later I tried to implement the algorithm but after some efforts gave up. Later I tried to implement the algorithm but after some efforts gave up. Unfortunately the author does not open his C++ code.
There is a great advantage of being a teacher – you can give a task to a student, and if he is happened to have exceptional mind (moreover, a great patience, belief in his own abilities, belief that a teacher does not doubt a success), then you can win. And this happened to me and my student Ivan Federov. He worked very hard for a month (or more), putting aside all other obligations and finally succeeded. He managed to get the logic of written words (description of the algorithm that you can find using the link above) and convert it to a working code. But first, you should be sure that solution is possible.
The main idea of prof. Lizhi Du’s approach is to present a graph (any undirected graph) as a ring of nodes (see Fig.1) and try to mend ‘the breaks’ in successive chain of nodes. A break (or breakpoint by the author’s terminology) is the absense of the edge between two neiboring nodes (along the ring chain).
If you will manage to mend all the breaks, then Hamiltonian cycle is found. It is just the succession of your ring nodes. Long ago I developed an app that allows to redraw any graph in a RingView fashion and drag its nodes all over. If you try (using the application which acompinies this article) to intuitively drag the nodes of some graph trying to mend all the breaks, quite often you will succeed.
See Fig.2 where one break’was mended by dragging down the node #8 (compare Fig.1 and Fig.2).
Fig 3. shows the final result of mending all the breaks by dragging several nodes. Compare Fig.3 and Fig.1. Pay attention on numbers of the nodes. Consider the fact that while dragging, you don’t change the graph structure (or adjacency matrix). As you see all the breaks were mended and now we have a Hamiltonian cycle (it is the list of all the nodes while moving along the ellipsoidal ring).
This kind of exercises made me beleive that prof. Lizhi Du’s approach is quite reasonable. Showing this trick to Ivan Federov (my student) made him beleive that solution is near. All you have to do is to convert intuitive dragging manipulations to some strict programming logic. Oh, don’t forget to use the description of the Lizhi Du’s algorithm on several pages of PDF document.
Inspired by this logic Ivan started working. The resulting code turned out to be very impressive in a sense that it worked! But it was not so good in a sense that it was compressed into two big functions with many repetitions and very-hard-to-follow logic. After two days pondering over the problem and wrestling with the code, I hope the code became more readable and manageable. Now it is encapsulated in a class that has 8 methods, each implementis a separate step of the algorithm. The code works a little faster than the original (two functions approach).
Points of Interest
Even now I am not sure that can clearly explain all the magic (especially the logic of methods named TrySecond, TryThird and CutAndInsert). I think I perceived and can explain the rotational technique used to change the graph structure, but nevertheless I am not 100% sure that I could explain all the actions. Ivan says that he shares my opinion in spite of the fact that it was he who resurrected the code from honest but rather verbose Lizhi Du document (see the link to his article above).
Data files have an extension ‘*.gv’ (GraphView Files). It is the simplest format (the list of adjacent nodes for each of the graph nodes). If you change the filter in OpenFileDialog to ‘*.hcp’, you can open many of the existing in the net graph files. The format of such files is very simple — a list of edges (pairs of connected nodes). I placed only one such a file in Data folder of the project.
While playing with the application, first open a file (Ctrl+O) with the small digit prefixes and try to use older known algorithms (Posa, Roberts and Flores, Recursive Backtracking). They were implemented by me several years ago. By the way, Posa’s algorithm not always finds the solution, for it selects nodes randomly (description of algorithm is here). Try it several times on simple graphs and it sometimes will find a solution (may be different each time). More capabale, but not so fast, is the algorithm created by Roberts and Flores (you may find its description in the net). It surely will find a Hamiltonian cycle or will give a message that one does not exist.
You can circularly toggle the currently selected algorithm by pressing right arrow key. Press space to start the search. You also can see the inner cooking (details) of searching algorithm by setting a delay of animation (use toolstrip button with the tooltip: Change Animation Delay). Don’t forget to set the delay time to zero when you open some bigger graphs (the files, after 09 Knight.gv). This graph corresponds to the famous Knight’s tour problem which is shown in Wikipedia. In order to see the essense of Lizhi Du’s algorithm (and the purpose of this article) do the following steps:
- Open the file 09 Knight.gv,
- Select the algorithm RobertsFlores
- Clear the delay (use button Change Animation Delay).
- Press space and drink some coffee. Computer will be busy for several hours. Finding a solution will require more than 780 millions steps.
- After coffee pause, stop the algoritm (use toolstrip button Stop the search).
- Select the algorithm LizhiDu and press spacebar.
The solution will be found instantly (if you did not forget to clear the delay). The algorithm will require only 234 steps. That’s fantastic!
If the Math community will adopt the professor Lizhi Du’s proof of the solution of P vs NP Problem, then as (the authorities warn us), all Public Key RSA cryptosystems will go down. Should it be troubling news for us? I don’t know, I always neglected security problems. The mathematicians must invent something new.