Die Mathe-Redaktion - 24.05.2019 15:07 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 391 Gäste und 19 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Minimale Tagesstrecke
Druckversion
Druckversion
Autor
Universität/Hochschule J Minimale Tagesstrecke
grezebeze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 14.06.2015
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-04-19


Hallo lieber Matheplanet,

zurzeit bin ich dabei, meine Programmierskills, insbesondere in C++, aufzubessern. Dazu hänge ich gerade an einer Aufgabe fest.

Ein Wanderer möchte innerhalb einer vorgegeben Zeit eine mehrtägige Wanderung unternehmen. Auf der festvorgegebenen Route befinden sich mehrere Übernachtungsmöglichkeiten mit Abständen zueinander (Etappen).
Wie muss der Wanderer seine Route wählen, damit die maximale Tagesstrecke minimal ist? Ein Beispiel:
Tage: 3, Strecke: 59 km, Etappen: 6, dazu folgendes Bild:



Dies ist eher eine Logik Frage, als eine programmiertechnische Frage, deshalb entschuldige ich mich dafür, falls der Beitrag im falschen Forum erstellt wird.

Meine Überlegungen bisher:
1) Ich bestimme den Durchschnitt der gesamten Strecke pro Tag. Also wären es im obigen Beispiel ca. 20 km pro Tag (Gesamte Strecke/Anzahl der Tage).
Danach wollte ich so vorgehen: Ich gehe eine Etappe und bestimme den Abstand zwischen meiner momentan zurückgelegten Strecke und dem Durchschnitt. Danach bestimme ich den Abstand zwischen dem Durchschnitt und der zurückgelegten Strecke, wenn ich noch eine Etappe weiter gegangen wäre. Wenn nun der Abstand zwischen Durchschnitt und (Etappe+1) kleiner als der Abstand zwischen Durchschnitt und (Etappe) ist, dann gehe ich zur (Etappe+1), andernfalls bleib ich bei (Etappe). Dieses Vorgehen führte aber nicht zum erwünschten Ergebnis.

2) Meine nächste Überlegung wäre, jede einzelne Permutation durchzugehen. Dies kommt mir aber einwenig unelegant vor und komme damit nicht wirklich voran.

Vielleicht kann mir ja der ein oder andere auf die Sprünge helfen. Ich denke, dass die Lösung für dieses Problem einfacher ist, als ich momentan denke.

Vielen Dank!



  Profil  Quote  Link auf diesen Beitrag Link
Caban
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.09.2018
Mitteilungen: 368
Aus: Brennpunkt einer Parabel
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-04-19


Hallo

Ich würde so vorgehen:

Zuerst würde ich prüfen ob es einzelne Etappen geben kann, die die größte Etappe sein können.
Dann würde ich dasselbe mit Etappen machen, die aus zwei Strecken bestehen

dann aus drei Strecken usw.

Ich bin zur Lösung 16+5+5 als Lösung gekommen.

Gruß Caban



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-04-19


Hallo grezebeze,

unelegant mag das sein, aber es gibt bei sechs etappen nur 2^6 = 64 möglichkeiten, diese auf tage zu verteilen ( da man an jeder etappe entweder anhalten kann zum nächtigen oder weitergeht ). Man muss dann noch gucken, dass man mit den tagen auskommt, dazu kann man einfach die fälle verwerfen, in denen mehr als die zulässigen übernachtungen vorkommen. Dann alles zusammenzählen - und unterwegs das minimum vermerken. Als Programmierübung wäre das gar nicht so schlecht.

Grüsse aus dem Harz
Gerhard/Gonz

[Die Antwort wurde vor Beitrag No.1 begonnen.]


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
grezebeze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 14.06.2015
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-04-19


Hallo,

Danke für die Antwort!
Nur leider kann ich deinem Vorgehen nicht ganz folgen. Wie genau bist du zum Ergebnis 16+5+5 gekommen (also mir ist klar, dass dies die richtige Lösung ist, nur leider verstehe ich den Weg nicht ganz).

[Die Antwort wurde nach Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Caban
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.09.2018
Mitteilungen: 368
Aus: Brennpunkt einer Parabel
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-04-19


Hallo

Wir betrachen als erstes die Routen, die nur aus einer Strecke bestehen:

Keiner dieser Strecken kann die maximale Strecke sein.

Nun kommen wir zu den Routen, die aus zwei Strecken bestehen:

11+16 wäre möglich, die anderen nicht.

Die Routen mit drei Strecken:

16+5+5 ist möglich, einige Möglichkeiten wären möglich, scheiden aber aus, weil sie 26 übertreffen. Z.B.: 11+16+5

Gruß caban



  Profil  Quote  Link auf diesen Beitrag Link
grezebeze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 14.06.2015
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-04-19


Hallo gonz,

also im Beispiel mit 3 Tagen und 6 Etappen, gibt es genau 10 mögliche Szenarien. Wie würdest du da dann vorgehen? einen vector<vector<int>> v definieren, in dem alle Vektoren mit den jeweiligen Tagesrouten stehen? Scheint mir eine vernünftige Vorgehensweise, nur weiß ich nicht, wie ich mit C++ alle Möglichkeiten durchgehen kann. Also falls da wer einen Ansatz hat, wäre ich sehr dankbar.



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26756
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-04-19


Es ist ein Partitionierungsproblem:
Teile die 6 Etappen in 3 Gruppen mit je mindestens einem Element ein.
fed-Code einblenden
G1, G2 und G3 sind die 3 Gruppen, bestehend aus den n in der Zeile angegebenen Elementen, Max ist jeweils der größte Etappenwert der 3 Gruppen.

Die Partitionierung machst du Rekursiv.

Gruß vom ¼


-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-04-19


es hängt ja nebenbei nicht daran, dass es c++ ist. du könntest versuchen, den algorithmus zur bestimmung dieser möglichkeiten nutzen willst, allgemein oder in pseudocode zu beschreiben. es ist dann ein zweiter ( und eigentlich recht simpler ) schritt, das dann in C++ zu gießen. Du könntest dann im ersten schritt einfach ein programm schreiben, dass diese möglichkeiten bestimmt und ausgibt....


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-04-21


Hallo grezebeze,

Um es ein wenig weiter zu erläutern, wie man da vorgehen würde...

die Schritte zur Realisierung sind damit doch in etwa so gegeben:
1) Die Parameter des Problems in Konstanten gießen ( hast du in Post #5 schon angefangen )
2) Die Datenstrukturen definieren, in denen du Kandidaten für Lösungen speicherst, und dir den (bisher) besten Wert merken kannst.
3) Einen Algorithmus finden, der alle Partitionen durchgeht
4) Für jede gefundene Partition den Zielwert berechnen und mit dem bisherigen Minimum vergleichen
5) und ein bisschen was an Program drumherum mit hübschen Ausgaben etc.

