Sortierung der Kanten in Prim

MikMik
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 24. Apr 2015 18:56

Sortierung der Kanten in Prim

Beitrag von MikMik »

Ich habe mir vor einigen Tagen das Erste mal das Foo Testat Prim angesehen und muss sagen, dass die größte Schwierigkeit bei diesem ist, die Kanten, welche man in die Liste einfügen möchte in der Auswahl zu finden.
Verstehen tue ich nicht ganz, warum man sie nicht einfach alphabetisch sortieren kann jeweils nach dem in lexikographische Reihenfolge als ersten kommenden Buchstaben.
Vermutlich wäre das nicht allzu großer Aufwand, und ich finde es ziemlich unnötig das Testat an solchen umsignifikanten Stellen durch unsortiert Kanten zu erschweren.
Natürlich stellt uns das nicht vor unlösliche Aufgaben, aber dennoch finde ich es nervend und unnötige Zeitaufwendung jeden der Strings aus einer unsortierten Liste heraussuchen zu müssen.

Benutzeravatar
luedecke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 17. Mär 2015 00:08

Re: Sortierung der Kanten in Prim

Beitrag von luedecke »

Ja, diesen Punkt hatte ich bereits beim Review schon bemängelt.

Wir arbeiten derzeit an einer Lösung dafür am Kruskal, können bisher aber nur eine lexikographische Lösung anbieten, in der erst nach vorderem Buchstaben und dann nach dem hinteren sortiert wird.
Ich finde das immer noch nicht ganz optimal, da ich gerne das Identitätsproblem \((a,d) \equiv (d,a)\) so lösen würde, dass der lexikographisch niedrigere Buchstabe namensgebend in jedem Tupel der Kanten ist.

Benutzeravatar
luedecke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 17. Mär 2015 00:08

Re: Sortierung der Kanten in Prim

Beitrag von luedecke »

luedecke hat geschrieben:Ja, diesen Punkt hatte ich bereits beim Review schon bemängelt.

Wir arbeiten derzeit an einer Lösung dafür am Kruskal, können bisher aber nur eine lexikographische Lösung anbieten, in der erst nach vorderem Buchstaben und dann nach dem hinteren sortiert wird.
Ich finde das immer noch nicht ganz optimal, da ich gerne das Identitätsproblem \((a,d) \equiv (d,a)\) so lösen würde, dass der lexikographisch niedrigere Buchstabe namensgebend in jedem Tupel der Kanten ist.
Update kommt heute zwischen 16 und 17 Uhr. Kruskal wird dann auch zur Verfügung stehen.

Antworten

Zurück zu „Archiv“