[UUUI] 1. laboratorijska vježba - 2020/2021

Jale

Vonj na teamsu u Course assistance kanalu je odgovorio asistent na to pitanje, kaže neće penalizirati različite putove

Dr_Flare

PSA za ljude koji se čude što im java program treba pol godine za obaviti 3×3, nemojte kao ja koristiti LinkedList za iteriranje kroz masu puno stvari jer je sporo. Ako mozete HashSet to je super, LinkedList je za queue isto super samo nemojte molim vas iterirati po 180 tisuca objekata tako…

To vrijedi i za ostale strukture podataka, ako ste sumnjičavi, samo promijenite u koju strukturu spremate nešto i promotrite utjecaj na brzinu, zna bit velika razlika

feel_d_boot

Da li nekom kod ai.txt podataka koristeći bfs algoritam vraća drukčiji poredak stanja, tj. drukčiji put?
# BFS
[FOUND_SOLUTION]: yes
[STATES_VISITED]: 3
[PATH_LENGTH]: 5
[TOTAL_COST]: 26.0
[PATH]: enroll_artificial_intelligence => complete_lab => fail_continuous => fail_exam => fail_course

S time da je u rješenjima točan put:
[PATH]: enroll_artificial_intelligence => fail_lab => fail_course

Također sam probao isključiti abecedno sortiranje u očajničkom pokušaju da samo dobijem točno rješenje, ali dalo je opet neko krivo rješenje za ai.txt, a za istru.txt se nije prestalo vrtiti. Stoga, to očito ne pomaže iako je moj minibrain mislija da može nekako.

Znam da je napisano da BFS algoritam treba prvo abecedno poredati open listu, tj. frontu pa onda nadodavati na nju nove čvorove. Ali ako abecedno poredamo, pošto su “complete_lab” i “fail_lab” sljedeća dva stanja, “fail_lab” će abecedno uvijek biti prvi. Je li netko imao ovakav problem ili sam ja krivo napisao algoritam?

Uz to, da li je bitno ako nam BFS i UCS algoritmi daju manji broj posjećenih stanja i za istra.txt i za ai.txt (naravno izuzev bfs slučaja za ai.txt), ali svi ostali elementi koje trebamo ispisati su identični kao u pdf-u za laboratorijsku vježbu?

Amariska

iNut ne trebas sortirat open listu prije dodavanja, nego sortirat listu novih cvorova, pa ih onda dodavat

KitKat

iNut Uz to, da li je bitno ako nam BFS i UCS algoritmi daju manji broj posjećenih stanja i za istra.txt i za ai.txt (naravno izuzev bfs slučaja za ai.txt), ali svi ostali elementi koje trebamo ispisati su identični kao u pdf-u za laboratorijsku vježbu?

ovo i mene zanima s obzirom na to da mi bfs ispisuje manje za broj posjećenih stanja, osim ako isključim abecedno sortiranje, onda mi ispisuje točno.

feel_d_boot

Amariska
Možda sam se krivo izrazija, to i napravim pa onda svaki od tih čvorova provjeravam da li su ciljano stanje. Ako nisu, provjerim da li su posjećeni već te ako nisu, tek onda ih stavljam na listu otvorenih čvorova.

dora

Koji algoritam koristit za pronalazak prave cijene puta kod provjere optimisticnosti?

Retard00

AE UCS

Rene

Koliko vam cca. traje izvođenje A* za 3×3?

Retard00

Rene Jel treba uopće rješit 3×3?

Rene

Retard00 da, samo ne treba provjera optimisticnosti u 2 minute zavrsit

Retard00

Rene Sad sam tek skužio da je 3×3 zapravo ista stvar ko prijašnji problemi pa lako testiram dal radi,
Izvođenje cijelog programa (znači A* + misplaced_heu) mi traje oko 4.4 s dok sama funkcija a_star traje oko 2.9 s. Najvjerojatnije bi moglo i mnogo brže od toga jer sam radio u Python-u.

SonGoku

Rene
Pa 3×3 je u dodatnim zadacima a i demosi su dns rekli da to ne moramo…odakle ti taj info ?

Rene

Retard00 lol onda ja nesto jako pogresno radim s a*, hvala

KingGeedorah

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…

gladiator

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

FERonja

Rene jaoo ja trajanje a* brojim u satima

Rene

~~~~~~~~ koliko ja vidim, u dodatnim zadacima je rješivost slagalice i dokaz vezano za to, optimizacija provjera optimističnosti i konzistentnosti i dizajn heuristika za 3×3. Sam obilazak stanja BFSom, UCSom i A* za 3×3 koliko shvaćam je sastavni dio labosa, a nalazi se i u primjerima za autograder

Gulbash

Kolko vremena treba za ovo?

KitKat

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

TheNubKiller

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.

Vonj

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.

angello2

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?

ppooww

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

angello2

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

« Prethodna stranica Sljedeća stranica »