Fórum: Találjunk jobb megoldást!

Kiszámoltattam számítógéppel nyers erővel. Nem nehéz, kevesebb mint 5000 mozgatás alatt megkapjuk a legrövidebb megoldást. Hogy hány lépésből áll, azt csak a kék alapon kék képre írtam rá, hogy más is próbálkozhasson. Azt nem tudom, mit mondhatunk nagyobb pályára.

Van egy 5x5-ös négyzetrács alakú jégpálya, amit egy magasított perem vesz körül. A pálya 3 sarokmezőjében 1-1 doboz van, amik pont elfoglalják a teljes sarokmezőket. Egy lépésben egy dobozt valamelyik főirányban megtolhatunk, és az addig csúszik, amíg a peremnek, vagy egy másik doboznak nem ütődik (ha két doboz szomszédos, akkor csak a közös sorukra/oszlopukra merőlegesen mozgathatók). Ezek lényegében a Sokoban szabályai, kivéve, hogy kívülről is lehet tolni, és hogy a dobozok csúsznak.

A feladat az, hogy minél kevesebb lépéssel juttassunk be egy dobozt a pálya közepére. Pótkérdés: mit mondhatunk (2n+1)×(2n+1)-es pálya esetén?

Azt bevállalom, hogy 2x4n-eshez kell legalább n ;-)

Arra is kíváncsi lennék, hogy lehetne belátni vagy cáfolni, hogy korlátlanul nagy sakktáblánál a megoldás egyértelmű meghatározásához korlátlanul sok fal kell.

Kösz, megszenvedtem vele :)

Ugye ez a megoldás is arra épül, hogy a szélén lehet egyértelműen elkezdeni építeni, de semmi se garantálja, hogy egymástól távol eső falakkal ne lehessen kifeszíteni az ábrát. szóval szerintem szgép nélkül reménytelen. (Papíron könnyű belátni, hogy 1 fal nem elég, illetve szerintem a 2-őt is ki lehet izzadni, bár ehhez még nem volt kedvem, de a 3 már elég reménytelennek tűnik.)

Eleve a 4 falas megoldások száma a szimmetriai megfontolások alapján felére csökkenthető. Másrészt ezek nagy része megoldható a triviális lefedéssel. (Azaz először 2*4-es téglalapokra vágjuk az ábrát, majd ezeket lefedjük külön-külön.) mivel 8ilyen téglalap van, ezért ha egy ilyen lefedés van, akkor van több is. Végül azt is ki lehet használni, hogy ha találunk egy megoldást, amiben van egy 2*4-es 2 elemmel lefedett terület fal nélkül, akkor már léphetünk is tovább.

Határozottan ügyes, grat :-)

Egyébként nekem valóban úgy tűnik, hogy ez az öt fal már egyértelműen meghatározza a kitöltést.

Öt falra szerintem reménytelennek tűnik az összes eset végigpróbálgatása, és még négy falra is valami jó haténkony heurisztikus parkettázó kéne, ami előállítja az összes megfelelő lefedést, ezt pedig nem könnyű megcsinálni, ezért nem írta még meg senki a programot.

Csináltam egyet 5 fallal.

Egyébként azt csodálom, hogy még senki nem írta meg a programot, ami kidobja a jó választ. Kár, hogy én nem értek hozzá. :)

Szép megoldás.

Na jó, nem csigázlak tovább titeket:

Lehet, de én ahogy mondtam, 6-ot tudok :-) És nem nagyon látom, hogy hogyan is lehetne javítani...

költői megérzés :) 4? (értelemszerűen nincsen rá példám)

Kizárólag kézzel, és azóta sikerült 6-tal is. Holnap meg is mutatom.

Legfeljebb hét fallal? Érdekes. Megkérdezhetem, hogy kézzel találtad, vagy részben számítógéppel?

A tetrisben csak 4 elemből álló alakzatok vannak, tehát 3x2-es téglalapból vágjuk ki az L betűt (amúgy is 5 elemből álló alakzatokkal nem lehet lefedni a 64 elemből álló sakktáblát).

