Frage zu Algorithmus (Profitabelster Pfad berechnen)



  • Also, ich fang mal mit der Datenstruktur an:
    Es gibt Systeme, Systeme haben Stationen, Stationen haben Listings, ein Listing kann gekauft oder verkauft werden (also Waren). Systeme haben (x,y,z)-Koordinaten und eine Distanz zu unserem Sonnensystem. Stationen haben eine Distanz zu ihrem Stern und können auch planetarisch sein. Listings haben einen Namen, Kategorie, Angebotsmenge, Preis und eine Aktualität/Alter (also wie aktuell ist das Angebot?). Jedes System ist von jedem System aus über Sprünge erreichbar.
    Algorithmus:
    Wie berechnet man für eine maximale Sprunganzahl, maximale Distanz zum Sonnensystem, maximale Systemdistanz, maximale Station-Distanz, minimale Angebotsmenge, einen maximalen Kaufpreis und ein maximales Angebotsalter einen n-Pfad (n = maximale Sprunganzahl), bei dem bei Erreichen einer Station die vorher eingekauft Ware verkauft, die nächste Ware gekauft und der daraus resultierende Profit maximal wird?
    Code:

    struct Res1
    {
        shared_ptr<System1> sys1;
        shared_ptr<Station1> sta1;
        shared_ptr<Listing1> lis1;
    };
    
    vector<shared_ptr<System1>> systems;
    unordered_map<uint32_t, shared_ptr<System1>> systems_map;
    
    vector<shared_ptr<Station1>> stations;
    unordered_map<uint32_t, shared_ptr<Station1>> stations_map;
    
    vector<shared_ptr<Comm1>> comms;
    unordered_map<uint32_t, shared_ptr<Comm1>> comms_map;
    
    vector<shared_ptr<Listing1>> listings;
    unordered_map<uint32_t, shared_ptr<Listing1>> listings_map;
    
    // ...
    
    unordered_map<uint32_t, vector<shared_ptr<Station1>>> neighbours;
    void readNeighbours1()
    {
        for (size_t i = 0; i < systems.size(); i++)
        {
            shared_ptr<System1> sys1 = systems[i];
            for (size_t j = 0; j < systems.size(); j++)
            {
                if (i != j)
                {
                    shared_ptr<System1> sys2 = systems[j];
                    if (sys1->getDis(sys2) <= maxSysDis)
                    {
                        for (auto const &e1 : sys1->stations)
                        {
                            for (auto const &e2 : sys2->stations)
                            {
                                if (neighbours.count(e1->id) <= 0)
                                {
                                    neighbours[e1->id] = vector<shared_ptr<Station1>>();
                                }
                                neighbours[e1->id].push_back(e2);
                            }
                        }
                    }
                }
            }
        }
    }
    
    bool sorter2(const vector<Res1> &a, const vector<Res1> &b)
    {
        int p1 = 0;
        int p2 = 0;
        for (size_t i = 1; i < a.size(); i += 2)
        {
            p1 += (a[i].lis1->price - a[i - 1].lis1->price);
            p2 += (b[i].lis1->price - b[i - 1].lis1->price);
        }
        if (p1 != p2)
        {
            return p1 > p2;
        }
        else
        {
            float d1 = 0;
            float d2 = 0;
            for (size_t i = 1; i < a.size(); i += 2)
            {
                d1 += a[i - 1].sys1->getDis(a[i].sys1);
                d2 += b[i - 1].sys1->getDis(b[i].sys1);
            }
            return d1 < d2;
        }
    };
    
    vector<shared_ptr<Listing1>> getBestLis(shared_ptr<Station1> e1, shared_ptr<Station1> e2)
    {
        shared_ptr<Listing1> best1 = NULL;
        shared_ptr<Listing1> best2 = NULL;
        int best3 = 0;
        unordered_map<uint32_t, shared_ptr<Listing1>> sta_map_1 = e1->to_buys_map;
        unordered_map<uint32_t, shared_ptr<Listing1>> sta_map_2 = e2->to_sells_map;
        for (auto const &e3 : sta_map_1)
        {
            shared_ptr<Listing1> l1 = e3.second;
            if (l1->price > 0 && l1->demand >= minSupDem && sta_map_2.find(l1->comm_id) != sta_map_2.end())
            {
                shared_ptr<Listing1> l2 = sta_map_2[l1->comm_id];
                if (l2->price > l1->price && l2->demand >= minSupDem)
                {
                    if (l2->price - l1->price > best3)
                    {
                        best1 = l1;
                        best2 = l2;
                        best3 = l2->price - l1->price;
                    }
                }
            }
        }
        if (best3 == 0)
        {
            return {};
        }
        vector<shared_ptr<Listing1>> res;
        res.push_back(best1);
        res.push_back(best2);
        return res;
    }
    
    void getResults4(unordered_map<uint32_t, vector<shared_ptr<Station1>>> &ns, shared_ptr<Station1> index, int n, vector<vector<Res1>> &res, vector<Res1> &a)
    {
        if (n == 0)
        {
            vector<Res1> b = a;
            res.push_back(b);
            if (res.size() >= 10000)
            {
                sort(res.begin(), res.end(), sorter2);
                res.resize(5);
            }
            return;
        }
        vector<shared_ptr<Station1>> v1 = ns[index->id];
        for (auto const &sta2 : v1)
        {
            vector<shared_ptr<Listing1>> l1 = getBestLis(index, sta2);
            if (!l1.empty())
            {
                a.push_back({systems_map[index->sys_id], index, l1[0]});
                a.push_back({systems_map[sta2->sys_id], sta2, l1[1]});
                getResults4(ns, sta2, n - 1, res, a);
                a.pop_back();
                a.pop_back();
            }
        }
    }
    
    void getResults10(vector<vector<Res1>> &res)
    {
        time_t t1 = time(0);
        vector<Res1> a;
        for (size_t i = 0; i < stations.size(); i++)
        {
            if (i % (stations.size() / 100) == 0)
            {
                cout << i / (stations.size() / 100) << " Prozent ..." << endl;
            }
            getResults4(neighbours, stations[i], numberJumps - 1, res, a);
        }
        sort(res.begin(), res.end(), sorter2);
        time_t t2 = time(0);
        cout << (t2 - t1) << " Sek." << endl;
    }
    
    void printnres(vector<vector<Res1>> &res, size_t n)
    {
        cout << res.size() << endl;
        for (size_t i = 0; i < n; i++)
        {
            cout << (i + 1) << ":" << endl;
            int pro1 = 0;
            float dis1 = 0;
            vector<Res1> a = res[i];
            for (size_t j = 0; j < a.size(); j++)
            {
                cout << res[i][j].sys1->to_string() << endl;
                cout << res[i][j].sta1->to_string() << endl;
                cout << res[i][j].lis1->to_string() << endl;
                if (j % 2 == 0)
                {
                    pro1 += (res[i][j + 1].lis1->price - res[i][j].lis1->price);
                    dis1 += res[i][j].sys1->getDis(res[i][j + 1].sys1);
                }
                else
                {
                    cout << pro1 << endl;
                    cout << dis1 << endl;
                }
            }
            cout << endl;
        }
    }
    
    int main(int argc, char *argv[])
    {
        readSystem1();
        readStations1();
        readComms1();
        readListings1();
        readNeighbours1();
    
        vector<vector<Res1>> res;
        getResults10(res);
        printnres(res, 5);
    
        return 0;
    }
    

    Frage: Berechnet getResults10 die profitabelsten Pfade?



  • Du meinst im Ernst das jemand von deiner Minimalbeschreibung und undokumentiertem Code jetzt einen Korrektheitsbeweis herleitet?



  • @TGGC sagte in Frage zu Algorithmus (Profitabelster Pfad berechnen):

    jetzt einen Korrektheitsbeweis herleitet?

    Nein, an für sich nicht... Aber falls noch Bedarf besteht, kann ich die Funktionen noch dokumentieren.

    Hab ich "technisch gesehen" denn allgemein richtig programmiert?


  • Mod

    Das Ding hat globalen State ohne Ende. Dreifach verschachtelte Datenstrukturen ohne jede Abstraktion. So tolle Bezeichner wie sorter2. Das einen bool zurück gibt. Wohingegen getResults4(sic!) nichts zurück gibt.

    Selbst wenn du jetzt zufällig es irgendwie geschafft haben solltest, dass das irgendwie funktioniert, wird das Ding explodieren, sobald man es auch nur feste anguckt. Deswegen habe ich auch lieber nicht zu genau geguckt.

    PS: Falls du es nicht bemerkt haben solltest: Alles was ich im ersten Absatz aufzähle, sind keine nüchternen Aussagen, sondern jedes davon ist eine tödliche Programmiersünde aus der Spaghetticodeküche. Und ich habe, wie gesagt, gar nicht einmal so genau geguckt.



  • @EinNutzer0 sagte in Frage zu Algorithmus (Profitabelster Pfad berechnen):

    Frage: Berechnet getResults10 die profitabelsten Pfade?

    Ich habe mir den Code nicht genauer angeguckt, aber für sowas erstellt man sich Testfälle mit Beispielen für die man das von Hand durchgerechnet hat (das macht man für jede Teilfunktionalität). Wenn die erfolgreich durch laufen, weiß man, dass der Code zumindest für die Testfälle korrekte Ergebnisse liefert. Wenn man die Testfälle geschickt wählt, löst der Code dann wahrscheinlich das Problem korrekt. (man kann natürlich immer was vergessen zu testen...)



  • Ihr habt mich voll demotiviert. 😃

    Ich wechsele jetzt die Programmiersprache und beginne nochmal von Vorn - auch, wenn ich dann etwas länger auf die Pfadberechnungen warten muss...

    Gleich mehrere Todsünden begehen, war natürlich nicht von mir beabsichtigt... 😞



  • @EinNutzer0 die "Totsünden" sind nicht mal C++ spezifisch, sondern allgemein gültig für Softwareentwicklung, ganz unabhängig von der Programmiersprache.

    Edit: Es geht dabei nicht darum dich zu demotivieren, sondern dir Verbesserungspotentiale aufzuzeigen, die dir und deinen Kollegen das Leben erleichtern werden.


  • Mod

    Was halt ein bisschen komisch ist, wo du das überhaupt her hast. Mindestens das mit dem globalen State würde jeder Lehrer eigentlich extra sagen, und besonders niemals so vormachen. Und den Rest der Punkte mindestens auch niemals so vormachen. Du hast offensichtlich schon eine Menge C++ gelernt, auch anspruchsvollere Teile. Muss daher ein etwas merkwürdiger Lehrkurs sein, der das so beibringt.



  • @SeppJ sagte in Frage zu Algorithmus (Profitabelster Pfad berechnen):

    Was halt ein bisschen komisch ist, wo du das überhaupt her hast

    Naja - ich lerne viel selber und auch durch StackOverflow... Ich weiß jetzt nicht, welches von beiden verwerflicher wäre. Manche Sachen frage ich aber auch hier nach... (ihr seid die beste C++-Community im deutschsprachigen Raum.)

    Kopf ab? 🙃



  • @EinNutzer0 sagte in Frage zu Algorithmus (Profitabelster Pfad berechnen):

    Kopf ab? 🙃

    das nicht, aber auf lange sicht wirst du einfach probleme bekommen, weil variablen mit dem namen schon existieren, du ewig auf- und abscrollen musst, usw. spätestens dann, wenn jemand anderes so programmiert und du da weitermachen darfst, wirst du dich darüber ärgern.


  • Mod

    Das kann man auch direkt schon an diesem Beispiel schön erkennen: So ein Pfadsuchalgorithmus für sich ist ja eigentlich kein Selbstzweck. Nehmen wir mal an, du wolltest das in einem von dir programmierten Spiel benutzen. Wie würdest du das einbauen? Ziemlich doof, nicht wahr?



  • @SeppJ Ich nutze das schon als (illegale) Hilfe/Cheat in einem nicht von mir programmierten Spiel...
    Aber ich nutze das eben nur für mich - kein anderer sieht denn Code und kein anderer wird es jemals aufrufen/benützen...
    Darum habe ich mich auch an keinerlei Entwurfsmuster-Richtlinien, vernünftige Variablennamen, beschränkte Scopes, flache Schachtellungen, sinnvolle Schnittstellen usw. usf. gehalten. Der Code ist ein fehleranfälliger und nur schwer nachvollziehbarer Spaghettihaufen, BLOB oder auch eine Gott-Klasse. 😞


Log in to reply