Projektne naloge

Tiri

Naloga

Dana je množica enot E = { X_i : i = 1 .. n }. Na vsaki enoti X_i izmerimo vrednosti izbranih k lastnosti (spremenljivk). Lestvica je vsaj urejenostna - merimo s številskimi vrednostmi. Tako dobimo k-razsežen vektor - opis enote

X_i = [ x_i,1, x_i,2, ..., x_i,k ]

Na primer i Food Engy Prot Fat Calc Iron 1 Beef, braised 340 20 28 9 2.6 2 Hamburger 245 21 17 9 2.7 3 Beef, roast 420 15 39 7 2.0 4 Beef, steak 375 19 32 9 2.6 5 Beef, canned 180 22 10 17 3.7 6 Chicken, broiled 115 20 3 8 1.4 7 Chicken, canned 170 25 7 12 1.5 8 Beef heart 160 26 5 14 5.9 9 Lamb leg, roast 265 20 20 9 2.6 10 Lamb shoulder, roast 300 18 25 9 2.3 11 Smoked ham 340 20 28 9 2.5 12 Pork, roast 340 19 29 9 2.5 13 Pork, simmered 355 19 30 9 2.4 14 Beef tongue 205 18 14 7 2.5 15 Veal cutlet 185 23 9 9 2.7 16 Bluefish, baked 135 22 4 25 0.6 17 Clams, raw 70 11 1 82 6.0 18 Clams, canned 45 7 1 74 5.4 19 Crabmeat, canned 90 14 2 38 0.8 20 Haddock, fried 135 16 5 15 0.5 21 Mackerel, broiled 200 19 13 5 1.0 22 Mackerel, canned 155 16 9 157 1.8 23 Perch, fried 195 16 11 14 1.3 24 Salmon, canned 120 17 5 159 0.7 25 Sardines, canned 180 22 9 367 2.5 26 Tuna, canned 170 25 7 7 1.2 27 Shrimp, canned 110 23 1 98 2.6 Take, večrazsežne podatke lahko prikažemo tako, da narišemo k vzporednih pokončnih in enakorazmaknjenih daljic iste dolžine - za vsako spremenljivko po eno. Posamezno vrednost x_i,j linearno preslikamo na ustrezno daljico. Prikaz posamezne enote dobimo kot tir, ki povezuje (z daljicami) ustrezne slike vrednosti spremenljivk na sosednjih daljicah.
Za različne urejenosti (vrstne rede) spremenljivk dobimo bolj ali manj pregledne prikaze. Merilo za preglednost je število presečišč med tiri.

Sestavi program, ki bo za dano množico enot določil tako urejenost spremenljivk, da bo ustrezni prikaz s tiri čim preglednejši. Vgradi tudi možnost 'preklopa spremenljivke' - pri vsaki daljici, ki predstavlja zalogo vrednosti neke spremenljivke, se lahko še odločimo ali je spodnja največja ali najmanjša vrednost.

n <= 2000, k <= 100

Za primere podatkov poglejte na Datasets.

Namig

Nalogo lahko prevedemo na iskanje Hamiltonove poti v (polnem) grafu, v katerem so točke spremenljivke, vrednosti povezav pa enake številu presečišč v dvodelnem grafu daljic (tirov) med ustreznima spremenljivkama.