Site Map Guestbook News Support Download / Purchase Efficiency Testlab About

Examples of Calculation Procedures
Company
Feedback
PCGrates
PCGrate-S(X) Series
PCGrates Screenshots
PCGrates Examples
Our Customers
NP-Complete Problems
Traveling Salesman Problem
Hamiltonian Cycle Problem
NP-Complete Problems Screenshots
NP-Complete Problems Examples
References
Introduction:
This page demonstrates a few examples of step-by-step calculations (under a Microsoft® Windows® 32/64-bit operation system) of different Hamiltonian cycle and optimal tour problems taken from...
more...
Example 1: ALB1000 with 25 random tests
The step-by-step instruction for unzipping the HCP_Solver package, running calculations for the above listed graph, and saving the results of testing is as follows:
more...
Example 2: {7,8}-leaper on a 15x106 board with 2 random tests
The step-by-step instruction for unzipping the HCP_Solver package, generating the LEAPER_7_8_15_106 example, running the process of calculation for the above listed graph, and saving the results of testing is as follows:
more...
Example 3: USA Map with 10 Random Tests
The step-by-step instruction for unzipping the TSMP-1 package, running calculations for the above listed tour and saving the results of testing is as follows:
more...
Example 4: 70-city Problem (Smith/Thompson) from TSPLIB with 3 Random Tests
The step-by-step instruction for unzipping the TSMP-1 package, running calculations for the above listed tour and saving the results of testing is as follows:
more...
 
This page demonstrates two examples of step-by-step calculation (under a Microsoft® Windows® 32/64-bit operation system) of different Hamiltonian cycle problems taken from the famous Internet library TSPLIB at http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/. The first one is a common graph “ALB1000.hcp” and the second one is a “{7,8}-leaper on a 15x106 board” graph obtained with the use of the LEAPER generator (TSPLIB/HCP). Both examples have the same TSPLIB-format (hcp-type) and Hamiltonian cycles. The Hamiltonian cycles are found using our HCP Solver, while the results (Hamiltonian tours) as well as the initial graphs can be viewed through the WinHcp32 graphical viewer. For the graphs tested you can use any numbers of randomly generated initial cycles. General data on each example and test results are stored in a special text file. Information on generating a leaper file, on finding Hamiltonian cycles, and on viewing graphs for the examples described is included in this instruction.  
This page demonstrates also two examples of step-by-step calculations (under a Microsoft® Windows® 32/64-bit operation system) of the precise determination by the polynomial method (see General Information/Preface) of the length and path of different minimal (or maximal, see the Maximum Route option description) Hamiltonian cycles of weighed networks (the Traveling Salesman Problem, the TSMP) taken from: (1) searching for a minimal route through a current set of 50 USA capital cities and Washington DC; (2) searching for a minimal tour for the 70-city problem (Smith/Thompson) from the famous Internet library TSPLIB at http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/index.html (st70.tsp). Both examples have input and output data in TSPLIB formats (map- or tsp- type) and text formats. The Hamiltonian cycles are found using our TSMP-1 Solver; the results (optimal tours) as well as the initial graphs can be viewed through our graphical viewer (see Figure 10). For the graphs tested you can use any numbers of randomly generated initial cycles. General data on each example and test results are stored in text files.  
 
On our website at http://www.pcgrate.com/about/npcomprb/hcp or at http://www.pcgrate.com/about/npcomprb/tsp you can find more computation examples using the HCP and TSMP-1 programs with data files, plots and tables.  
Back to the Top
1. ALB1000 with 25 Random Tests  
 
The step-by-step instruction for unzipping the HCP_Solver package, running calculations for the above listed graph, and saving the results of testing is as follows:  
  • Unzip files from the “HCP_Solver.zip” archive into the main “HCP_Solver” directory.  
  • Run Command Prompt application using the “Start Menu\All Programs\Accessories\Command Prompt” command.  
  • Choose the main “HCP_Solver” directory using, for example, the command “cd c:\...\HCP_Solver”.  
  • Run the “HCP.exe” command to see information about using the HCP Solver.  
  • Run HCP Solver to find a Hamiltonian cycle in the “ALB1000.hcp” graph for 25 random tests using the “hcp.exe ALB1000.hcp 25” command. The string “Hamiltonian cycle problem solver” appears and calculation starts.  
  • To save the results of calculation for a future analysis, rename the current “HCP.txt” file with the default name from the main “HCP_Solver” directory into, for example, a “HCP_ALB1000.txt” file.  
During the calculation you can track the status information about the solution process in the strings. If you would like to stop the calculation, press the combination “Ctrl-C”. After completing the calculation, you can see the results of testing for 25 tests and different times for the solving process in the Command Prompt window. General statistical data for this example and its test results are stored in the “HCP.txt” file (see Figure 8). The Hamiltonian cycle thereby obtained is stored in the “ALB1000.tou” file (as an example, see Figure 7).  
 
