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");
}