Für den Schritt eins... sieht das bei mir so aus ( ich habe es mal in Python gebaut) ( Die Daten sind nicht die aus deinem Beispiel, ich hab ein wenig damit herumgespielt ):
python
STOPS  = 4
# der letzte Stop ist der beim Erreichen der Gesamtstrecke.
# es gibt also genausoviele Stops wie Tagestouren.
 
HOUSES = 9
# Es gibt ein Haus mehr als Teilstrecken, da am
# Anfang und am Ende der Gesamtstrecke je ein Haus steht.
# Nebenbedingung: Es muss mindestens ein Haus mehr geben als Stops :)
 
DISTANCES = [0,6,2,5,5,6,10,5,2]
# es gibt einen Abstand weniger als Häuser ( siehe oben )
# DISTANCE[1] ist der Wegabstand von Haus 1 zu Haus 2.
# weil. Ich liebe es einheitlich - alle Indices sollen ab 1 laufen 
# TODO ob dies eine gute Entscheidung war sei mal dahingestellt 
# und damit haben wir alles was wir an Daten zum Problem brauchen :)

Du siehst nebenbei, dass ich da auch noch mit den Strukturen kämpfe. Eine Frage ist immer, ob man Indicierungen mit 0 oder 1 beginnen soll,
was natürlich auch davon abhängt, was die Sprache so mitbringt.

Für den dritten Schritt, der sicherlich ( wenn man die Programmiersprache, in deinem Fall C++, beherrscht ) der anspruchsvollste ist, gibt es mehrere Möglichkeiten ( wie immer :) ). Ich bin so vorgegangen:

- Startpartition: Gehe jeden Tag nur eine Strecke, am letzten Tag den Rest
- Finde eine neue Partition, indem du, ausgehend von der aktuellen Partition
-- an einem Tag ( beginnend mit dem letzten Tag, an dem das möglich ist) eine Strecke weiter gehst als bisher, und
-- an allen auf diesen Tag folgenden Tagen ( ausser dem letzten ) wieder nur eine Strecke einplanst

Ich hoffe das hilft dir ein wenig weiter.
Lass uns wissen wie du vorankommst oder ob es irgendwo dann noch "klemmt"!

Frohe Ostern - und viel Erfolg
Gonz/Gerhard




-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-04-21


Noch als Ergänzung... zu dem Algorithmus. Man sollte sich bei der Auswahl ja sicher sein, dass er a) wirklich alle Partitionen findet ( das ist notwendig ) und b) jede nur einmal ( wenn... man nicht nachher aussortieren will ).

Es ist nebenbei bemerkt auch sicher so, dass man sich nach und nach einen Vorrat an Ideen vermerkt, die man später für neue, ähnliche Probleme nutzen und anpassen kann. Ob ich auf den oben vorgeschlagenen ursprünglich mal selber gekommen bin, oder ihn irgendwo gefunden habe, vermag ich gar nicht zu sagen ( tippe aber eher auf letzteres ).

Wenn das obige nicht einsichtig ist oder ggf. zu kompliziert, weil man sich bei der Realisierung immer mal vertut ( ich hatte ursprünlich beim coden in python einige macken eingebaut, insbesondere +-1 Fehler... ) dann ist folgender irgendwie brachialer und robuster:

Da wir am Streckenende notwendig einen Stop einlegen müssen, betrachten wir nur die Zwischenstops, deren Zahl soll STOPS-1 sein.

In erstem Anlauf können wir aber davon ausgehen, dass wir an jedem Haus auf dem Weg einkehren oder weitergehen können. Wenn wir 0 = weiter und 1 = stop codieren, so sind das genau die Folgen der Länge STOP-1 aus den beiden Symbolen 0 und 1.

Diese aber können wir auf die Binärzahlen im Bereich 0..2^(STOP-1) -1 abbilden.

Natürlich haben wir jetzt ggf. zu wenige oder zu viele Stops. Um das auszumerzen gehen wir wie folgt vor:

