CODEWITHSUNDEEP
cubuntu
Bruno SIgnori
Bruno SIgnori

Reputation: 31

Program is taking way longer than expected, is it running properly?

not sure this is the right place... I am running a brute-force code to solve an asymmetric traveler sales problem. It has 17 cities, one is fixed, so it would have 16! (> 20 trillions) permutations to check. 

unsigned long TotalCost(unsigned long *Matrix, short *Path, short 
Dimention)
{
    unsigned long result = 0;
    unsigned long Cost;
    int iD;

    for (iD = 1; iD <= Dimention; iD++)
    {
            Cost = Matrix[Dimention*Path[iD - 1] + Path[iD]];
            if (Cost > 0)
            {
                result = result + Cost;
            }
            else
            {
                return 4099999999;
            }

    }
    return result;
}

void swapP(short *x, short *y)
{
    short temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(unsigned long *Matrix, short Dimention, unsigned long *CurrentMin, short *PerPath, short **MinPath, short l, short r)
{
short i;
unsigned long CCost;

if (l == r)
{
    CCost = TotalCost(Matrix, PerPath, Dimention);
    if (CCost < (*CurrentMin))
    {
        for (i = 0; i <= Dimention; i++)
        {
            (*MinPath)[i] = PerPath[i];
        }
        (*CurrentMin) = CCost;
        PrintResults(Matrix, PerPath, Dimention, 2);
    }
}
else
{
    for (i = l; i <= r; i++)
    {
        swapP((PerPath+l), (PerPath+i));
        permute(Matrix, Dimention, CurrentMin, PerPath, MinPath, l+1, r);
        swapP((PerPath+l), (PerPath+i)); //backtrack
    }
}
}

int main (void)
{
// The ommited code here, allocs memory for the matrix, HcG and HrGR array
// it also initializes them

   permute(Matrix, Dimention, &TotalMin, HcG, &HrGR, 1, Dimention - 1);
}

I tested the above code for an instance of five cities and it returned successfully as expected in a few milliseconds. For the 17 cities, i initially thought it would take a few hours to solve, and then a couple days. It is running for 4 days now and i'm beginning to suspect the program, for some reason, is no longer running, like it's frozen. I'm not getting any errors, but it's taking way longer than i expected, the program prints the total cost and the path every time it finds a path with lower cost, but it stopped printing half an hour since it started.

I am using ubuntu 18.04, the program is "running" on terminal, the system monitor tells Memory: N/A, does that mean it's not using memory? It also tells CPU: 6%, can i increase it? Is there a way to check if it is running properly? Or estimate how long it will take to finish? I'm so unsure about it's integrity that i think i should stop the process, but at the same time i really wanted to see the results.

Upvotes: 0

Views: 281

Answers (1)

Daniel Goldfarb
Daniel Goldfarb

Reputation: 7714

I only glanced through your code, but I have done things like this many times in the past. My general approach for this is as follows (although it adds a small cost) ...

  1. add a print statement in a way (perhaps with a mod counter) that you would expect the print to come out approximately once every 2 to 3 minutes. Include some information in the print so that you can tell how far along your simulation is progressing. (note, among that information you probably want to be sure to print out variables that, if they get trashed, could cause infinite looping, for example "Dimention" (which you have misspelled btw)

  2. I would personally not have jumped from 5 cities to 17. Rather 5 to 7, then maybe 9 or 10 ... just to confirm all is working and to get an idea how much time increase to expect with your particular CPU.

Finally, in the situation you are in now, is it possible to get another window and run "ps" to see if your job is getting any CPU time? If not, my approach would be to kill it and implement as I described above. HTH.

Note also, the code you have omitted (memory allocation, etc) is critical: the code as written has the potential to go out of bounds, and possibly not crash (if only slightly out of bounds) but rather end up trashing variables (depending on memory layout) that could (as mentioned above) create an infinite or near-infinite loop.

Upvotes: 1

Related Questions