Engem is érdekel az MI, de sajnos túl bonyolult matek-háttértudást igényel. De még nem adtam fel, hátha egyszer megvilágosodok -valami csoda folytán.

De attól függetlenül a 14. fejezet érdekes:
Ha „túl jó” a kereső algoritmus, és a célfüggvény nem pontos.
Pl. ápoló robot: ha célfüggvény a páciens szenvedésének a minimalizálása, akkor pl. a páciens megölése nullára csökkenti.
http://www.inf.u-szeged.hu/~jelasity...10/jegyzet.pdf

Szerintem te félreértetted a dolgot.
Szerintem ez egy fogalom:
mesterséges intelligenciás algoritmust

Ki kell nyitni a megfelelő tankönyvet és megnézni, hogy mit értenek pontosan ez alatt.
De a feladat kiírásában úgy látom szó sincs arról, hogy egyedül kell kitalálni valami forradalmi dolgot.

Nah így reggel józanabb fejjel megnézve, erre egyértelmüen egy backtrack-hez hasonló keresési algoritmust kell használni:) brute force-al ez picit több mint 6milla összehasonlítás, ha az összes lehetőséget megnézed, egy jól megírt backtrack-el nagyságrendekkel kisebb:) plusz még tovább tudod finomitani, ha a hibás eredményt kielemzi a program, és így kihagyhat pár lépést.

Lehet elkezdek holnap irogatni rá egy keresési algoritmust, nem árt majd a jövöheti vizsgámhoz:)

Ha esetleg nem ismered még a backtrack-et amúgy, a legjobb a 8királynő problémáján keresztül szemlélteni, hogy hogy is müködik.
->feltesszük az első királynőt az első sorba.
->feltesszük a következőt az első sorba. üti? tovább toljuk eggyel, megint üti?még1-el,ez így megy amig nem.
->feltesszük a harmadikat azzal is eljátszuk ezt. ha eljutunk addig hogy minden pontban ütés van, visszalépünk az elözö királynőhöz és tolunk rajta egyet, ha azzal is eljutunk a végéhez, még 1-et.

Az algoritmus futhat az első helyes eredményig, de megkeresheti az összes helyes eredményt. Bizonyitható, hogy minden helyes variáción végig fog menni (ezt most nem teszem meg). ahogy az is belátható,hogy ha az első királynő eléri a táblavégét és nincs helyes eredmény, akkor a feladatnak nincs megoldása. ugye az algoritmus lényege, hogy hibás eredménynél csak 1-et lép vissza és ott módosít.

Mondjuk végig gondolva talán gyorsíthatsz a keresésen, ha tudod, hogy nincs nagy szórás az értékekben, egy egymásba ágyazott kiválogatás+megszámlással, máris kitudod zárni,azt ha nincs megoldás, és azokat a kezdő értékeket is, amiknél automatikusan lépjen tovább a program:) ha pl csak 1-2 olyan érték van, amiből nincs legalább 2500, akkor 1 ilyen érték találatnál máris biztos,hogy ugorhatsz egy 50*50-es négyzetet...:)

?? Senki nem mondta, hogy ne lenne ilyen.

Akkor hajrá. Nekem nincsen ilyen tankönyvem, de örömmel venném, ha megosztanád velem, hogy mit is írnak benne.

Ezt sem írta senki.

Akkor azt hiszem, a backtracket már használtam, mert a királynőset hasonló módon írtam meg. megszámolom, hogy kb az én módszeremmel hány összehasonlítást kell végezni :)