- Gehe alle Zahlen von 0 bis 2^(STOP-1) -1 durch
- Betrachte sie als Binärzahlen und wandle in eine Folge von Nullen und einsen.
- Zähle die 1en und nimm eine Folge nur dann, wenn diese STOP-1 ist.
- Die Partition ergibt sich nun, indem an den Häusern gehalten wird, für die in der Folge eine 1 steht.

Das ist von der Laufzeit her aufwendiger. Aber es ist glaube ich einsichtiger, dass man damit alle Partitionen findet und zwar nur einmal. Und es ist ggf. einfacher zu coden.

Und vor allem: Ich glaube das wäre mein Algo gewesen, wenn ich die Aufgabe gestellt bekommen hätte als ich noch nicht so weit war, komplexere zu finden. Und ich hätte ihn selber gefunden ( sich da sicher ist ) ( gonz ist eh ein "das Rad immer neu erfinder" )

Aber letzteres ist Spekulation. Ich schreibe das eigentlich nur, damit du ggf. etwas hast, was eingängiger ist. Besser machen kann man es dann immer noch.

Grüsse nochmal
Gonz/Gerhard

PS.: Und man kann - dritte Möglichkeit von wahrscheinlich noch vielen anderen - das mit Rekursion lösen :) was immer recht elegant ist.
Aber vielleicht dem Softwerker aus grundsätzlichen Überlegungen nicht gefällt... ( aber das ist eine andere Geschichte und soll ein andermal erzählt werden feix )





-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1324
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2019-04-21


Man kann eine vollständige Suche auch noch beschleunigen.
Wenn die (während der Suche) aktuell gefundene Bestlösung eine max. Tagesstrecke von z.B. 26km enthält, ist klar, dass man beim Durchsuchen der restlichen Lösungskandidaten alle die überspringen kann, die eine längere Teilstrecke enthalten.
Das bietet sich besonders bei einer rekursiven Lösung an, bei der sukzessive Teilstrecken hinzugefügt werden. Dann kann man den entsprechenden Teilbaum in der Suche abschneiden.

Kay



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-04-21


Das stimmt. Man könnte sogar ( wenn es größere Datenmengen werden und die Laufzeit relevant wird ) zunächst plausibele Annahmen treffen und danach schon einmal möglichst kleine Zielwerte erreichen, um bei der folgenden Breitensuche dann möglichst viel abschneiden zu können.

Und man kann sicher weitergehen, wenn man damit noch unter der Ideallösung ( Gesamtlänge durch Tageszahl ) bleibt. Damit dürfte insgesamt der Baum schon recht weit gestutzt werden können.


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26756
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2019-04-21


Ok, hier die rekursive Lösung zur Erzeugung aller Tagesetappen, also die Liste wie in Beitrag #6 ohne die Max-Spalte:
C++
void Zaehlen(
          const int E
         ,const int T
         ,int Z[]
         ,const int S   // Etappensumme der vorherigen Tage
         ,const int t   // Tag (Zählung beginnt bei 0) <=> Index für Z
         )
{
   if (t == T-1) // letzter Tag
   {
      Z[t] = E-S;    // alle restlichen Etappen müssen durchlaufen werden
      // in Z steht jetzt die Anzahl Etappen pro Tag
      // erst mal einfach nur ausgeben
      for (int i=0; i<T; i++)
      {
         cout << Z[i] << " ";
      }
      cout << "\n";
      return;
   }
 
   for (Z[t] = 1; Z[t] <= E-S-(T-(1+t)); Z[t]++)
   {
      Zaehlen(E, T, Z, S+Z[t], t+1);
   }
}
 
int main()
{
   const int   E = 6,   // Etappen
               T = 3;   // Tage
   int         Z[T];    // Zähler für Etappen pro Tag
 
   cout << "Start\n";
   Zaehlen(E, T, Z, 0, 0);
   cout << "Ende\n";
   return 0;
} // main

In Zaehlen(..) kann man dann die oben bereits erwähnten Optimierungen einbauen. Und überhaupt natürlich die Berechnung der Tagesmärsche.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-04-21


Genau... Butter bei die Fische * smile

python
# HOUSES.PY by gonz@gmx.biz
 
# Das Problem der optimalen Einteilung einer Wanderstrecke in Tagesstrecken
# ( Partitionierung, aka "part" ) bei gegebenen Übernachtungsmöglichkeiten.
# Quelle: guckst du auf Matroid's Matheplanet: https://tinyurl.com/y2myp9h5
 
# Dieses Codestück ist frei verfügbar unter der MIT Lizenz. 
# https://de.wikipedia.org/wiki/MIT-Lizenz
# Enjoy and have fun!
 
# Versionsgeschichte:
# Vers. 1.00 - Ostersonntag 2019
print ("HOUSES.PY\nVers. 1.00 by gonz@gmx.biz\n");
 
# Die Daten des Problems. nebenbei: Grossschreibung für die
# Konstanten, und alles mit Plural-"s" - damits einheitlich ist. 
 
HOUSES = 25
# Es gibt ein Haus mehr als Teilstrecken, da am
# Anfang und am Ende der Gesamtstrecke je ein Haus steht.
 
STOPS  = 11
# der letzte Stop ist der beim Erreichen der Gesamtstrecke.
# es gibt also genausoviele Stops wie Tagestouren.
# Nebenbedingung: Es muss mindestens ein Haus mehr geben als Stops :)
 
DISTANCES = [6,2,5,5,6,10,5,2,6,2,
             5,6,10,5,2,6,2,8,5,6,
             2,8,5,6]
# es gibt einen Abstand weniger als Häuser ...
# DISTANCE[0] ist der Wegabstand von Haus 1 zu Haus 2.
# und damit haben wir alles was wir an Daten zum Problem brauchen :)
 
