Fórum: Valaki mondja meg!

Köszönöm a segítséget, de sajnos ezt még nem tudom használni. Az a baj, hogy egy hatos kombináció nagyon sok 12-esből előáll. Nekem az lenne jó, ha minden 6-os csak egyszer állna elő. Nem kell feltétlenül 12-es futamokat alkotni, lehet kevesebb versenyző is egy futamban. Az a cél, hogy lehetőleg kevés futam legyen. Írtam egy algoritmust, de sajnos nagyon lassú. További segítséget köszönettel veszek.

(45, 12, 6)-ra is lefutott a program, 134 perc alatt. A kapott megoldás 52127 mérkőzésből áll, ami megint 6-szor nagyobb az egyszerűen kapott minimumnál.

A megoldás az előzőhöz hasonló formában letölthető. (Persze ha használod, érdemes ellenőrizni is.)

A (43, 12, 6)-ra a kapott megoldásom tehát 38889 elemű, letölthető. Az n=43 versenyző az A,B,...,Z,a,b,...,p betűk jelölik. Minden sorban egy k=12 elemű mérkőzés van, ezek együtt lefednek minden m=6 elemű csoportot. (Az utolsó mérkőzésben van egy szóköz, ez azt jelenti, hogy az egyik pályán ezen a mérkőzésen senkinek nem kell indulnia.)

Előállítottam egy megoldást (n=43, k=12, m=6) esetre, ez gyors gépen 73 perc alatt lefutott, és 38889 menetből állt, ami csak hatszor rosszabb, mint az egyszerűen kapott minimum, a 6598. A program teljesen egyszerű, nem használ semmilyen trükkös heurisztikát vagy visszalépést. Egyszerűen véletlen sorrendbe rakom az n alatt m csoportot, amiknek együtt kell játszania, mindig veszem ebben a sorrendben az első néhány olyan csoportot, aminek a tagjai még nem játszottak együtt, és az ezekben szereplő emberek játszanak. Lefuttatom ugyanezt a kicsit nagyobb n=45 esetre, és meglátjuk, mit kapok. Sajnos a kapott beosztás egy hozzászólásban nem fog elférni, úgyhogy kívülre rakom föl valahova.

Azt hiszem, erről valaki olyan algebristát kell megkérdezni, aki emlékszik valamire a csoportelméletből, vagy a szimmetrikus struktúrák vagy blokkrendszerek vagy hasonló nevű tárgyakból. Én szimmetrikus struktúrákat nem hallgattam, csoportelméletről pedig csak papírom van, de nem értek hozzá, ezért nem hiszem, hogy tudnék válaszolni. Lehet, hogy más valaki a fórumon tud segíteni; ha nem, akkor gondolom keresned kell valakit a fórumon kívül, aki ért ilyesmikhez.

Ez így van. Nekem viszont m=6 bármely ponton át kéne lehetőleg egy egyens, amely legfeljebb k=12 pontot tartalmaz. Ez már nem affin sík lesz (mivel 6 ponton át általában nem húzható egyenes), de nem is annyira elméletileg, mint gyakorlatilag érdekelne a feladat. Legalább 8815 12-es beosztás kell, de egyáltalán nem biztos, hogy ennyiből megoldható. Ha ennek kb. kétszeresével megoldható, még az is jó.

Ha jól emlékszem, az eredeti salakmotoros konstrukció a 4-elemű test feletti affin síkra épült: n=16 pont, 20 egyenes, minden egyenesen k=4 pont, és bármely m=2 ponton át pontosan egy egyenes.

n=45, k=12, m=6. Egyelőre programot próbálok írni, ami legenerálja a megfelelő 12-eseket.

Ilyen általános problémánál a legjobb, ha mondsz pontos példákat, hogy milyen n, k, m stb paraméterek érdekelnek téged, és megpróbáljuk arra megoldani.

Az Új matematikai mozaik c. könyvben Montágh Balázs írt egy fejezetet Salakmotor-versenyek és véges síkok címmel.Itt azt vizsgálja, hogy n versenyzőt hogy lehet k versenyzőből álló futamokba beosztani úgy, hogy bármely két versenyző egy futamban összemérje magát. Engem egy kicsit általánosabban érdekelne a probléma, vagyis bármely m versenyző (m<=k)legalább egy futamban együtt induljon. Nem kell feltétlenül csak egy futamban elindulni adott m versenyzőnek, de persze ez lenne a legjobb. A futamok sem kell, hogy pontosan k versenyzőből álljanak, lehet kevesebb is (de legalább m). A cél, hogy a lehető legkevesebb futam legyen, és bármely m versenyző legalább egy futamon együtt induljon el. Ha ez elméletileg nehéz lenne, akkor egy közel optimális megoldás is megfelel, illetve egy algoritmus is, amely egy megfelelő beosztást generál.