adott egy m*n-es tomb. minden eleme csak 1 vagy 0 lehet. Az 1 jelenti a feketet, 0 a feheret. Hogyan lehet megkeresni leggyorsabban a legnagyobb csak feher (0) mezoket tartalmazó téglalapot? Én úgy gondolkoztam, hogy minden mezőhöz hozzárendeltem egy számot, mégpedig hogy a terület bal felső sarkával alkotott téglalapban hány fekete mező van. Ekkor bármely téglalapban lévő fekete mezők meghatározhatóak mindenféle ciklus nélkül. Ezután meghatározom a terület "területét" (m*n).Mindig csökkentem eggyel a terület értékét, és megkeresem mekkora téglalapoknak annyi a területe, aztán megnézem hogy az eredeti területben belefér-e magassága és szélessége, ha igen, akkor végignézem az összes olyan téglalapot az eredeti területben, és ha csak fehér mezők vannak benne, akkor győzelem. De ez túl lassú :( 500*500-ra 60 mp alatt kéne lefutni, de csak 3-4 perc alatt fut le :(

A lényeg lemaradt, szóval aki tud segíteni, akár csak sejtése van, szívesen fogadom :)

Szeretem az ilyen feladatokat :) Van egy jó ötletem, hogyan lehetne megközelíteni, csináltok egy próbált és elmondom milyen eredményre jutottam, egyébként egy 500x500-as tömb nem akkora adatméret, úgyhogy sztem bőven 1perc alá lehetne vinni.
Egyébkétn a te megközelítésed akkor jó, ha tudni lehet, hogy a keresett téglalap legalább a terület felét-háromnegyedét lefedi, de ha mondjuk egy 2x2 a legnagyobb, akkor szívás mire eljutsz odáig

Mekkora területeket kell keresni? kész van egy algoritmus, mindjárt közlöm az eredményeket...

Én kíváncsi lennék erre az algoritmusra, ha szabad. Érdekelne, mert agyaltam rajta, de nem sok sikerrel. :)

A legnagyobb területet keressük :) Kíváncsi lennénk az algoritmusra :)

Úgy értem h a várható legnagyobb terület mekkora? majdnem az egészet befedi, vagy ritább területen keresünk? mert van jó algoritmus arra, ha mondjuk 50x50 körüli eredményeket várunk vagy kisebbet (akkor az átlag futási idő olyan 500ms körüli), de nagy eredményeknél nem valami gyors, egy másik pedig pont a nagy eredményeket találja meg hamar, de ha ritkább a kitöltöttség az sok fölösleges kört futtat vele :)
Viszont most eszembe jutott még valami, máris kipróbálom...
Egyébként egy 15x15-ös területet most átlag 90msec alatt találok meg :) Sztem ez jó eredmény lesz

bármekkora lehet a legnagyobb, akár 1 területű, akár 25000 területű :)

Addig leírom a jelenlegi algoritmus lényegét:
Elindulok a tábla elején, szépen sorfolytonosan haladok. Ha találok egy aktív területet (1) akkor van legalább egy 1x1-es megoldás.

Ezután megnézem, hogy adott irányban (mondjuk X mentén, tehát vízszintesen) meddig találok aktív területet, legyen ez X, utána másik irányban Y. Így tehát van lehetőségem egy maximum X*Y eredményre. Ezt összehasonlítom a korábbi eltárolt legjobb eredménnyel (ha van). Ha az eredményem nagyobb, fölösleges tovább vizsgálni, nem lesz belőle új eredmény. Ezután esetleg végzek még gyorsteszteket (átellenes sarok, oldalak ellenőrzése), amik érvényteleníthetik a jelenlegi keresést, és a legvégén csinálok teljes vizsgálatot (vagyis hogy teljes-e a téglalapom), mivel ez az legidőigényesebb munka. Ha stimmel, és a téglalap nagyobb mint az eddigiek, akkor végeredményként eltárolom, és legközelebb már csak az ennél nagyobb esélyesek vizsgálata történik meg, ami jelentősen csökkenti a futási időt.
Sok helyen lehet ignore feltételeket alkalmazni, pl. ha van egy 10x10-e eredményem, akkor a 491. sor 491. oszlopnál legjobb esetben egy másik 10x10-est találhatok, az ez utáni oszlopokban meg sokkal kisebbeket, ilyenkor ki lehet hagyni a keresést, és következő sorral folytatni (ahol már az utolsó 11 oszlop elhagyható, mivel az is csak 11x9=99 lehetne)

Egyenes rekurzió helyett ajánlott while ciklusokat használni stack műveletek spórolása miatt, sokszor nagyságrendekkel gyorsabb lehet a progi.

Ez a módszer hasonló a tiédhez, vagyis végignézem a táblát, kiszedek belőle max méretű téglalapokat, és feljegyzem a legjobbat, a többi nagy részét pedig keresés előtt is el tudom vetni. De akad más megközelítés is, a reklám után folytatom... :)