# Hier beginnt also die eigentliche Arbeit des Programms
 
# Wir wollen im folgenden alle möglichen Parttitionen durchgehen
# und werden uns dabei on the fly die jeweils bisher beste
# gefundene Lösung merken.
 
BestValue = 1000 # einfach... sehr viele, wir suchen ein Minimum
# Die beste Partition brauchen wir uns gar nicht zu merken,
# wir geben einfach nur dann etwas aus, wenn es besser war
# damit steht am Ende die optimale Partition unten auf der Konsole.
 
# Anfangebedingung: eine Minimalroute
# jeden Tag eine Strecke - und am letzten Tag den Rest
ThisPart = [0]*(STOPS+1)
for X in range(1,STOPS):
    # Achtung: In der Ersten Nacht übernachten wir im zweiten Haus!
    ThisPart[X]=X+1
ThisPart[STOPS]=HOUSES
# Die Partition ist also immer so aufgebaut:
# auf Part[1]..Part[STOPS-1] steht die Nummer des Hauses,
# in dem wir bei dem betreffenden Stop übernachten. Damit
# muss der Wert für den letzten Stop das letzte Haus sein,
# damit wir auch ankommen! 
 
# und ab geht die Post!
Fertig = False
while not Fertig:
    # aktuelle Partition für Ausgebe vorbereiten
    AusgabeStr=""
    # zur Erinnerung: range liefert Werte im Bereich
    # Startwert ... Stopwert-1
    for X in range(1,STOPS+1):
        AusgabeStr+=str(ThisPart[X])+" "
    # berechnen was die aktuelle Partition so bietet
    ThisStart = 1
    ThisMax   = 0
    for X in range(1,STOPS+1):
        ThisDist = 0
        for Y in range(ThisStart,ThisPart[X]):
            ThisDist += DISTANCES[Y-1]
        ThisStart = ThisPart[X]
        if ThisDist>ThisMax:
            ThisMax=ThisDist
    # ggf ist es ja die (aktuell) beste Partition?
    if ThisMax < BestValue:
        BestValue = ThisMax
        print(AusgabeStr+" - new best choice. Max = "+str(ThisMax))
    elif ThisMax == BestValue:
        print(AusgabeStr+" - just as well")
 
    # und nun... Butter bei die Fische!
    # wir suchen die nächste Partition.
    # angenommen, wir seien fertig
    Fertig=True
    # suchen wir doch noch einen weitere partition :)
    # indem wir, von hinten beginnend, einen Wert suchen,
    # den wir noch erhöhen können. Nicht den letzten, denn
    # wir wollen ja ankommen. Und er kann nur erhöht werden,
    # wenn dann noch Platz für die verbleibenden Stops ist...
    IncreaseStop=STOPS-1
    while Fertig and IncreaseStop>0:
        if ThisPart[IncreaseStop]<HOUSES-(STOPS-IncreaseStop):
            Fertig=False
            ThisPart[IncreaseStop]+=1
            # und die verbleibenden Tage wieder nur je eine Strecke.
            for X in range(IncreaseStop+1,STOPS):
                ThisPart[X]=ThisPart[IncreaseStop]+(X-IncreaseStop)
        else:
            IncreaseStop-=1
# alles getan...
print ("\nWork is done. Have fun!")



Ich habe ein bissl ausprobiert, wann die Rechenzeit anfängt länger zu werden. In dem hier eingestellten Beispiel sind 24 Teilstrecken auf 11 Tagesmärsche aufzuteilen. Das mit diesem Code so etwas über eine halbe Minute.


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
grezebeze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 14.06.2015
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2019-04-21


Vielen vielen Dank für die wirklich ausgezeichnete Hilfestellungen! Das hilft mir gerade enorm! Ich werde mich jetzt noch  dahinter setzen und melde mich, falls ich an Probleme stoße!

Und ebenfalls frohe Ostern :)



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5504
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2019-04-21


Hallo,

Hier noch eine einfache Variante ohne Rekursion smile
Rust
fn perm(a: &mut Vec<usize>) -> bool {
    let s = a.len()-1;
    if s==0 {false}
    else if a[s]!=0 {
        a[s]-=1;
        a[s-1]+=1;
        true}
    else {
        let mut p=s-1;
        while p>0 && a[p]==0 {p-=1;}
        if p==0 {false}
        else {
            a[p-1]+=1;
            a[s]=a[p]-1;
            a[p]=0;
            true}}}
 
fn main() {
    let mut a: Vec<usize> = vec![0,0,3];
    let b: Vec<u32> = vec![11,16,5,5,12,10];
    let mut r: Option<(Vec<usize>, u32)> = None;
    while {
        let mut y: Vec<u32> = vec![];
        a.iter().fold(&*b, |x,t| {let (c,s) = x.split_at(t+1); y.push(c.iter().sum()); s});
        let m = *y.iter().max().unwrap();
        let t = Some((a.clone(),m));
        r = if let Some(x) = r {if x.1>m {t} else {Some(x)}} else {t};
        perm(&mut a)} {}
    r.map(|(r1,r2)| println!("{} {:?}", r2, r1.iter().map(|x|x+1).collect::<Vec<usize>>()));}

--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



  Profil  Quote  Link auf diesen Beitrag Link
grezebeze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 14.06.2015
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2019-04-22


