Studoši

Jel tko riješio sporost astara sa 3×3? Lol, ne znam što mi je krivo. Radim sve po prezentaciji i za ostale primjere radi savršeno. Radim u javi, koristim liste za open i closed. Ovo nikako da se završi, kao da je u beskonačnoj petlji.

Lumpy
Vjerojatno je problem u open, potreban je prioritetni red, ali pri provjeri jel neko stanje vec u redu open i usporedbi cija heuristika je manja, to je skupa operacija. Uz ubacivanje u red, dodaj da se ubacuju i vrijednosti u novu hash mapu.
Sad, prilikom svakog ubacivanja u open, taj isti Cvor ubacujes i u tu hash mapu, pa prilikom provjere nalazi li se neki cvor u redu open, provjeravas tu hash mapu, ako se vrijednost nalazi u hash mapi i veca je od trenutne vrijednosti, ides u izmjenu reda open.

ja ne razumijem kak oni dobiju ove pathove koje su dali u primjerima. na koju foru bfs koji sortira po abecedi moze prvo otic u fail_lab umjesto u complete_lab?

ista stvar za istru, kak je moguce da bfs ide jednakim putem kao ucs i astar kad to ocito ne bi smjelo bit tako? na koji nacin vi racunate/ispisujete path?

angello2 path treba ispisati najkraci pronadeni put. ako sam dobro skuzio ti ispisujes sva stanja koja je posjetio.

pp zar se ne pronalazi najkraci put pomocu astar? al kakvog smisla ima da za pravilan ispis bfs-a moram radit i astar? ne kuzim uopce poantu ispisivanja patha kad ne ispisujemo ono sta bfs radi nego neki skroz nepovezani najkraci put, nije li poanta demonstrirat da je bfsov put do konacnog stanja puno dulji nego put od boljih algoritama? sori ak su glupa pitanja al fakat mi nije jasno sta zele

angello2 Pa iz broja posjecenih stanja se vidi da BFS luta okolo, a A* ide usmjereno. Konačni put koji ispisuješ je pronašao i BFS, samo mu je trebalo duže

angello2 BFS isto uvijek pronade najkraci put. To je i logicno s obzirom da BFS posjecuje sva stanja razinu po razinu tj. u biti ispita sve moguce opcije. Prednost A* je da u prosjeku posjeti puno manje stanja nego BFS jer radi drukcije. To se ne vidi na ovim primjerima u labosu jer su grafovi dosta mali.

Gulbash kao i sa svakim labosom koji je na autograder, puno i previše jer više od pola vremena provedeš da shvatiš kako te autograder neće posrati

Retard00 Jesi koristio tuple za strukturu cvora ili? Ja sam tako ali mi je na autograderu iscurilo vrijeme za A* i provjeru optimisticnosti na 3×3.
Uz to mi je pao UCS nad 3×3 jer se razlikuje path. Zanimljivo je da je i moj i njihov algoritam nasao path jednake duljine i s istim brojem posjecenih stanja (znaci svih 5 znamenki poklapa) al moj je iz nekog razloga drugaciji…

King Geedorah Ne znam dal uopće imam ikakve čvorove tj. stablo. Napiso sam kod po njihovom algoritmu, skup open sam stavio da je prioritetni red (heapq), a skupovi closed i visited su obični setovi. Originalno (za BFS) sam imao klasu State koja sadži naziv i listu susjeda stanja, ali za sortiranje u heapq-u sam moro napravit StateWrapper koji u sebi sadrži cijenu i potrebne operatore za to. Za dobivanje putanje i uspoređivanje cijena sam jednostavno dodao atribute g_cost, f_cost i h_cost i previous State objektima. tuple-ove sam koristio kao elemente u listama susjeda stanja (parovi (ime, cijena)) i pri hash-iranju liste susjeda State-a (list -> tuple).

Vonj Jesi isprobao to? Radi li u razumnom vremenu?

Vonj
Kako iz prioritetnog reda open obrisat element koji ima veci f od trenutnog kojeg dodajemo?

Lumpy
Da, skratilo je izvodenje na 2-3 sekunde.

Treba li se nalaziti jos nesto u target\classes\ui jer mi autograder ne radi.
Solution.java mi je u src\main\java\ui

Retard00 jedno pitanje: KAKO? Meni traje beskonačno više

gladiator Skužio sam da i meni traje “beskrajno” ako maknem “if expanded_state in visited: continue” nakon ekspandiranja čvorova, pa sam ja jednostavno to tak ostavio (uz open i closed imam i set visited).
Sad dal je to dobro, ne znam. Ali prolazi njihove testove + neke moje. Moguće je da postoje krajnji(?) slučajevi gdje bi to moglo dovest do krivog rješenja al ih nisam uspio nać.

Retard00 Ok, našo sam i način da se A* za 3×3+misplaced izvede brzo (u istom vremenu ko i prije) i bez sumnjive visited liste. Uglavnom visited sam skroz uklonio, a izvođenje sam ubrzao tako da sam setove open i closed pretvorio u rječnike (npr.open=dict(), open[some_state] = some_state - time se provjeravanje i dohvačanje podataka brzo izvodi), i naravno uz to za open imam i priorityqueue, mada je mijenjanje podataka u njemu linearno. Sad je jedini problem što to kod mene za 3×3 i misplaced posječuje nešto više stanja (100870 > 95544, zašto? - nemam pojma) al to su tak i tak rekli u obavijesti da se to neće penalizirat.

Kako zapamtiti path?

mamaRu path je valjda u argv i dalje, nije nigdje pobjegao

gladiator sori, krivo sam se izrazila, mislim na ovaj path i path length koji opisuju najkraći put.

mamaRu meni moj search vrati konacni cvor, a svaki cvor ima roditelja, tak da ja za path odem od tog konacnog cvora natrag do prvog roditelja, obrnem listu, ispisem i u meduvremenu negdje prebrojim koliko ih ima

Jel ima netko pro tip kako da spustimo vrijeme za 3×3_puzzle(BFS) ispod 2 min

Peter Jordanson Za open koristi PriorityQueue (trebat ces komparator napisati), za closed korsti HashMap/HashSet, ako ni to nije dovoljno napravi za open Dodatni HashMap u kojem ces sa O(1) ispitivat jel cvor u redu, ako ni to nije dovoljno

Run with Java Flight Recorder analizira ti koliko posto vremena se koji dio koda izvodi pa vidi sta se jos da popraviti

EDIT: ups nisam vidio da pitas za BFS ali za sve koji pisu u javi i pate se sa vremenom 🙂