A megírt programodra kíváncsi vagyok, tesztelnék egy párat :)

Nos, a legtisztább az lenne, ha generálnál néhány alakzatot, megmondanád mennyi idő alatt keresel, és ugyanazt megpróbálom én is megtalálni keveseb idő alatt.

Elkészült a program, még próbálom értelmezni, mit is találtam ki :D És érthetően beszámolni róla, röviden annyit a teljesítményről, hogy vegyes sűrűségű próbákkal nem tudtam 400ms fölé(!) menni :) Remélem ez már megteszi, ha érdekel a progi, esetleg elkészíthetem egy kis alkalmazással, mondjuk bittérkép rajzolóval, elkészíted az ábrát, és ráereszted a keresőt... :)

Milyen nyelven írtad? Ha C,C++,Java vagy Pascal akkor e-mail-ben küldd már el a forráskódot, mert van itt jóhényán forrásom, aztán megnézem, és azt is, hogy helyes-e :)

C#... :D
De sok programnyelvre át tudom írni, java, c++, delphi, pascal, asm, php amit akarsz.

Közben megálmodtam mégegy algoritmust, ami nem brute-force, csak sajna elég nehéz optimalizálni. Sajna képek nélkül elég nehéz lenne elmagyarázni, majd kitalálok valamit, addig is elküldtem a progit, az egyszerűség kedvéért 500x500-as képre korlátoztam, de bármekkora területen működik (1000x1000-nél sem nagyon ment 4-5sec fölé)
Itt egy táblázat 500x500-ra, hogy adott telítettség mellett milyen futási idők jöttek ki. Az oszlopok:
1. Telítettség: az a valószínűség, amivel a terület fel lett töltve, tehát nem a pontos területarány, ettől lehet kis eltérés
2. Minimális futási idő
4. Átlagos futási idő
3. Maximális futási idő
(adott valószínűséggel legenerált 100 egyedi térképen való futtatás alapján)

A 3 érték mindegyike millisec, jól látható, hogy kis telítettségnél (1-esek aránya <95%) a sok 0 elszórva a térképen megakadályozza, hogy nagy eredmény jöhessen létre, a kicsi lehetőségek vizsgálata hamar megtörténik [a futási idő O(n^3) közelítésű], valamint nagyon nagy telítettségnél (csak néhány 0 található) a kevés variáció vizsgálata tart rövid ideig (pontosabban, mivel nagyon nagy eredmények hamar születhetnek, sok vizsgálatot el tudunk dobni):

10,000% 17 21 31
20,000% 21 28 50
30,000% 24 30 35
40,000% 32 38 60
50,000% 35 37 41
60,000% 37 41 49
70,000% 42 47 63
80,000% 50 56 74
90,000% 73 79 93
91,000% 80 85 98
92,000% 78 87 109
93,000% 89 99 117
94,000% 106 110 130
95,000% 115 126 145
96,000% 138 146 164
97,000% 170 178 196
98,000% 242 255 274
99,000% 369 391 433
99,100% 388 411 434
99,200% 416 436 520
99,300% 457 518 648
99,400% 481 548 617
99,500% 503 582 798
99,600% 501 567 615
99,700% 518 589 649
99,800% 441 490 662
99,900% 314 395 456
99,910% 298 334 429
99,920% 276 307 336
99,930% 256 296 406
99,940% 231 269 327
99,950% 198 211 225
99,960% 162 204 271
99,970% 133 151 194
99,980% 115 126 160
99,990% 85 104 130
99,991% 78 91 111
99,992% 70 92 124
99,993% 61 69 93
99,994% 54 70 113
99,995% 53 66 90
99,996% 41 54 84
99,997% 40 47 71
99,998% 24 29 36
99,999% 18 26 43

A keresés bizonyíthatóan a legjobb eredményt hozza ki.

készítettem egy oldalt ahol leírtam az új algoritmus elvi fejtegetését (sajna itt nem működtek a képek, azok nélkül esélytelen megérteni):
users.atw.hu/cptbalu
ide fogom írni a jelenlegi progi működését is.