Ich bin nun relativ gut zurecht gekommen. Nur häng ich gerade an einer programmiertechnischen Sache fest. Ich habe den Code von viertel soweit erweitert, dass er mir die pro Tag zurückgelegte Distance angibt, sowie die maximale Distanz der jeweiligen Wanderung. Nun würde ich mir wünschen, als Ausgabe die Tagesdistanzen sowie die maximale Tagesstrecke, der Wanderung dessen Tagesstrecke am kleinsten von allen ist.

Mein Code:
C++
#include "pch.h"
#include <iostream>
#include <vector>
 
using namespace std;
 
int SumOfListElements(int ListOfIntegers[], int Start, int End)
{
	if (Start > End)
		return 0;
	else return ListOfIntegers[Start] + SumOfListElements(ListOfIntegers, Start + 1, End);
}
 
int MaximumOfList(int ListOfIntegers[], int size)
{
	int max = ListOfIntegers[0];
	if (size > 1)
	{
		for (int i = 0; i < size; i++)
		{
			if (ListOfIntegers[i] > max)
				max = ListOfIntegers[i];
		}
	}
	return max;
}
void Zaehlen(int ListOfDistances[], const int Stages, const int Days, int StagesPerDay[], int DistancePerDay[], const int SumOfPreviousDays, const int CurrentDay)
{
	if (CurrentDay == Days - 1) // letzter Tag
	{
		StagesPerDay[CurrentDay] = Stages - SumOfPreviousDays;    
		int PassedStages = 0;
 
		for (int i = 0; i < Days; i++)
		{
 
			DistancePerDay[i] = SumOfListElements(ListOfDistances, PassedStages, PassedStages+StagesPerDay[i]-1 );
			PassedStages += StagesPerDay[i];
			cout << DistancePerDay[i] << " ";
		}
		int max = MaximumOfList(DistancePerDay, Days);
		cout << max << " ";
		cout << "\n";
		return;
	}
	int RemainingDays = Stages - SumOfPreviousDays - (Days - (1 + CurrentDay));
	for (StagesPerDay[CurrentDay] = 1; StagesPerDay[CurrentDay] <= RemainingDays; StagesPerDay[CurrentDay]++)
	{
		Zaehlen(ListOfDistances, Stages, Days, StagesPerDay, DistancePerDay, SumOfPreviousDays + StagesPerDay[CurrentDay], CurrentDay + 1);
	}
}
 
int main()
{
	const int   Stages = 6, Days = 3;  
	int         StagesPerDay[Days];    // Zähler für Etappen pro Tag
	int			ListOfDistances[Stages] = { 11,16,5,5,12,10 };
	int		    DistancePerDay[Days];
	cout << "Start\n";
 
	Zaehlen(ListOfDistances, Stages, Days, StagesPerDay, DistancePerDay, 0, 0);
	cout << "Ende\n";
	return 0;
} 

Ausgabe sollte sein: Tag 1: 16 km, Tag 2: 26 km, Tag 3: 22 km. Max.: 26.
Vielleicht kann mir jemand weiterhelfen und ein paar Hinweise geben. Vielen Dank :)



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5504
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2019-04-22


Hallo,

Ein Beispiel dafür findet sich in Beitrag No.15, oder für die Ausgabe in der Form: [11, 26, 22] 26 etwas schöner wie folgt: smile
Rust
fn perm(a: &mut Vec<usize>) -> bool {
    let s = a.len()-1;
    if s==0 {false}
    else if a[s]!=0 {
        a[s]-=1;
        a[s-1]+=1;
        true}
    else {
        let mut p=s-1;
        while p>0 && a[p]==0 {p-=1;}
        if p==0 {false}
        else {
            a[p-1]+=1;
            a[s]=a[p]-1;
            a[p]=0;
            true}}}
 
fn main() {
    let mut a: Vec<usize> = vec![0,0,3];
    let b: Vec<usize> = vec![11,16,5,5,12,10];
    let mut r: Option<(Vec<usize>, usize)> = None;
    while {
        let v: Vec<usize> = a.iter().scan(0, |s,&x| {
            let t=*s; *s=*s+x+1; Some(b[t..*s].iter().sum())}).collect();
        let m = *v.iter().max().unwrap();
        let t = (v,m);
        r = Some(if let Some(x)=r {if x.1>m {t} else {x}} else {t});
        perm(&mut a)} {}
    r.map(|(r1,r2)| println!("{:?} {}", r1, r2));}
Allerdings bin ich mir nicht ganz sicher, woran du gerade hängst...

--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26756
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2019-04-23


2019-04-22 19:46 - matph in Beitrag No. 17 schreibt:
Hallo,

Ein Beispiel dafür findet sich in Beitrag No.15, …
Als ob das außer dir noch jemand lesen geschweige denn in C++ umsetzen könnte confused



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5504
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2019-04-23


Hallo,

Ich gehe einmal davon aus, dass dies kein Problem darstellt smile
Es gibt natürlich minimale Unterschiede, so schreibt man statt push in C++ push_back, fold wird zu accumulate, option zu optional und statt max verwendet man max_element wink

--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



  Profil  Quote  Link auf diesen Beitrag Link
grezebeze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 14.06.2015
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, vom Themenstarter, eingetragen 2019-04-23


Danke für die Antwort. Aber leide komme ich wirklich nicht mit der Übertragung von deinen Code auf C++ klar. Bin allgemein nicht allzu fit im Programmieren.
naja ich weiss eben nicht genau, an welcher Stelle und wie ich was einbauen muss, damit ich die gewünschte Ausgabe, also genau die Tagesstrecken des Tages mit minimaler Maxstrecke, erhalte... Ich vermute das wird in der if anweisung der zaehlen methode geschehen müssen... Hab etwas rumgespielt aber kam auf keinen grünen zweig...



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2019-04-23


