Algorytmy redukcji macierzy i komiwojażera

Klasa ReductionMatrix

• Reprezentuje macierz.
• Posiada atrybut matrix_ przechowujący dane macierzy (jako wektor wektora intów).
• Posiada atrybut reduction_cost_ przechowujący koszt redukcji.
• Konstruktor pobiera macierz jako argument i inicjalizuje atrybut matrix_. Koszt redukcji inicjalizowany jest na 0.
• Metoda reduceMatrix() oblicza koszt redukcji wierszy i kolumn.
• Metoda getReductionCost() zwraca obliczony koszt redukcji.
• Metoda reduceRows() oblicza i odlicza minimalne wartości w wierszach, redukując i zwracając wartość kosztu redukcji.
• Metoda reduceColumns() oblicza i odlicza minimalne wartości w kolumnach, redukując i zwracając wartość kosztu redukcji.
• Metoda blockEdge() blokuje wiersz i kolumnę w macierzy poprzez ustawienie wartości na numeric_limits<int>::max().

Klasa TSPBranchAndBound

• Klasa reprezentująca algorytm Branch and Bound dla problemu komiwojażera.
• Metoda isInPath() sprawdza, czy dany wierzchołek znajduje się w ścieżce.
• Metoda breadthFirstSearch() realizuje algorytm przeszukiwania wszerz.
• Metoda depthFirstSearch() realizuje algorytm przeszukiwania w głąb.
• Metoda lowestCostFirstSearch() realizuje algorytm przeszukiwania z najmniejszym kosztem najpierw.
• Metoda calculatePathCost() oblicza koszt ścieżki.

Struktura CompareNode

• Przygotowuje kolejkę priorytetową algorytmu w zależności od kosztu węzła.
• bool operator()(const Node& a, const Node& b) - porównuje węzły a i b na podstawie ich kosztów, przekazując priorytet węzłowi z niższym kosztem.

Klasa Graph

• Reprezentuje graf.
• Posiada atrybut matrix_ przechowujący macierz sąsiedztwa.
• Metoda readFromFile() wczytuje graf z pliku.
• Metoda printMatrix() drukuje macierz na standardowym wyjściu.
• Metoda randomGenerateGraph() generuje losowy graf.
• Metoda saveToFile() zapisuje graf do pliku.

Zbadaj kluczowe koncepcje dotyczące klas ReductionMatrix oraz TSPBranchAndBound. Dowiedz się, jak macierz może być używana do obliczania kosztów redukcji i jak działa algorytm komiwojażera. Przetestuj swoją wiedzę na temat tych złożonych struktur i algorytmów.