The step-by-step instruction for downloading graphical views of the input graph and of its Hamiltonian cycle is as follows:  
  • Run the “WINHCP.exe” command to open the WinHcp32 application.  
  • Choose the “File\Open\ALB1000.hcp” item in the main menu of the WinHcp32 application and click the “Open” button in the “Open” dialog window. You can see a graphical view of the “ALB1000.hcp” example with a default cycle {1,2,3,4,...1000} (see Figure 3).  
  • Choose the “View\Rearrange cycle” item in the main menu or click the “Rearrange cycle” button on the main toolbar of the WinHcp32 application.  
  • Click the “Browse” button in the “Rearrange cycle” dialog window and then choose the “ALB1000.tou” file in the “Open” dialog window from the main “HCP_Solver” directory.  
  • Click the “OK” button in the “Rearrange cycle” dialog window (see Figure 3). You can see a graphical view of the “ALB1000.hcp” example with a Hamiltonian cycle {328,287,288,28,...327} (see Figure 4).  
 
Back to the Top
2. {7,8}-leaper on a 15x106 Board with 2 Random Tests  
 
The step-by-step instruction for unzipping the HCP_Solver package, generating the LEAPER_7_8_15_106 example, running the process of calculation for the above listed graph, and saving the results of testing is as follows:  
  • Unzip files from the “HCP_Solver.zip” archive into the main “HCP_Solver” directory.  
  • Run the Command Prompt application using the “Start Menu\All Programs\Accessories\Command Prompt” command.  
  • Choose the main “HCP_Solver” directory using, for example, the “cd c:\...\HCP_Solver” command.  
  • Run the “LEAPER.exe” command to see information about using LEAPER.  
  • Run the “LEAPER 7 8 15 106” command to generate the “LEAPER_7_8_15_106.hcp” graph.  
  • Run the “HCP.exe” command to see the information about using HCP Solver.  
  • Run HCP Solver to find a Hamiltonian cycle in the “LEAPER_7_8_15_106.hcp” graph for 2 random tests using the “hcp.exe LEAPER_7_8_15_106.hcp 2” command. The “Hamiltonian cycle problem solver” string appears and the calculation starts.  
  • To save the results of calculation for further analysis, rename the current “HCP.txt” file with the default name from the main “HCP_Solver” directory into, for example, “HCP_LEAPER_7_8_15_106.txt” file.  
During the calculations, you can track status information about the solution process in the strings. If you would like to stop the calculation, press the combination “Ctrl-C”. After completing the calculation, you can see the results of testing for 2 tests and different times for the solving process in the Command Prompt window.  
 
General statistic data for this example and test results are stored in the “HCP.txt” file. A Hamiltonian cycle which has been obtained is stored in the “HCP_LEAPER_7_8_15_106.tou” file. For the step-by-step instruction for downloading a graphical view of the input graph and its Hamiltonian cycle, see Sample 1.  
 
Back to the Top
3. USA Map with 10 Random Tests  
 
The step-by-step instruction for unzipping the TSMP-1 package, running calculations for the above listed graph and saving the results of testing is as follows:  
  • Unzip files from the TSMP-1.zip archive into the main TSMP-1 folder.  
  • Choose the main TSMP-1 folder and open the Software subfolder.  
  • Run the IIG_Rsch.exe file to open the TSMP-1 program.  
  • Choose USA Map Test Window from the New window and click the Ok button.  
  • Type 10 in the Random Starts field and type the same in the Full Tests field.  
  • Run TSMP-1 Solver to find a minimal tour in the USA_Map1 problem for 10 random tests using the Polyn. Meth. button.  
  • After calculations, see the statistics in the Information window and click Ok to close the window.  
  • To save results of the computation for a further analysis, type File/Save As… and, then, Save to store the default USA_Map1.map file in the Software subfolder.  
During the calculation you can track the status information about the solution process in the strings. If you would like to stop the calculation, press the Close command in the File menu. After completing the calculation, you can see the results of testing for 10 tests and different times for the solving process in the Information window. The optimal tour thereby obtained is stored in the USA_Map1.map file (see in the Software subfolder and Figure 9).  
 
 
Back to the Top
4. 70-city Problem (Smith/Thompson) from TSPLIB with 3 Random Tests  
 
The step-by-step instruction for unzipping the TSMP-1 package, running calculations for the above listed graph and saving the results of testing is as follows:  
  • Unzip files from the TSMP-1.zip archive into the main TSMP-1 folder.  
  • Choose the main TSMP-1 folder and open the Software subfolder.  
  • Run the IIG_Rsch.exe file to open the TSMP-1 program.  
  • Choose TSMP Test Window from the New window and click the Ok button.  
  • Type 70 in the Nodes field.  
  • Type 3 in the Random Starts field and type the same in the Full Tests field.  
  • Press the Import button and choose the input st70.txt file from the TSP Lib Data subfolder of the main folder.  
  • Run TSMP-1 Solver to find a minimal tour in the st70 problem for 3 random tests using the Polyn. Meth. button.  
  • After calculations, see the statistics in the Information window and click Ok to close the window.  
  • To save results of the computation for a further analysis, type File/Save As… and, then, Save to store the default TSMP1.tsp output file in the TSP Lib Data subfolder.  
 
During the calculation you can track the status information about the solution process in the strings. If you would like to stop the calculation, press the Close command in the File menu. After completing the calculation, you can see the results of testing for 3 tests and different times for the solving process in the Information window. The optimal tour thereby obtained is stored as the TSMP1.tsp file (see in the TSP Lib Data subfolder).  
 
 
Back to the Top
 
Site Map Contacts
Copyright © 1996-2017 International Intellectual Group, Inc.
About Efficiency TestLab Download / Purchase Support News
All rights reserved.