Hallo grezebreze,

bist du denn überhaupt sicher, dass das Programm in der Form, die du gepostet hast, das gewünschte leistet? Ich würde mir das nochmal in Ruhe durchgehen und überlegen, was da wo passiert. Vielleicht kannst du uns verbal beschreiben, welche Routine was macht.

Grüße
Gerhard/Gonz


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2019-04-23


Und - was jetzt für dich nicht Thema ist, mich aber allgemein interessiert ( ggf. in einen neuen Thread packen? ) mich würde schon interessieren, wie man den Algorithmus optimal formen kann und welche Laufzeit er dann hat.

Ich hätte im ersten Anlauf gedacht, dass es ungefähr mit n! geht ( irgendwie n ein Maß für die Anzahl der Strecken und der Zwischenstopps ), aber mit ein paar Messungen an meinem Algo denke ich, dass das zu pessimistisch ist.

Eine etwas bessere Schätzung könnte sein, dass es ggf. mit 2^n geht, etwa mit der Überlegung, dass man bei jeder Tagestour ja mindestens solange Strecken dazu nehmen kann, wie man unter dem theoretischen Minimum ist ( also Gesamtstrecke durch Gesamttage ) und aufhören kann, wenn man den bisherigen Bestwert mit dieser Teilstrecke andernfalls überschreiten könnte. Angenommen für jede Tagestour gäbe es damit nur +-1 sinnvolle Länge, käme man eben auf 2^n Kombinationen dieser Längen...

Das wären zB bei 40 Häusern immer noch eine nicht praktikabele Sache. Aber vielleicht geht es ja noch effizienter?

Grübelnde Grüße aus dem Harz
Gerhard/Gonz


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
grezebeze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 14.06.2015
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, vom Themenstarter, eingetragen 2019-04-23


Danke gonz!
Naja das Programm wie ich es gepostet habe, berechnet mir eben genau die Tagesstrecken einer Wanderung (wovon es im Beispiel mit Etappen=6 und Tage=3 insgesamt 10 gibt, und allgemein glaube ich \(\frac{(Etappen-1)!}{(Tage-1)!(Etappen-Tage)!}\), was aber nebensächlich ist).
Die Rekursion liefert alle möglichen Szenarien, also alle Partitionen der Zahl die der Anzahl an Etappen entspricht, wie eine Wanderung geplant werden kann.
Desweiteren erhalte ich auch die maximale Tagesstrecke pro Wanderung.

Mir ist ganz genau klar, was die rekursive Methode macht.
Ich erhalte also für jede Wanderung die Tagesstrecken und die maximale Tagesstrecke davon. Dies entspricht schon fast der Ausgabe die ich mir erwünsche. Nur würd ich jetzt gerne nur DIE eine Wanderung ausgegeben haben, dessen maximale Tagesstrecke minimal ist.

Daran scheitere ich aber kläglich. Ich hab mir überlegt alle jeweiligen Maxima in ein Array oder Vector zu speichern und davon das Minimum suchen. Das bekomm ich allerdings innerhalb der Rekursion nicht hin und bin mir auch nicht sicher, ob das überhaupt die richtige Vorgehensweise ist.

Vielleicht hat dazu noch irgend jemand einen Hinweis.

Viele Grüße :)



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26756
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2019-04-23


Du kannst einen weiteren Parameter (ein Array der Länge T) mitschleppen, in dem du das bisher beste gefundene Ergebnis ablegst.
In main gibst du dieses Array dann aus, wenn also die Rekursion vollständig abgearbeitet ist.



  Profil  Quote  Link auf diesen Beitrag Link
grezebeze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 14.06.2015
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, vom Themenstarter, eingetragen 2019-04-23


So hab ich es auch versucht. Ich wollte zunächst mal einen Zähler in die Zaehlen Methode einbauen, welcher mir die Anzahl der Wanderungen (also die Anzahl aller Partitionen) ausgibt. Ich habe es so probiert:
C++
void Zaehlen(int ListOfDistances[], const int Stages, const int Days, int StagesPerDay[], int DistancePerDay[], const int SumOfPreviousDays, const int CurrentDay, int count)
{
	if (CurrentDay == Days - 1) // letzter Tag
	{
                count++
		StagesPerDay[CurrentDay] = Stages - SumOfPreviousDays;    
		int PassedStages = 0;
 
		for (int i = 0; i < Days; i++)
		{
 
			DistancePerDay[i] = SumOfListElements(ListOfDistances, PassedStages, PassedStages+StagesPerDay[i]-1 );
			PassedStages += StagesPerDay[i];
			cout << DistancePerDay[i] << " ";
		}
		int max = MaximumOfList(DistancePerDay, Days);
		cout << max << " ";
		cout << "\n";
		return;
	}
	int RemainingDays = Stages - SumOfPreviousDays - (Days - (1 + CurrentDay));
	for (StagesPerDay[CurrentDay] = 1; StagesPerDay[CurrentDay] <= RemainingDays; StagesPerDay[CurrentDay]++)
	{
		Zaehlen(ListOfDistances, Stages, Days, StagesPerDay, DistancePerDay, SumOfPreviousDays + StagesPerDay[CurrentDay], CurrentDay + 1,count);
	}
}
count soll also um eins erhöht werden, wenn man beim letzten Tag angelangt ist. Allerdings gibt count mir immer nur "1" aus. Ich denke, dass es daran liegt, dass in der Methode Zaehlen ja immer wieder die Variable count neu deklariert wird.