(ps: ha moderátoroknak kifogásuk van linkelés miatt, várnék javaslatot hogy tudnám megoldani a képes postokat, img tagek behozták a képeket oszt el is tüntették rögtön, gondolom tiltva van külső hivatkozás bbc-ben)

egy forráskódot nekem is küldenél??? elsőre én is hasonló algoritmusban gondolkodtam csak nem volt időm még foglalkozni vele.:)

Még annyi a kérdés, hogy az eredeti feladatban használható-e rekurzió vagy nem?

Gondolom igen, csak erősen nem ajánlott :) Területvizsgálatnál egy rekurzió hamar elszabadulhat (pl. felezéses közelítéseknél ha nincs limit, akkor 2^n felé tart a lehetséges újrahívások száma, ami elég bizonytalan futási időt eredményez)

ezzel tisztában vagyok, de annyira nem vészes, ebben az esetben. csak mert szerintem megirnám rekurziv backtrack-kel is. ugyis kell gyakorolnom majd vizsgára, meg azért is, mert van olyan tételem, hogy rekurzív fügvényt kell átirni simára, és vissza.

Az átírás gyakorlatilag annyi, hogy while ciklus helyett függvényt hívsz :)
rekurziót akkor érdemes használni, ha egyébként túl sok köztes eredményt és állapotot kellene tárolni, ezt a függvény hívása megoldja nekünk, de pont ez a gyengéje is, a hívás és visszatérés sokszor lényegesen több mint maga a programkód futási ideje, ekkor kell választani, egy kis plusz programozásért cserébe gyorsíthatunk a kódon.
Elkezdem szép lassan írni az oldalra a jelenlegi progi algoritmusát is, remélem érdekesnek találjátok majd a gondolatmenetet :)

Elvileg nincs, és img tagek jól működnek. Legalábbis eddig jól működtek. Nem lehet, hogy inkább a külső linkelés van letiltva annál az oldalaknál, ahonnan behúztad a képet? Mert olyat szoktak. Bár képmegosztó oldalaknál nem, de pl. az ingyenes tárhelyszolgáltatók ezt csinálják, hogy ne használd a tárhelyüket "háttértárolónak" egy másik oldalhoz.

Erre nem is gondoltam, köszi... :)
A fura h előnézetnél egy pillanatra megjelentek a képek, aztán eltűntek belőle, ezért gondoltam h fórum motor csinálja.
Időközben befejeztem az algoritmus leírásának első lépését, a "profilozást" (talán valakinek ismerős lesz a módszer), feltettem az oldalamra, nemsokára megírom az utolsó lépést, ami saját szerzemény, és kicsit bonyolult, de megpróbálom érthetően :)

Update: mialatt írtam a cikket, észrevettem egy dolgot, amit beletettem a progiba :)
Az új eredmény (csak a kritikus rész):

99,200% 393 415 463
99,300% 402 423 444
99,400% 430 450 474
99,500% 444 462 471
99,600% 440 459 471
99,700% 432 442 456
99,800% 399 420 438

Egyértelmű a javulás, lám egyetlen integerrel mi mindent lehet tenni... :) (A becslés szerint a javulás mértéke a tábla méretével arányos)

Mivel a megoldás maga egyszerűbb, mint a magyarázkodás :P ezért itt postolom az algoritmust C# kódját:
Eddig a bevezetés, hogy hogy is néz ki a tábla, tehát int tömb, 1 és 0, ebben fogunk keresgélni.
A következő függvény adja a megoldást, az eredmények
X,Y,W,H változókba kerülnek (híváskor W értéke -1, a többi lényegtelen), amit a hívás helyén tudunk felhasználni:
Nem túl hosszú kód, de annál bonyolultabb értelmezni, kíváncsi vagyok ki jön rá mit is csinál pontosan :) Lehet ötletelgetni!
Segítség: az első for ciklus (for (int i = Width - 1; i > -1; i--)) törzsének végéig az oldalon leírtak szerint működik.

Más szerverről kell beilleszteni a képet. Valami olyanról, ami képként kezeli, és nem html oldalként, ami fölé muszáj fejlécet is tenni. Ott a Gugli fotóalbuma például, az korlátlan, ingyenes, gyors.

