Sortiranje mnozice stevil glede na non-tranzitivno relacijo

[Nejc Skoberne]

Zdravo.

Saj vem, da je moja seminarska, a mogoce mi bo vseeno kdo dal kaksen
namig. :)

Torej imamo non-tranzitivno relacijo - recimo relacijo "<", kjer velja
nekaj izjem, ki so programu podane kot parameter, recimo: "5 < 3",
"6 < 2", ... Ce vzorcno mnozico stevil, recimo "5 2 4 1 3", uredimo
"po vrsti", torej: "1 2 3 4 5", zanjo velja, da vsebuje dolocene
konflikte glede na dano (non-tranzitivno) relacijo. Torej ce imamo v
tem primeru izjema "3 < 2", potem sta stevili 2 3 v konfliktu.

Za vsako tako zaporedje sedaj definirajmo ceno: skupna cena
(permutacije clenov zaporedja) je enaka vsoti posameznih cen, ki jih
prispevajo posamezni konflikti glede na relacijo - ta pa se izracuna
tako, da se kvadrira razdaljo (v zaporedju) med steviloma, ki sta v
konfliktu glede na relacijo. Torej v zgornjem primeru imamo izjemo "3
< 2"; razdalja med steviloma je 1, 1^2 pa je tudi 1. Torej je cena
celotnega zaporedja v zgorjnem primeru kar 1.

Sedaj pa je potrebno ugotoviti nek pameten algoritem, ki bo stevila
tako premetal sem ter tja, da bo cena permutacije clenov zaporedja
cimmanjsa.

Ima kdo v rokavu kaksen zanimiv algoritem? :)

Hvala!

(P.S.: Relacija je non-tranzitivna (netranzitivna) in ne
intranzitivna, saj ne velja za VSA stevila naslednje: ce aRb in ce
bRc, potem NOT(aRc), ampak samo za NEKATERA.)

-- 
Nejc Skoberne
Grajska 5
SI-5220 Tolmin
E-mail: nejc.skoberne at guest.arnes.si