Egy mátrixos probléma - megoldva

Algoritmusok

Hello!

A következő feladathoz kérnék segítséget:

5x5-ös mátrix/tömb, benne számok 1<=x<=9, x egész
tudjuk soronként, oszloponként, átlónként a számok összegét, ennek függvényében kell a 25 számot meghatározni(legalább 1 megoldást)

A feladat időkorlátja sajnos 3 másodperc, ezért az egyenletrendszeres összes lehetőség előállítását nem tartom reálisnak(12 egyenlet, 25 ismeretlen; 9^(25-12) = 2541865828329 lehetőség). De talán mégis lehetne szűkíteni valahogy rajta.
Van valakinek ötlete? Részmegoldások is érdekelnek, valamilyen szintig már sikerült eljutnom.

csko

  • 2129 megtekintés

( viktor1983 | 2006. 10. 20., p – 00:21 )

ha SZTE-TTK algoritmusok kotprogi, akkor vsz hatizsak pakolas... akinek eddig talalkoztam a feladataval, mindenkinek az volt 8)

Hm, kezdek álmos lenni.. amit a kollégák mondanak, finite-domain constraint programming, (fogalmam se volt eddig, hogy ezt így hívják) na azt kellene használni.

A lényege erre vonatkoztatva:
Egy cellára meg tudod mondani, hogy legalább és legfeljebb mekkora szám lehet ott. Soronként, oszloponként és átlónként is szűkíted a cellák lehetséges értéktartományait, majd a cellák közül kiválasztasz egy olyat, aminek a lehetséges felvehető értékeinek száma minimális az összes közül, (ha a minimális 1 darabot jelent, akkor az összes ilyet kiválasztod) éa beírod az értéket (ha mondjuk 4 és 6 között vehet fel értéket, akkor mondjuk 5-öt, de ezt most nem látom át, hogy nem mindegy-e). Majd újraszámolod az értéktartományokat, és így tovább. Ha valahol pedig ellentmondás keletkezne, akkor vissza kell lépni.

( csko | 2006. 10. 20., p – 02:48 )

Nem tanulmányokhoz kötött feladat, hanem saját célkitűzés. Nincs megadva, hogy milyen nyelven csinálom meg.

( strangelove | 2006. 10. 20., p – 14:11 )

Üdv!

Nos, ez egy egészértékű (lineáris) programozási feladat.
javasolandó átírni 0 és 8 zárt intervallumbeli egészekre átírni a feladatot,
majd megoldani, mint egyenlőséges, nemnegatív LP megengedettségi feladatot.
mint egészértékű prog. feladat, szerintem lődd be BnB illetve CP algoritmusokra,
hogy ilyen méretre még jól működnek-e.

Illetve ha célfüggvényes LP-ként oldod meg, akkor célszerű minimalizálni a legnagyobb összegű sor és a legnagyobb összegű oszlop keresztezésében álló elemet, így kapsz rá egy alsó korlátot is rögtön.

ha ad hoc heurisztikát alkalmazol, akkor javasolt első lépésben az átlókra vonatkozó korlátozó feltételektől eltekinteni, hiszen arra van jó javítóheurisztika, ha a sor- és az oszlopösszegek stimmelnek egy megoldásnál, de az átlók még eltérnek.

Teljes esetleszámlálásnál is egy kerekített folytonos LP relaxáció megoldásából indulj ki, majd 25 egymásba ágyazott for ciklus során permutáld intelligensen a változókon végigfutó egész értékeket.

Hello!

Kösz az ötleteket. Sajnos nem sikerült mindent felfognom, gondolom hiányosak az ismereteim ezen a téren. Az átlós dologra én is rájöttem, fel is írtam a lehetséges "mozgatásokat".

Jelenleg egy backtrack-szerű módszeren elmélkedek, valószínűleg nem lesz elég, és vegyíteni kell más technikákkal is.

csko

Képlet folytonos esetre, elindulásképp:

a_{i,j} = (("i. sor összege" + "j. oszlop összege")/5) - ("minden elem összege"/25)

kerekíteni kell intelligensen a teljes esetleszámlálás esetén is, és ez egy jó kezdeti megoldás szolgáltat.

pl. a_{i,j} == 3,141592653589793238 esetén az alábbi sorrendben próbálkoznék:

(3;4;2;5;1;6;7;8;9)

de 3,6666 esetén már

(4;3;5;2;6;1;7;8;9)

értékekkel

Valami hasonlóig jutottam el én is. A kezdeti felállás után a legkisebb különbségű szakasszal(sorral, oszloppal vagy átlóval) vagy a legnagyobbal kellene elindulni? Én a legkisebbre gondoltam.

Pl. sor1 összege 22, sor2 összege 20: sor1 "közelebb van" (5+45)/2=25-höz, ezért ott kezdeném a változtatásokat, persze a sor azon oszlopával, ahol a különbség az oszlopokra(esetleg átlókra) vonatkoztatva szintén minimális.

( csko | 2006. 10. 24., k – 22:04 )

Örömmel jelentem, hogy sikerült megoldani a feladatot :)

Végül a megoldás a következőképpen nézett ki:

41 tömbbel indulok, mindegyik tartalmazza az 5..45 összeg összes lehetséges előállítást.
Tudom az 5 sor összegét, mindegyikbe berakom egyik véletlenszerű (5-jegyű) számot, ezzel teljesítem a sorok összegére vonatkozó feltételeket. Ezután megnézem, hogy mely oszlopösszegek nincsenek rendben, majd ezeket vízszintes cserékkel feloldom, már csak az átlók vannak hátra. Azokra is van módszer, lehet cserélgetni, átmozgatni.
A programom több helyen is "elakadhat", ekkor újrakezdi egészen a véletlen soroktól, de még így is sokszor 1mp alatt megvan a megoldás.

Köszönöm a segítséget.