Programozó versenyek

Levelező programozó verseny, 2019/2020. ősz

2019. október 1. 8:00 – 2020. május 31. 23:59

Toleranciarelációhoz legközelebbi ekvivalenciareláció

Adott egy T parciális toleranciareláció (reflexív és szimmetrikus). A feladat megkeresni az ehhez legközelebbi ekvivalenciarelációt. Miután ez NP-nehéz feladat, így csak közelítő eredmény várható.

A megírandó program maximum két parancssori argumentumot kaphat. Az első (amit mindenképpen megkap) egy fájl neve. Ebben a fájlban soronként egy-egy gráfot leíró fájl neve található. Minden gráfleíró fájl első sora a gráf csúcsainak számát (n) adja meg. Ezt n sor követi, melyek mindegyikében n karakter szerepel. A 0 karakter jelzi, hogy ez a pozíció nem érdekes, mivel a reláció itt nem értelmezett. Az 1 karakter jelzi, hogy a reláció ebben az esetben értelmezett és teljesül. Míg a 2 karakter azt jelzi, hogy a reláció értelmezett, de nem teljesül. Például álljon itt a bal oldalon egy lehetséges ilyen fájl tartalma:

6                     
122021          111122
211022          111122
211012          111122
000120          111122
221211          222211
122011          222211

Ebben a fordulóban Erdős–Rényi véletlen gráfokat használunk. A keresett ekvivalenciareláció is leírható lenne hasonló módon (fent jobb oldalt), viszont az minden elempárra értelmezett, így 0 karakter nem szerepelhet a leírásában. Érdemes az ekvivalenciarelációt egy függvényként elképzelni (f : V → N), mely minden csúcshoz egy egész számot rendel. Két csúcs ekvivalens, ha a hozzájuk rendelt két szám egyenlő, és nem ekvivalens, ha ez a két szám különböző.

A tolerancia- és az ekvivalenciareláció távolságát úgy értelmezzük, hogy azon i és j csúcspárok száma, ahol vagy a toleranciareláció teljesül, de az ekvivalenciareláció nem, vagy a toleranciareláció nem teljesül, míg az ekvivalenciareláció igen. Fent az eltéréseket piros színnel jeleztük, így a távolság 4. Mivel mind a tolerancia-, mind az ekvivalenciareláció szimmetrikus, így elegendő az előbb szereplő mátrixok felső (háromszögmátrix) felével dolgozni, mert az alsó háromszögmátrixban is ugyanezek a csúcspárok szerepelnek.

A programnak az egyes gráfok esetén számolt távolságok összegét kell a kimenetre írnia, azaz minden futás esetén csak egyetlen számot!

Annak érdekében, hogy ez a megoldás utólag ellenőrizhető legyen, ha egy második parancssori argumentum is megadásra kerül (a tartalma lényegtelen), akkor a távolságok összege helyett a kimenetre minden egyes gráfleíró fájl esetén meg kell adni a gráfhoz tartozó távolságot, majd az ekvivalenciához tartozó valamely f függvényt is, azaz előbbi példánk esetén az output lehet

4 1 1 1 1 2 2

vagy akár

4 3 3 3 3 1 1

is. Az a lényeg, hogy egy ekvivalenciaosztály tagjaihoz ugyanazon szám legyen megadva. Az egyes gráfokhoz tartozó kimeneteket külön sorba kell kiírni, az adatokat egy soron belül egy-egy szóközzel elválasztva.

Megjegyzés

Ebben a feladatban a feltöltött programokat csak kis gráfok esetén teszteljük (ahol n ≤ 10), hogy egy 3 másodpercig futó program is biztonsággal meg tudja találni az optimális megoldást. A levelező verseny feladatában azonban a tesztelést nagy gráfokkal fogjuk végezni, és a legoptimálisabb megoldást keressük. Az első parancssori argumentumban megadott állományban legfeljebb 20 állománynév fog szerepelni, amelyek hossza nem haladja meg az 50 karaktert.

Példa állomány (grafok.txt)

  1. graf-1.txt
letöltés szöveges állományként

Példa állomány (graf-1.txt)

  1. 6
  2. 122021
  3. 211022
  4. 211012
  5. 000120
  6. 221211
  7. 122011
letöltés szöveges állományként

Parancssori argumentumok

  1. grafok.txt
letöltés szöveges állományként

A futtatás eredménye a standard kimeneten

  1. 4
letöltés szöveges állományként

Parancssori argumentumok

  1. grafok.txt kecske
letöltés szöveges állományként

Egy lehetséges eredmény a standard kimeneten

  1. 4 3 3 3 3 1 1
letöltés szöveges állományként
Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.