Thx, akkor megpróbálkozok vele...

Nyilvános a Doom3 engine.

Lecsaptam rá, köszi :)
már találtam is benne hasznos dolgokat, maya import stb. jobb ha nem magamnak feljesztem csak az időt viszi :)

2009/2010-es OKTV-ről két feladatra lennék kíváncsi :

1. Írj programot (jarda.pas, …), amely kiszámítja, hogy hány féleképpen lehet kikövezni egy 2*N egység méretű járdát 1*1 és 1*2 méretű lapokkal!

2.Egy vállalkozó alkatrészek gyártásával foglalkozik. Minden alkatrészen kétféle műveletet kell elvégeznie, A és B műveletet. Mindkét művelet elvégzésére egy-egy munkagépe van, amelyek egymástól függetlenül tudnak dolgozni. Minden alkatrészen először az A műveletet
kell elvégezni, majd ezután lehet elvégezni a B műveletet (bármikor, nem feltétlenül folyamatosan). Minden legyártandó alkatrészre ismert, hogy mennyi időt igényel az A,valamint a B művelet elvégzése.

Készíts programot (utemez.pas, …), amely kiszámítja, hogy legkevesebb mennyi idő alatt lehet legyártani az összes alkatrészt!

A utemez.be szöveges állomány első sorában az alkatrészek N (2≤N≤2000) száma van. Az alkatrészeket az 1,…N számokkal azonosítjuk. A második és a harmadik sor pontosan N egész számot tartalmaz egy-egy szóközzel elválasztva, a legyártandó alkatrészeken elvégzendő A, illetve B műveletek idejét. A második sor ban az i-edik szám az i-edik alkatrészen végzendő A művelet ideje. A harmadik sorban az i-edik szám pedig az i-edik alkatrészen végzendő B művelet ideje. A második és harmadik sorban lévő számok mindegyike 1 és 50 közötti érték.

Példa:
utemez.be
3
8 1 6
1 6 3

utemez.ki
16
2 3 1
2 3 1

Igazából magára az algoritmusra lennék kíváncsi, nem feltétlen forráskódra :)

Nekem az jött ki, hogy ezt rekurzióval kell megcsinálni.

Ezután egy 2*N-es járdát úgy számolnék ki, hogy a vágósíkokat végigfuttatnám rajta.
Először felteszem, hogy 1+N-1 -re van szétvágva, aztán 2+N-2-re és így tovább.

A gond, hogy ezeket nem lehet összeadni, mert van közte átfedés.
De mindenképp úgy számolnék, hogy letenném a vágósíkokat minden lehetséges módon, aztán csak össze kell adogatni az eredményt.

Az egyes szétvágott daraboknak olyannak kell lennie, hogy belül már ne legyen vágósík. Ez akkor van, ha egy darab 1 széles (2elrendezés) vagy 2 széles (3 elrendezés) vagy 2x széles ekkor megint 2 elrendezés van.

Vagyis az N-et fel kell osztani minden lehetséges módon 1,2,4,6,8... összegére. A sorrend is számít.
De ezt leprogramozni nem tűnik vészesnek.

Például a 2x2-esnél ha nincs felosztva az 3 elrendezés, ha fel van, akkor még 2*2 és kijön a 7.

2x3-asnál 1+1+1 , 1+2, 2+1 a lehetséges sorrendek, szépek ki lehet számolni, hogy ez 2*2*2+2*3+3*2=20 lefedést jelent.

igen, így belegondolva tényleg igazad lehet :)

Így belegondolva tippem sincs, hogy mit jelent, amit írtál. :)

Akkor most bajban lennék, ha te tetted volna föl az eredeti kérdést :)

A 2x2-esnél milyen 3 elrendezésre gondolsz?

Ha nincs benne függőleges vágósík, akkor lehet vízszintesen 2db kettes tégla.
Aztán vagy az alsó vagy a felső becserélhető egyesekre.
(Mindkettő nem, mert akkor mégis van benne vágósík.)

Egyébként mégse kell semmiféle rekurzió. Csak elkezdtem írni, aztán láttam, hogy nem teljesen jó, úgyhogy újra kellett gondolnom.