Resolving Travelling Salesman Problem with Inchrosil

The travelling salesman problem (TSP) is one of the most famous and best studied in the computational area, being one the most difficult to resolve, due its complexity, which is considered a NP-complete problem. In the previous section, we have described an electronic system to solve Hamiltonian path problem with a cost approximately of polynomial order, in this paragraph, the graph to analyze has a weighted and direction in its paths, where only one or set Hamiltonian paths are solution of TSP, so first step would be found all Hamiltonian paths at the graph, and next steps would be calculated final cost each Hamiltonian path found, using its weighted and directions, by this reason, in our research, we have used the same infrastructure explained in Hamiltonian Path device, which would obtain all Hamiltonian paths, later with these paths, the system would calculate each individual cost and compare all cost to get which is the best Hamiltonian path, always depending a initial characteristics established by programmer/user.

All these calculations could be done in parallel, also all criteria to sort path cost could be stored in different modules of the system, in this way any operation is quick and faster to do. In this article, we have considered two different systems to do all mathematical operation and choice the best Hamiltonian path cost, depending one specific criteria. The first system contains software to calculate and storage all paths cost, which determinates the correspondence between weight-edge. This system, once the individual cost is obtained, calculates the total cost of each path. When all cost is calculated, the system order all cost by one specific criterion (for example, from least to greatest, from greatest to least, etc).

Finally, system has a set of ordered paths and the system can choose the best path. In Figure 1 shows first system to calculate TSP, the reference Figure 1-21 in figure represents the circuit to obtain the Hamiltonian path, Figure 1-22 the connection interface with interface Figure 1-25 of a data processing module Figure 1-23, reference Figure 1-24 is a database and Figure 1-26 a cost and sorting calculation module. The reference Figure 1-27 represents an external data request device.

Figure 1: First System to calculate any TSP.

On the other hand, the intermediate data was stored in the database, i.e. the weights of the edges, etc. being these systems as support to the calculations, which are going to be made or are have been made.

At second system (system shown in Figure 2) uses memories to store and manipulate all weight of vertex-edge. These memories could be an electronics circuit using Inchrosil technology or other kind of memories. In this case, system does not store real value of weight at the edge, only a reference of memory address (point reference), because the value can be huge and any system address has an established size, by this reason, it is better to store only memory address, later with this memory address, system can access real value stored.

On the other hand, this second system follows next steps: when the Hamiltonian paths are determined, by the circuit Figure 2-21, it seeks the value of the edges in the memory Figure 2-28, since as we know its address, we will know its value. These costs are added and will be looked for by circuitry mediation, i.e. a bus Figure 2-32 and adders Figure 2-30, on the other hand, to obtain the total cost of each path which can be stored in the memory Figure 2-28 with consecutive addresses. As in the previous implementation, the user or the system which receives this information as input chooses with which path it remains, by criteria of choice, outside the devices described in this article. In this example, reference Figure 2-22 represents the connection interface with an interface Figure 2-25a of the data processing module Figure 2-23a, reference Figure 2-29 the sorting module, Figure 2-31 a connection interface of module Figure 2-23a with a data fetching device Figure 2-27.

Figure 2: Second system to calculate any TSP.