MST- parę pytań

TK
  • Rejestracja:ponad rok
  • Ostatnio:10 miesięcy
  • Postów:11
0

Hej, nie rozumiem kilku rzeczy z MST metodą Prima:

Pytanie_1:
Załóżmy, że wierzchołki to miasta, a krawędzie to odcinki między miastami. Chcę odbyć trasę według tych krawędzi, tak jak ponizej. Dojechałem do miasta o indeksie 4, następnie 5 i muszę przecież wrócić do 4 żeby kontynuować trasę:
-dlaczego wiec nie jest brane pod uwagę to, że po dojechaniu z wierzchołka 5 muszę przecież wrócić do wierzchołka 4 aby kontynuować trasę więc do wagi powinienem dodać kolejne 2km?
screenshot-20240504030607.png

Widać to na prostszym grafie:

  1. Czyli metodą Prima wybieram sobie wierzchołek 0.
  2. Porównując wagi dodaję na początku 3, a potem 4 wiec waga to 7km.
  3. Ale gdybym chciał odwiedzić wszystkie miasta począwszy od 0 do 1 to daje 3km, z 1 muszę wrócić do 0 więc +3km, z 0 do 2 +4km, a wiec 3+3+4=10
    screenshot-20240504033051.png
edytowany 1x, ostatnio: tkowal
SA
  • Rejestracja:ponad 12 lat
  • Ostatnio:około 9 godzin
  • Postów:1435
0

Nie mylisz przypadkiem problemu komiwojażera z MST? W MST nie ma żadnych ścieżek czy wracania, chodzi o to, żeby istniała ścieżka pomiędzy każda parą wierzchołków.

Można o tym myśleć jak o kładzeniu asfaltu między miastami. Nie interesuje Cię ile czasu zajmą podróże tylko, żeby dało się wszędzie dojechać i zużyć jak najmniej asfaltu.

TK
dzięki za pomoc!
TK
  • Rejestracja:ponad rok
  • Ostatnio:10 miesięcy
  • Postów:11
0

Mam do rozwiązania taki problem za pomocą Prima i tego właśnie nie rozumiem, bo tam nie ma żadnych ścieżek i wracania tak jak napisałeś i jeżeli chodziłoby o dojechanie i zużycie jak najmniej asfaltu to ten sposób działa (dzięki za fajny przykład).

Ale, mimo wszystko nie rozumiem tego jak można określić MST trasy samochodu jeżeli nie da się tak pokonać trasy żeby nie wrócić do miasta o numerze 4, a więc trzeba użyć powrotów, a więc trzeab dodać jeszcze raz tę wagę. Czy ja dobrze do tego podchodzę w kontekście tego zadania czy popełniam jakiś błąd myślowy? ;/

screenshot-20240504141242.png

abrakadaber
abrakadaber
  • Rejestracja:ponad 12 lat
  • Ostatnio:8 miesięcy
  • Postów:6610
1

ale w zadaniu masz "dotrzeć do DOWOLNEGO" a nie "do KAŻDEGO". Obierasz jakieś miasto jako początkowe i najpierw wyznaczasz drogę do każdego miasta ale składającą się z jak najkrótszych odcinków, potem wybierasz najdłuższy odcinek (z tych znalezionych tras) i to jest twój minimalny zasięg


Chcesz pomocy - pokaż kod - abrakadabra źle działa z techniką.
edytowany 1x, ostatnio: abrakadaber
TK
  • Rejestracja:ponad rok
  • Ostatnio:10 miesięcy
  • Postów:11
0

Gdybym miał taki graf:
screenshot-20240505215926.png

i chciał znaleźć jego MST Kruskalem to:
krawędź : waga
1 - 2 : 2
2 - 8 : 3
3 - 7 : 4
0 - 4 : 5
5 - 6 : 7
0 - 1 : 10
2 - 3 : 30
4 - 5 : 60
___
121

A następnie znaleźć najdłuższy odcinek między dowolnymi dwoma miastami (z trasy którą znalazł MST) to zawsze nim będzie odcinek o największe wadze prawda czyli 60 w tym przypadku? :)

