Algorytm zachłanny - Komiwojażer (TSP)

0

Witam serdecznie. Mam za zadanie stworzyć algorytm zachłanny (dla problemu komiwojażera - algorytm najbliższego sąsiada).

Algorytm ten realizowany ma być dla "n" miast. pÓÓÓÓki co robię to dla minimalnej ilości miast - 3, które tworzą cykl Hamiltona. No i już tutaj natrafiłem na problemy.

Mam stworzoną macierz sąsiedztwa i macierz wag. Następnie inicjuję te macierze (tablice) zerami, a po tym tworzę graf pełny dla miast równych 3, gdzie wagi dobierane są losowo.

Problem zaczyna się gdy zaczynam realizację samego algorytmu zachłannego. Tak jak podczas pierwszego obiegu pętli FOR znajduje mi najmniejszą wagę i zeruje odpowiednie pola w macierzy sąsiedztwa, tak przy następnym obiegu tej pętli dzieją się dziwne rzeczy.

Np. przy kolejnym obiegu z racji wyzerowania całej kolumny odpowiadającej miastu nr 1 powinienem otrzymać w pierwszym IF'ie
matrix[w][0] =0 po czym powinien ominąć ten warunek. Program natomiast wchodzi w niego i zmienia mi zmienną "temp" mimo że w macierzy sąsiedztwa widnieje zero.

Wygląda na to że mimo że na końcu pętli FOR nadaję matrix[k][w] = 0; to nie wpisuje poprawnie tej wartości (???) . Nie wiem o co tutaj biega, orłem z programowania nie jestem, a nie wiem co może być przyczyną...

Poniżej wstawiam kod:


#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {

    srand(time(NULL));
    int n;
    cout << "Podaj ilosc miast dla ktorych ma byc rozwiazany problem Komiwojazera (Minimum 3): ";
    cin >> n;

    /* ----- TWORZYMY MACIERZ SĄSIADÓW N x N ----- */

    int **matrix = new int *[n];  // Alokacja pamięci dla tablicy dwuwymiarowej - MACIERZ SĄSIEDZTWA
    int **matrix_weight = new int*[n];  // Alokacja pamięci dla tablicy dwuwymiarowej - MACIERZ WAG

    for (int i = 0; i < n; i++) {

        matrix[i] = new int[n];  
        matrix_weight[i] = new int[n];
    }

    /* ----- INICJALIZACJA MACIERZY SĄSIADÓW ZERAMI ----- */

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++){

            matrix[i][j] = 0;
            matrix_weight[i][j] = 0;
        }
    }

    /* ----- TWORZENIE GRAFU PEŁNEGO DLA ILOŚCI MIAST RÓWNEJ TRZY ----- */

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i != j) {
                matrix[i][j] = 1;
                matrix_weight[i][j] = (std::rand() % 99) + 1;
            }
            else {
                matrix[i][j] = 0;
                matrix_weight[i][j] = 0;
            }
        }
    }

    cout << "Macierz sasiedztwa wyglada nastepujaco: " << endl;
    cout << "---------------------------------------" << endl << endl;

    for (int i = 0; i < 3; i++){

        for (int j = 0; j < 3; j++){
            cout << matrix[i][j] << " ";

        }
        cout << endl;
    }

    cout << endl;
    cout << "Macierz wag wyglada nastepujaco: " << endl;
    cout << "---------------------------------------" << endl << endl;

    for (int i = 0; i < 3; i++){

        for (int j = 0; j < 3; j++){
            cout << matrix_weight[i][j] << " ";

        }
        cout << endl;
    }

    int temp = 100;
    int temporary = 0;
    int w = 0;
    int waga[10];
    int odwiedzone = 3;

    while (odwiedzone!=0) {    
        for (int k = 0; k < 3; k++) {
            if ((k != w) || (matrix[w][k] != 0)) {
                if (matrix_weight[w][k] < temp) {    
                    temp = matrix_weight[w][k];
                    temporary = k;                  
                }
            }
            matrix[k][w] = 0;
            waga[w] = temp;
        }
        w = temporary;
        temp = 100;
        if (odwiedzone = 1) {

                                                    // <--- TUTAJ POJAWI SIĘ INSTRUKCJA BY POWRÓCIŁ DO MIASTA POCZĄTKOWEGO
        }
        odwiedzone--;
    }

    system("pause");
}
1

if (odwiedzone = 1) to jest przypisanie. A robienie 2 macierzy to jakaś głupota tak BTW. Po co ci ta pierwsza macierz skoro ta druga niesie te same informacje?

0

Okej wywaliłem tą macierz sąsiedztwa która rzeczywiście była zbędna, ale czy jest ktoś w stanie mi wytłumaczyć czemu mi wchodzi w ten warunek:

if ((k != w) || (matrix_weight[w][k] != 0))  

Skoro dana tablica matrix_weight[w][k] w danym obiegu pętli dla danego "w" i "k" ma właśnie wartość zero i knoci mi cały algorytm :/

0

Pewnie dlatego że nie rozumiesz logiki. Warunek jest spełniony jeśli w macierzy nie ma 0 lub jeśli k i w są różne. Czyli warunek w ogóle nie ma sensu bo żeby nie był spełniony to musiałbyś mieć na przekątnej coś różnego od 0. Nie miało btam być czasem &&?

0

Racja powinien tam być &&. Wprowadziłem również warunek w którym wraca nam do miasta początkowego i stwierdziłem że przyda mi się ta zero-jedynkowa macierz sąsiedztwa jako dodatkowa bo jakbym zerował tą macierz z wagami to program w pewnym momencie straciłby wagę aby wrócić do miasta początkowego. Wiem że to mało optymalny i najprostszy możliwie algorytm zachłanny (nie uwzględnia remisu gdy wagi są równe na danym poziomie) ale jakoś działa :-) .

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0