Hódító / Queosia forum

Hódító / Queosia forum (http://forum.hodito.hu/index.php)
-   PC (hardver, szoftver, játékok stb.) (http://forum.hodito.hu/forumdisplay.php?f=28)
-   -   Programozás (http://forum.hodito.hu/showthread.php?t=4435)

RicsiPi 06-06-2011 08:14

Quote:

Originally Posted by Redback (Post 288282)
Matektanárom valami méylségi keresést, meg valami backtrack valamit emlegetett. Annyira nem vagyok benne a dologban, igazából én is arra lennék kíváncsi, hogy mit is nevezünk Mesterséges Intelligenciának.

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

Valezius 06-06-2011 12:29

Quote:

Originally Posted by Dus (Post 288280)
Nem hiszem, hogy a jelenlévők közül bárki is tudna olyat írni, ami tényleg MI. Mármint, én nem nevezem mesterséges intelligenciának a tapasztalat alapján tanuló programot, például. Belátásos tanulást meg még nem igazán tud csinálni az emberiség. :)

Szóval mire gondolsz mesterséges intelligencia alatt?? :)

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.

Kutyuleee 06-06-2011 13:14

Quote:

Originally Posted by Redback (Post 288277)
Adott egy 100mx100m-es térkép. Minden egyes ponthoz meg van adva a magassága. Tekintsük úgy, hogy egy négyzet 1mx1m, és egy négyzet minden pontja ugyan olyan tengerszint feletti magasságon van. Írjunk programot, amely megmondja kialakítható-e rajta egy legalább 50M^2-es tó, bal felső és jobb alsó koordinátáját adja meg a tónak. HAsználnátok-e hozzá valamilyen féle mesterséges intelligenciás algoritmust? Ha igen, melyiket? Nekem megvan a program ,viszonylag gyors is, de mesterséges intelligenciát nem hiszem hogy tartalmaz.

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.

Kutyuleee 06-06-2011 13:31

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...:)

Dus 06-06-2011 13:46

Quote:

Originally Posted by Valezius (Post 288304)
Szerintem te félreértetted a dolgot.
Szerintem ez egy fogalom:
mesterséges intelligenciás algoritmust

?? Senki nem mondta, hogy ne lenne ilyen.

Quote:

Originally Posted by Valezius (Post 288304)
Ki kell nyitni a megfelelő tankönyvet és megnézni, hogy mit értenek pontosan ez alatt.

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

Quote:

Originally Posted by Valezius (Post 288304)
De a feladat kiírásában úgy látom szó sincs arról, hogy egyedül kell kitalálni valami forradalmi dolgot.

Ezt sem írta senki.

Redback 06-07-2011 07:13

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 :)

Redback 11-01-2011 20:15

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 :(

Redback 11-01-2011 20:39

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

Cpt Balu 11-11-2011 11:03

Quote:

Originally Posted by Redback (Post 293912)
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 :(

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

Cpt Balu 11-11-2011 12:04

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


All times are GMT +1. The time now is 06:57.

Powered by vBulletin®
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Design partly based on Hódító's design by Grafinet Team Kft.

Contents and games copyright (c) 1999-2020 - Queosia, Hódító

Partnerek: Játékok, civ.hu