Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

algoritam razmišljanja

[es] :: Art of Programming :: algoritam razmišljanja

[ Pregleda: 4380 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

vedric

Član broj: 6777
Poruke: 3
*.net.hinet.hr



Profil

icon algoritam razmišljanja24.12.2002. u 17:09 - pre 258 meseci
Zanima me kako bi se riješio ovaj problemčić..
Imam jednu površinu npr 100 cm x 100 cm i sad bih ja u tu površinu želio upisat kvadrate i pravokutnike različitih dimenzija,od 3 objekta na više,do nekih n objekata.
Algoritam bi trebao biti takav da on te sve kvadrate i pravokutnike tj objekte različitih dimenzija poslaže u tu površinu 100 cm x 100 cm tako da na toj glavnoj površini ostane što manje neiskorištenog prostora.
Treba naći kombinaciju kako bih rekao tog mozaika s najmanje neiskorištenog prostora...

 
Odgovor na temu

drbogi

Član broj: 5045
Poruke: 601
212.62.58.*

ICQ: 454238854


+3 Profil

icon Re: algoritam razmišljanja24.12.2002. u 20:31 - pre 258 meseci
Jel' bi ti da seces ivericu, ili si se bacio u razmisljanje?

 
Odgovor na temu

Puzo
Milos Puzovic
London

Član broj: 6451
Poruke: 24
*.router.demon.net

Sajt: myweb.tiscali.co.uk/puzov..


Profil

icon Re: algoritam razmišljanja24.12.2002. u 20:40 - pre 258 meseci
Postoji jedan veoma slican problem tvom u matematici koji se zove tiling problem. U problemu postoji kvadrat odredjenih dimenzije koji treba poplocati sa fixed tile (tj. poplocati sa samo jednim objektom koji je fiksnih dimenzija). Ukoliko u poslednjih godinu dana nije doslo do nekog novog otkrica, ovaj problem je i dalje neresiv, a resavali su ga mnogi poznati matematicari (npr. Erdos :)))

Nisam siguran (ako gresim, neka me neko ispravi :)), ali mislim da je problem koji si ti naveo je NP-complete problem (tj. trenutno se ne zna da li postoji algoritam u polinomijalnom vremenu koji bi resio navedeni problem). Najbolje resenje ces dobiti samo u slucaju da proveris sve mogucnosti (kojih ima puuuuuuno :))

Trenutno najefikasniji algoritam koji se koristi kako bi resio probleme slicne tiling problemu je first-fit algorithm. Na internetu postoje neke reference oko algoritma.
 
Odgovor na temu

[es] :: Art of Programming :: algoritam razmišljanja

[ Pregleda: 4380 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.