Algorytmy redukcji macierzy i komiwojażera
5 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Co się dzieje w funkcji 'reduceMatrix'?

  • Koszt redukcji jest ustawiany na wartość maksymalną.
  • Macierz jest drukowana na standardowe wyjście.
  • Funkcja nie wykonuje żadnych operacji.
  • Wiersze i kolumny macierzy są redukowane, a ich suma przypisywana do kosztu redukcji. (correct)

    • Jakie są parametry konstruktora 'ReductionMatrix'?

  • Vector matrix jako jedyny parametr. (correct)
  • Dwa parametry: macierz jako wektor i koszt redukcji.
  • Tylko jeden parametr – koszt redukcji.
  • Nie ma parametrów.

    • Jak w klasie 'ReductionMatrix' przechowywana jest macierz?

  • W publicznej zmiennej klasy.
  • W prywatnej zmiennej klasy jako wektor. (correct)
  • Na stosie w pamięci.
  • W zmiennej lokalnej funkcji.

    • Jakie informacje można uzyskać z metody 'getReductionCost'?

    <p>Całkowity koszt redukcji.</p> Signup and view all the answers

    Co zrobione jest w funkcji 'printMatrix'?

    <p>Każdy wiersz macierzy jest iterowany i drukowane są jego wartości.</p> Signup and view all the answers

    Study Notes

    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.

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    Code for ReductionMatrix Class (PDF)

    Description

    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.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser