V
Master User schrieb:
Classiche traveling salesman Problem, wenn jemand eine Seite kennt, mit beispielen und so, wie ich das Lösse wehre ich dankbar. Die habe ich gemacht aber ich bin mir nicht 100% sicher, fast jede seite die ich gefunden habe benutzt was anderes.
das traveling-salesman-problem ist auch eine spielewiese für hobby-informatiker. und die korrekte lösung ist unanständig langsam und heuristiken sind hier sehr willkommen. zum beispiel, wenn man einfach nur stets die nächste stadt anfährt, ist die lösung nicht länger als doppelt so lang wie die optimale lösung, wenn ich mich recht erinnere. das ist doch schonmal ne starke garantie!
Schreibe ein algorihmus mit Laufzeit O(nlog k) der folgendes problemm lösst. Zussamenfugen von k listen in einer geornenden liste, wobei n die grosse aller daten aller k listen, benutze dazu MinHeap. Mein algorithmus braun O(nlogn) dazu.
äh. er hat dich bereits gesagt, daß du MinHeap dazu benutzen sollst.
baue einfach einen MinHeap, der k blätter auf der untersten ebene hat. und nimm in der großen schleife immer am anfang ein element weg, lass das loch hochblubbern zu einem der k blätter und fülle beim entstandenen blattloch aus der entsprechenden liste nach. jede liste gehört zu genau einem blatt. nähere details findest du in älteren algorithmen-büchern bei merge-sort. damals hatte man k bandlaufwerke und mußte die mergen.
Es werden zwei arrays gegeben X[1…n] und Y[1…n] die sortiert sind nach aufsteigenden wird. Gebe ein Algorithmus mit Laufzeit O(log n) das den mittleren werd von den 2n Daten zuruckibt von den arrays X und Y. Ich habe da ein gready algorithmus gefunden der findet den mittleren wert des arrays und spaltet dann den array wieder in den mitte solange bis ich nur noch ein wird in array da ist. Aber ich weis nicht.
ich hätte die arrays ja in O(n) gemerged und dann die mitte angeguckt. es stand ja nix von speicher-sparen da. aber wenn du einen beseren hast, dann nimm ihn.
edit: idee gut, ausführung schlecht. einfach nicht echt mergen, sondern nur so tun als ob und die daten nicht in ein dickeres array schreiben. aber an der stelle anhalten, so man das mittlere elemet schreiben würde.
Gegeben wird eine Menge x1, x2,..xn. Finde ein Algorithmus der die menge in kleinen mengen aufteilt mit spanweite 1, also von [y, y+1].
sortieren und durchrutschen. laufzeit O(n*log(n)).