Aber ich hab keinen Plan, wie ich es anders machen könnte..



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5838
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, eingetragen 2019-04-23


Hier mein rekursives Programm in Matlab.
Kurze Strecken am Anfang und am Ende der Tour werden automatisch zusammengefasst.
Außerdem gibt es die Möglichkeit, obere Schranken für die optimale Lösung (zum Bsp. aufgrund einer bekanten Lösung) mitzugeben und das Programm dadurch zu beschleunigen.
Verwendet werde auch obere Schranken aus bereits fertiggerechneten Teilbäumen, es werden aber keine obere Schranken aus heuristisch ermittelten Lösungen berechnet.

Probleme mit 80 Teilstrecken(*) habe ich damit noch gut hinbekommen.
(*) Sowie eine Instanz mit den Primzahlen <1000, die aus 168 Teilstrecken besteht.
Matlab
function Erg=maxStrecke(A,k,maxi)
 
% A = Vektor der Streckenlängen
% k = Anzahl der Zwischenstops (=Abschnitte - 1)
% maxi = Beste bekannte Lösung
 
if k==0  % keine Übernachtung mehr
    Erg=sum(A); return
end
if length(A)<=k+1  % Übernachtung nach jeder Wegstrecke möglich
    Erg=max(A); return
end
if max(A)>=maxi || sum(A)/(k+1)>=maxi  % Eine Lösung, die besser ist als maxi kann es nicht geben
    Erg=maxi; return
end
 
while A(1)+A(2)<= min( max(A), sum(A)/(k+1));     
    % Es ist optimal, die ersten beiden Abschnitte zusammenzufassen
    A=[A(1)+A(2), A(3:end)];
end
while A(end-1)+A(end)<= min( max(A), sum(A)/(k+1));     
    % Es ist optimal, die letzten beiden Abschnitte zusammenzufassen
    A=[A(1:end-2),A(end-1)+A(end)];
end
 
% Möglichkeit 1: Übernachtung nach der ersten Teilstrecke + Lösung des
% Restproblems
E1=max(A(1),maxStrecke(A(2:end),k-1,maxi)); 
 
% Möglichkeit 2: Keine Übernachtung nach der ersten Teilstrecke --> Die
% ersten beiden Strecken werden zusammengefasst + Lösung des Teilproblems
% Falls bei der Möglichkeit 1 eine bessere Lösung gefunden wurde, wird dies
% bei der Bearbeitung von Möglichkeit 2 berücksichtigt.
A2=[A(1)+A(2), A(3:end)];
E2=maxStrecke(A2,k,min(E1,maxi));
Erg=min(E1,E2);
return
 

Bemerkung:
Auf das Mitschleifen einer optimalen Lösung habe ich verzichtet, da man aus dem optimalen Zielfunktionswert sehr einfach eine optimale Lösung berechnen kann.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2019-04-23


Liebe Freunde der mehrtägigen Wanderungen,

manchmal sieht man ja den Wald vor lauter Bäumen nicht. Der Satz "Aus dem optimalen Zielfunktionswert kann man sehr einfach eine optimale Lösung berechnen." läßt sich umkehren. Man gehe einfach, vom theoretisch kleinsten Wert aus beginnend, der Reihe nach die möglichen Werte durch und schaue, ob es dazu eine Lösung gibt....

Das geht super fix, und damit dürfte die Laufzeit für große Anzahlen von Stopps/Häusern auch nur noch mit n^2 wachsen...

Python
import math
 
# Festlegung der Parameter des Problems
 
HOUSES = 81
STOPS  = 30
DISTANCES = [6,2,5,5,6,10,5,2,6,2,
             5,6,10,5,2,3,2,8,5,6,
             6,2,5,5,6,12,5,2,6,2,
             5,6,10,5,2,6,2,8,5,6,
             6,2,5,5,6,10,5,2,6,2,
             5,6,10,5,2,2,2,8,5,6,
             6,2,5,7,6,10,5,2,6,2,
             5,6,10,5,2,6,2,8,5,6 ]
 
# Die Bestimmung eines Minimums für den Zielwert
# Mindestens die Gesamtlänge geteilt durch die Anzahl der Teilstrecken, 
# und mindestens so groß wie die längste Teilstrecke.
 
Gesamt=0
Max=0
for X in range(0,HOUSES-2):
    Gesamt+=DISTANCES[X]
    if DISTANCES[X]>Max:
         Max = DISTANCES[X]
 
BestValue=math.ceil(Gesamt/STOPS)
if Max>BestValue:
    BestValue=Max
 
# und nun versuchen wir, für diese Vorgabe
# eine passende Lösung zu finden. Wenn nicht
# wir eben BestValue incrementiert, solange, 
# bis etwas zu finden ist :)
 
Found=False
while not Found:
    ThisDist  = 0
    ThisStops = 0
    for X in range(0,HOUSES-1):
        if ThisDist+DISTANCES[X]>BestValue:
            # wir übernachten und es beginnt eine neue Tagestour
            ThisStops+=1
            ThisDist=DISTANCES[X]
        else:
            # wir können noch eine Strecke weitergehen
            ThisDist += DISTANCES[X]
    # So. Es gibt noch den Stopp am Ende der Wegstrecke...
    if ThisStops<STOPS:
        # und damit sind wir fertig, wenn:
        Found=True
    else:
        # oder wir probieren eben den nächsthöheren Zielwert...
        BestValue+=1
 