abrakadaber
abrakadaber
dokładnie, czyli potrzebujesz samochód, który przejedzie min. 60 na jednym ładowaniu
TK
  • Rejestracja:ponad rok
  • Ostatnio:10 miesięcy
  • Postów:11
0

Mam jeszcze mały problem z odczytywaniem drugiego przypadku testowego z pliku. Wyrzuca mi wyjątek w int Graph::find_set(int i):

dane w pliku:
2 //liczba przypadków testowych
2 //liczba wierzchołków w przypadku testowym 1
0 1 9 //wierzchołek 0 oraz 1 oraz waga krawędzi
2 //liczba wierzchołków w przypadku testowym w
0 1 3 //wierzchołek 0 oraz 1 oraz waga krawędzi

Kopiuj
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <fstream>

using namespace std;

#define edge pair<int, int>

class Graph {
private:
    vector<pair<int, edge> > G;  
    vector<pair<int, edge> > T;  
    int* parent;
    int V;  
public:
    Graph(int V);
    void AddWeightedEdge(int u, int v, int w);
    int find_set(int i);
    void union_set(int u, int v);
    void kruskal();
    void print();
};
Graph::Graph(int V) {
    parent = new int[V];

    for (int i = 0; i < V; i++)
        parent[i] = i;

    G.clear();
    T.clear();
}
void Graph::AddWeightedEdge(int u, int v, int w) {
    G.push_back(make_pair(w, edge(u, v)));
}
int Graph::find_set(int i) {
    if (i == parent[i]) //Nieobsłużony wyjątek w lokalizacji 0x00007FF686B2D005 w ConsoleApplication1.exe: 0xC0000005: Naruszenie zasad dostępu podczas odczytywania w lokalizacji 0x000001EDCA4B3914.
        return i;
    else

        return find_set(parent[i]);
}

void Graph::union_set(int u, int v) {
    parent[u] = parent[v];
}
void Graph::kruskal() {
    int i, uRep, vRep;
    sort(G.begin(), G.end());  
    for (i = 0; i < G.size(); i++) {
        uRep = find_set(G[i].second.first);
        vRep = find_set(G[i].second.second);
        if (uRep != vRep) {
            T.push_back(G[i]);  
            union_set(uRep, vRep);
        }
    }
}
void Graph::print() 
    {
        int size_value = T.size();
        int largest = size_value - 1;
        cout<<T[largest].first;
        cout << endl;
    }

int main() 
{
    unsigned short numberoftests = 0;
    unsigned short first_size = 0;
    ifstream data("input.txt");
    data >> numberoftests;

    for (int begin = 1; begin <= numberoftests; numberoftests--)
    {
       data >> first_size;
       Graph g(first_size);

       for (int i = 0; i < first_size; i++)
       {
           int a = 0;
           int b = 0;
           int c = 0;
           data >> a;
           data >> b;
           data >> c;
           g.AddWeightedEdge(a, b, c);
           
       }
       g.kruskal();
       g.print();
       return 0;
      
    }
    


}
edytowany 1x, ostatnio: tkowal
abrakadaber
abrakadaber
  • Rejestracja:ponad 12 lat
  • Ostatnio:8 miesięcy
  • Postów:6610
0

no to musisz użyć debbugera i zobaczyć czy przypadkiem nie wychodzisz poza zakres


Chcesz pomocy - pokaż kod - abrakadabra źle działa z techniką.
TK
z tego co udało mi się wykminić to zakończeniu pierwszego przypadku testowego, a następnie rozpoczęciu nowego to już tutaj widać że dana nie została pobrana: for (int begin = 1; begin <= numberoftests; numberoftests--) { data >> first_size; cout << first_size; // brak pobrania tej danej w drugim przypadku testowym Graph g(first_size); powinienem coś wyczyścić jeszcze na koniec każdego przypadku testowego? ;/
TK
znalazłem babola: w pętli zamiast pobierać ilość krawędzi pobierałem ilość wierzchołków przez co wywalało się tylko na specyficznych danych kiedy np. ilość krawędzi była większa od ilości wierzchołków dlatego nie mogłem tego wychwycić. @abrakadaber @Saalin dzięki!

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.