Function not executing

[kbklpl21]

Hi, both the compiler and debugger don't show any errors except the program only runs until when I call the function first_2_opt(n, d, f, p) at line 69 from https://pastebin.com/9sGMSwp1 . The original code is this one : https://pastebin.com/Xz3vScrL . The function mentioned starts from line 288 for both code. The original one doesn't have the problem, even though I just added a few lines of code for the problematic one.

Allow me to explain why I added the lines for the problematic one. If you refer to the function in the original one, the i and j indices increases sequentially, which is {0,0},{0,1},{0,2},...,{n,n-2},{n,n-1},{n,n}. However, I want it to be random, for example, {3,2},{n-2,3},{n,5} and so on. So I thought of letting the i and j be random numbers less than n, which is shown from my for loop initialisation where i = rand()%(n-1) and j = rand()%(n-1). And the lines that involves count_i and count_j is my attempt to make sure the same number for i and j only appear n times, since repetition of the combination of i and j would happen if they appear more than n times.

This explanation I give also serves to let everyone know what I'm trying to achieve so if those code are incorrect for the purpose I wish to achieve, I sincerely wish someone would correct me. Also, I apologise to those that already saw me posting this same code again and again (for different problem) because I didn't take up some of your suggestions such as using vectors and many more.

Here is the file I'm reading from:

Nug12
12
578
0 1 2 3 1 2 3 4 2 3 4 5
1 0 1 2 2 1 2 3 3 2 3 4
2 1 0 1 3 2 1 2 4 3 2 3
3 2 1 0 4 3 2 1 5 4 3 2
1 2 3 4 0 1 2 3 1 2 3 4
2 1 2 3 1 0 1 2 2 1 2 3
3 2 1 2 2 1 0 1 3 2 1 2
4 3 2 1 3 2 1 0 4 3 2 1
2 3 4 5 1 2 3 4 0 1 2 3
3 2 3 4 2 1 2 3 1 0 1 2
4 3 2 3 3 2 1 2 2 1 0 1
5 4 3 2 4 3 2 1 3 2 1 0

0 5 2 4 1 0 0 6 2 1 1 1
5 0 3 0 2 2 2 0 4 5 0 0
2 3 0 0 0 0 0 5 5 2 2 2
4 0 0 0 5 2 2 10 0 0 5 5
1 2 0 5 0 10 0 0 0 5 1 1
0 2 0 2 10 0 5 1 1 5 4 0
0 2 0 2 0 5 0 10 5 2 3 3
6 0 5 10 0 1 10 0 0 0 5 0
2 4 5 0 0 1 5 0 0 0 10 10
1 5 2 0 5 5 2 0 0 0 5 0
1 0 2 5 1 4 3 5 10 5 0 2
1 0 2 5 1 0 3 0 10 0 2 0

Thanks in advance, and have a nice day!

[dutch]

#include <iostream>
#include <numeric>
#include <random>
#include <algorithm>
using namespace std;

int main()
{
    int n = 5;
    auto a = new int[n * n];

    // Init a with values from 0 to n*n - 1
    iota(a, a + n*n, 0);

    // Shuffle the values    
    shuffle(a, a + n*n, default_random_engine{random_device{}()});

    // Print the values as coords in an n by n grid
    for (int i = 0; i < n * n; ++i)
        cout << '{' << a[i] / n << ',' << a[i] % n << "}\n";

    delete[] a;
}

[kbklpl21]

Hi dutch,
auto a = new int[n*n] Isn't this line just initialising 'a' as an array of 25 elements?

Also can I know the purpose of dividing the elements of 'a' with n and getting its remainder, and printing it out?

[lastchance]

kbklpl21 wrote:

This explanation I give also serves to let everyone know what I'm trying to achieve

You are joking!

I suspect you are trying to do Iterated Local Search, but you have failed to give an explanation in this or any other thread.

It would be better if you pasted code here rather than pastebin. If it won't fit ... then it's too long.

[dutch]

Isn't this line just initialising 'a' as an array of 25 elements?

Of course. n by n. What about it?

Also can I know the purpose of dividing the elements of 'a' with n and getting its remainder, and printing it out?

I thought that was obvious.
It's printing the coords you want.
From {0,0} to {n-1,n-1}, in random order.
Did you run it?
Check it out and think about it.
E.g., 17 / 5 = 3, 17 % 5 = 2,
so 17 stands for the coord {3,2}.

[kbklpl21]

Hi lastchance,
As I mentioned in the question, the explanation is for the lines I added, not the whole code, sorry for before I didn't think there was a need for saying it's for iterated local search, should I show the algorithm for iterated local search?
The code is too long, otherwise why would I want to go to another link for extra work, if I only posted a portion there would be a problem of incomplete code so I had to use pastebin.

[kbklpl21]

Hi dutch, thanks for the explanation.

It's because I misunderstood when I saw you say n by n grid, I thought you meant a n by n matrix, sorry.

So it means I can take the u as a[i]/n and the v as a[i]%n. Interesting I never thought about doing it like that! Thanks for the brilliant idea! Will try it out and update later.

[kbklpl21]

*update

Since I already have a function for generating a random array, so I used it to replace iota and shuffle. This is the resulting one:

void first_2_opt_symmetric (long int n, long int **d, long int **f, long int *p)
{
    /*
    FUNCTION:      first improvement 2-opt local search for symmetric instances
    INPUT:         pointer to some initial assignment
    OUTPUT:        none
    (SIDE)EFFECTS: initial assignment is locally optimized, dlb is used to increase the search speed, the dlb value is changed to false if item change it's location during perturbation
    COMMENT:       neighborhood is scanned in random order, use of register for faster computation
    */
 
    long int improvement = 1;
    long int improve_item = 0;
    long int u, v, i, j, k;
    long int tmp;
//    long int *x;
//    x = generate_random_vector(n);
    auto a = generate_random_vector(n*n);
    
    //iota(a, a + n*n, 0);    
    //shuffle(a, a + n*n, default_random_engine{random_device{}()});
    
	//a = new long int [n*n];
	
	improvement = 1;
    while (improvement)
    {
        improvement = 0;
        
        for ( i = 0 ; i < n ; i++)
        {
            u = a[i]/n;
            
            v = a[i]%n;
            
			improve_item = 0;    
            if (u == v)
            {
               	continue;
			}
				
            tmp = 0;
                
            for ( k = 0 ; k < n ; k++ )
            {
                if ( (k != u) && (k != v) )
                {
                    tmp += (d[u][k] - d[v][k]) * (f[p[v]][p[k]] - f[p[u]][p[k]]);
                }
            }
            if (tmp < 0)
            {
                improvement = 1;
                improve_item = 1;
                swap (u, v, p);
            }
        }
    }
//    delete [] x;
    delete [] a;
}

The function won't enter the while loop, any idea why?

[MikeyBoy]

Why do you believe it's not entering the loop?

[kbklpl21]

Hi MikeyBoy,

Because when I tried to print something in the loop nothing comes out, but now when I try to run again, it's good now.