Hint on Checking a network
My problem goes something like this. I have a variable of 5 arrays a[5] for storing the 5nodes of a network. The network is randomly formed by the random number generator. I have the time of travel for each paths of the network. All the nodes may not be connected to eachother. The network and the time of travel of each path is as per the user has assigned. Now I have to check the elements of each array and assign the penalty as per the conditions. My main task is to find a network path traveling each node of the network only once such that the node visited is not repeated. Its similar to TSP but the difference is that in TSP has the condition that it is possible to travel from each node to every other node. But for my case the network is pre defined and nodes are not connected to every other nodes in the network.
a) Like if the network stored is 2-2-3-4-5 then I find that a[1]=a[2] so I will have to assign the penalty (type 1 )as the network has a path 2-2 which is not possible as the starting and end of the path is same. At the same time for rest of the paths from node 2 to 3, node 3 to 4, node 4 to 5 I will have to calculate the sum of total time of travel when I finally reach the node 5.
b) Also there is another penalty condition if the path is not a possible path in the network given by user then I will have to assign penaly( type 2) for such kind of condition like if 1-2-4-3-5 is a network to be checked. Here I am supposing that all the paths are possible but the path 4-3 doesn’t exist in the real network provided by the user, So for such cases I will have to calculate the sum of the time of travel for the paths which are possible and also assign the penalty (type 2)
c) There is also a condition that I need the end point of the network as node 5.So in the network generated randomly if the end node is not the node 5 then I will have to assign the penalty (type 3) and at the same time calculated the sum of the rest possible paths. For example the node 3-5-2-1-4 here the end node is 4 so I will have to assign the penalty(type 4)
d) Since I am not allowed to visit the same node twice I will have to assign the (penalty type 4) if the network has repeatition of nodes like if the network is 2-4-3-1-4. Here the node 4 is occurring twice so I will have to assign the penalty(type 4) and also calculate the sum of the time of travel of the other paths.
Considering all the above penalty conditions I will have to check the networks. I am really not being able to use any logic on how do I start. Need some hint on how do I do it.
Re: Hint on Checking a network
This is in fact a TSP problem and has no known guaranteed algorithm to find the best answer. All you can do is either approximate with any of the many solutions to this or to brute force try every possible permutation.
Re: Hint on Checking a network
Quote:
Originally Posted by
en061
...
Its similar to TSP but the difference is that in TSP has the condition that it is possible to travel from each node to every other node. But for my case the network is pre defined and nodes are not connected to every other nodes in the network.
...
Considering all the above penalty conditions I will have to check the networks. I am really not being able to use any logic on how do I start. Need some hint on how do I do it.
Just set a really high cost for each edge that does not exist in your network, then it will not be part of the optimal solution. Then your problem is a TSP again and you can apply existing algorithms.