# und nun noch die zugehörige Lösung rekonstruieren und ausgeben
 
ThisDist=0
ThisStops=0
for X in range(0,HOUSES-1):
        ThisDist += DISTANCES[X]
        if ThisDist>BestValue:
            ThisStops+=1
            print(str(ThisStops)+". Halt bei Haus "+str(X+1)
                  +" Tagesstrecke="+str(ThisDist-DISTANCES[X]))
            ThisDist=DISTANCES[X]
print(str(STOPS)+". Halt bei Haus "+str(HOUSES)
    +" Tagesstrecke="+str(ThisDist))
print("Maximale Tagesstrecke = "+str(BestValue))



-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5504
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, eingetragen 2019-04-23


Hallo,

Das Thema ist zwar nun bereits Optimierung, doch der Vollständigkeit halber noch der mehr oder weniger äquivalente C++ Code zu Beitrag No.17 smile
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <optional>
#include <utility>
using namespace std;
 
bool perm(vector<int> &a){
  auto s = a.size()-1;
  if(s==0){return false;}
  else if(a[s]!=0){
    a[s]-=1;
    a[s-1]+=1;
    return true;}
  else {
    auto p=s-1;
    while(p>0 && a[p]==0){p-=1;}
    if(p==0){return false;}
    else {
      a[p-1]+=1;
      a[s]=a[p]-1;
      a[p]=0;
      return true;}}}
 
int main(){
  vector<int> a{0,0,3};
  vector<int> b{11,16,5,5,12,10};
  optional<pair<vector<int>,int>> r = nullopt;
  do {
    vector<int> v; auto s=b.begin();
    for(const auto &x:a){
      auto t=s; advance(s,x+1);
      v.push_back(accumulate(t,s,0));}
    auto m = *max_element(v.begin(),v.end());
    pair<vector<int>,int> t (v,m);
    if(r.has_value()){if(r.value().second>m) r=optional{t};}
    else r = optional{t};
  } while(perm(a));
  for(const auto &x:r.value().first)
    cout << x << " ";
  cout << "max: " << r.value().second << endl;}

--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5838
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, eingetragen 2019-04-23


@gonz: Bei ganzzahligen Weglängen ergibt dein Ansatz einen Pseudopolynomialzeit-Algorithmus (d.h. polynomiell in der Eingabelänge bei unärer Codierung).
Das das Ganze polynomiell in n (=Anzahl der Wegstücke?) ist, sehe ich eher nicht...

EDIT: In dem Moment wo ich es abgeschickt habe, fällt es mir auf. Wenn man Intervallhalbierungen macht, ist es sehr wohl polynomiell in der Eingabelänge. Ein nettes Problem, mit einer überraschend schnellen Lösung.





  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3068
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.30, eingetragen 2019-04-24


@Kitaktus

ich gebe zu dass ich da sehr schlampig argumentiert habe. Es bleibt mit dem Algorithmus aus #27 jedenfalls festzustellen, dass wenn die Teilstrecken in ganzen Zahlen angegeben sind ( also als Vielfache einer Basislänge, zB km, Hektometer oder Meter), die Komplexität in Abhängigkeit von der Gesamtstrecke und der Anzahl der Teilstrecken polynominal ist ( und zwar mit kleinem Exponenten).

Ich muss maximal für jeden möglichen Wert der Zielfunktion, also jeden Wert im Bereich bis zur Gesamtstreckenlänge, jeweils alle Teilstrecken durchgehen und einzeln gucken, ob sie noch auf die aktuelle Tagesstrecke aufsummiert werden können, um am Ende zu prüfen, ob ich mit der vorgegebenen Stoppzahl ausgekommen bin.


Klar könnte ich, anstatt wie in #27 einfach linear mit dem kleinsten möglichen Zielwert anzufangen, hier auch noch mit Intervallhalbierung arbeiten. Dann wäre ich bei einer Laufzeit proportional zu

log(Gesamtlänge) * Anzahl_Häuser

Irgendwie faszinierend.







-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5838
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.31, eingetragen 2019-04-24


Das was Du in Beitrag #30 beschreibst, nennt man "Pseudopolynomielle Laufzeit", hier im Beispiel hieße dass: Polynomiell in der Gesamtlänge der Wegstrecken, was nicht gleichbedeutend ist mit "Polynomiell in der Länge der Eingabe".
Algorithmen mit pseudopolynomiellen Laufzeiten gibt es z.B. auch für das Rucksackproblem.
_Hier_ kann man durch Intervallhalbierung dem Algorithmus zu einer (echten) polynomiellen Laufzeit verhelfen, das geht beim Rucksackproblem (vermutlich) nicht.



  Profil  Quote  Link auf diesen Beitrag Link
grezebeze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 14.06.2015
Mitteilungen: 120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.32, vom Themenstarter, eingetragen 2019-04-26


Ich wollte mich noch bei allen hier beteiligten Mitgliedern für die wirklich äußerst hilfreichen Beiträge und verschiedensten Lösungsvorschläge bedanken.
Meine Fragen sind alle beantwortet. Ich hoffe Ihr hattet auch Spaß daran, euch mit der Aufgabe zu beschäftigen :-)

Schönen Tag euch allen!



  Profil  Quote  Link auf diesen Beitrag Link
grezebeze hat die Antworten auf ihre/seine Frage gesehen.
grezebeze hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]