Jónás: A 8 falas megoldás szép (nekem is megvolt), de akkor most már elárulom, hogy sikerült 7-ből is.

Szerintem nyolc fal elég. Azt nem tudom, hogy hét elég-e.

Az elvi megoldást valószínűleg nem befolyásolja, de a gyakorlatit igen: Már nem emlékszem, a Tetrisben csak egyfajta L alakú elem volt? És milyen? 2*3-as vagy 2*4-es téglalap része?

Kitaláltam egy optimalizációs feladatot. Lehet, hogy nem én vagyok az első, de még nem hallottam róla korábban. Szóval a feladat a következő (van rá egy megoldásom, nem tudom egyelőre, mennyire jó):

Vegyünk egy 8x8-as sakktáblát. Ez, mint tudjuk, nagyon sokféleképpen lefedhető a Tetris-ből ismert L alakú idomokkal. Próbáljuk minél kisebb "ráhatással" kikényszeríteni, hogy a lefedés egyértelmű legyen. Konkrétan a ráhatáson azt értem, hogy két élszomszédos mező közé falat emelek, és értelemszerűen a falra nem lehet L-alakot tenni.

A kérdés tehát az, hogy legkevesebb hány fal-elemre van szükség a lefedés egyértelművé tételéhez (a lefedéshez az L alakok mindkét tükörképe használható).

Üdv!

Lehet, hogy találtam egy jobb megoldást az Erich Friedman-féle Squares in Squares 51 négyzetes megoldására, de le kellene valakinek ellenőriznie a helyességet, mert nagyon kicsi a javítás mértéke. Régi s=7,707+, új s=7,703+. Tudna valaki segíteni nekem ebben?

S ha jól sejtem, amennyiben helyes, ez az első közlés.

Kicsit gyakorlatiasabb lenne egy olyan modell, ahol figyelembe vennénk az utak karbantartásának a költségét, ami nyilván az összúthosszal arányos, és az autók fogyasztását. A cél az összköltségek minimalizálása. A fogyasztáshoz tudni kell bármely két város közötti forgalmat. Így az összúthossz és bármely két város közti úthosszak valamilyen súlyozott összegét kellene minimalizálni. Ez már kézzel igen nehézkes, de erre is lehetne program.

Köszi szépen a hozzászólásokat. Úgy látom, megint egy olyan témán kezdtem el agyalni, amit már 20 éve eléggé kiveséztek :-)

Nekem is a szappanhártyák jutottak eszembe Jonas ábrája láttán :-)

Elérhető Graham nagyon érdekes előadása a Steiner-fákról (a 40:00 perc után valamivel van szó speciális, 2×n-es rácsokról), sőt a YouTube-on is lehet nézni erről animációkat: ez például a 4x4-es rács, de Steiner-tree-re keresve lesz még jó pár. Itt pedig az olvasható, hogy a jónás által megrajzolt fa "known to be optimal". Ez a cikk egyébként az *év cikke* kitüntetést kapta 1988-ban.

Sziasztok!

Rákerestem egy kicsit a témára, valóban Steiner-fáról van szó. Úgy látom, nem szükséges rácspontokat felvenni, van egy külön euklideszi változata a problémának. Ha beírjátok a Google-ba, hogy "Euclidean Steiner Tree", elég sok jó találat kijön, többek között cikkek, konkrét módszerek is.

Ezen a címen elvileg szoftver is van, ami kirajzolja: http://www.cs.sunysb.edu/ algorith/implement/geosteiner/implement.shtml (csak linux alatt megy, így itthon nem tudom kipróbálni).

Aki szeret kísérletezni, annak egy "természetes" megvalósítást ajánlok, amit sok éve hallottam egy előadáson: két párhuzamos plexilemez között rögzítsünk (merőlegesen) rudakat, ezek jelképezik a pontokat. Mártsuk az egész szerkezetet szappanos oldatba, majd ha kivesszük, a szappanhártya pont a kívánt alakot veszi fel. Tényleg működik, fényképek az előadásról itt. :-)