[LUGOS-PROG] Sortiranje mnozice stevil glede na non-tranzitivno relacijo

[Andraz Tori]

jah tu ponavadi vzames kak algoritem za iskanje minimumov.. vsaj na prvi
pogled (in kakor poznam APS2 seminarske) je problem itak v NP ...

uporabi recimo simulirano ohlajanje.

s tem da za spremenljivko ki jo ohlajas izberes stevilo zamenjav med
starim in novim kandidatnim zaporedjem... pri celi zadevi pa je precej
pomembno, da zmanjsas cas evaluacije na minimum... to je lahko tezavno.

na splosno pa tem algoritmom zelo pomaga, ce že začneš s kakim kolikor
toliko dobrim izhodiščem... ki ga dobiš seveda s kakim drugim ad-hoc
algoritmom

potem pa lahko si pomagaš tudi tako da začetne in končne člene, ki so
morda brez izjem izpustiš iz računanja itd... skratka ... te naloge so
ponavadi prav zabavne, le čas in veselje moraš imeti, da 'tunnaš'
algoritme :)


lep pozdrav
andraz tori


Na 1079989582, 2004-03-22 ob 22:06, je Nejc Skoberne napisal(a):
> 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.)