Robię ostatnio sobie kurs z podstaw AI na edx i mam trochę zagwozdkę z zadaniem projektowym. Może ktoś doświadczony z #java mógłby dać jakieś wskazówki. Zadanie polega na napisaniu agenta, który przy pomocy algorytmu BFS znajdzie rozwiązanie przedstawionego problemu. Problemem jest ułożenie po kolei cyfr w danej matrycy 3x3, przesuwając tylko jeden klocek z '0'. Napisałem to w pythonie, a potem się przerzuciłem na jave, jednak i tutaj i tutaj mam problemy z wydajnością, także pewnie jakieś złe podstawowe założenia mam. W javie wygląda to tak:
- obiekt Stan reprezentuje sobą stan planszy (tablica int [3][3]) oraz ma kilka pól takich jak ref na rodzica (czyli Stan z którego sie wywodzi), głębokość rozgałęzienia, String z kierunkiem ruchu który do tego stanu doprowadził (żeby odtworzyć potem ścieżkę) - każdy kolejny Stan gry jest dodawany do kolejki (LinkedList) - szukając stanów "dzieci" dla danego Stanu, kopiuję poprzez Arrays.deepCopy tablicę gry oraz dokonuje na nich zmian (np. jeśli możliwa jest zamiana 0 miejscem z cyfrą nad nim, tworzę nowy Stan - kolejność sprawdzania to up,down,left,right), na ich podstawie tworzę kolejne Stany, które dodaje do kolejki - dodatkowo mam 2 Hashsety, w których przechowuję Stany już odwiedzone (wrzucam tam tylko hashcode tablicy int[][]) oraz te w kolejce (coby szybciej sprawdzać obecność w queue niż iterować przez całe LinkedList). Chodzi o to, aby nie wrzucać do kolejki duplikatów lub Stanów już sprawdzonych.
Myślalem że dodając sprawdzanie po hashcode w setach znacznie przyspieszy proces w porównaniu do pythona, ale już na 16 poziomie rozgałęzienia komp mi się zdusił (wieeeele tysięcy Stanów). Macie może jakieś wskazówki z czego zrezygnować, jak to zoptymalizować? Albo odeślijcie mnie proszę do jakiejś książki :| #algorytmy #programowanie
@wafel93: A czy w Javie nie jest tak śmiesznie, że jeżeli dwie tablice są takie same to mają różne hashcode'y, bo array nie zmienia implementacji hashcode'u z Object, więc patrzy na referencje? Ergo, HashSet jest bezużyteczny tu? :)
W Pythonie też sobie możesz na setach i listach (albo lepiej: numpyArrays) zrobić ;)
@SwordPL: a wiesz, zabawne że wspomniałeś o tym. Spróbuję to we wrappera jakiegoś dać, z hashcode z Arrays.hashCode - wtedy wiem że są faktycznie na podstawie zawartości. Ale dobre pytanie co zrobi po prostu z array :D Zaraz sprawdzę
@SwordPL: Miałeś rację - generlanie array jest obiektem, takze domyślnie hashcode jest z dupy(tj referencja tez bierze udział). Trzeba użyć Arrays.deepHashCode lub Array.hashcode, iterując po każdej wewnętrznej :) P.S. Dla informacji, jakby ktoś miał podobną rozkminę - generalnie dobry pomysł mialem, bo z pythona gdzie przykład liczyło mi 20 minut, tutaj w 3,5 sekundy poszło :D No ale ja nie bardzo into pajton
oraz ma kilka pól takich jak ref na rodzica (czyli Stan z którego sie wywodzi), głębokość rozgałęzienia, String z kierunkiem ruchu który do tego stanu doprowadził (żeby odtworzyć potem ścieżkę)
nie musisz trzymać tych danych. Ref na rodzica jest zbędny - jak go używasz? BFS chodzi po grafie poziom po poziomie, więc głębokość możesz liczyć na bieżąco, przetwarzając kolejkę, jeśli użyjesz specjalnego "znacznika" nowego poziomu: zaczynasz
@superbybak zacznę od końca - pomysł ze stringami - myślałem o tym, tylko doszedłem do w wniosku, że zrobię z tej metody małego potworka pełnego if. Do dopracowania, pewnie mniej pamięci zje. Co do 2 hashset. Mam wrażenie, ze tworzenie nowych obiektów duplikatów i wrzucanie ich do kolejki moze być zasosobozerne. Nie eksperymentowalem z tym. Ale jak sie teraz zastanawiam, to chyba wystarczy jeden set, bo i tak służy do wydania decyzji
@wafel93: w przypadku gdy używasz stringów "duplikaty" nie zwiększają kosztu, bo dwa identyczne stringi będą współdzieliły pamięć (kwestia budowy JVM). Jeśli używasz zawiniętych we własny obiekt tablic int[][] to zgoda :)
Hm, a Twój agent nie ma dostępu do kolejki? Ścieżka sama w sobie nie byłaby zapisana w znaczniku. Ścieżkę budujesz wewnątrz głównej pętli programu. Domyślam się że masz jakąś taką pętlę typu:
while (!finished && !queue.isEmpty()) { // wrzucanie sąsiadów
Pamietajcie, jesli wybierzecie bande czworga, tzn ze zgadzacie sie na lockdowny i zamordyzm. Dacie znac ze w przyszlosci zmuszanie ludzi do siedzenia w domu przez 1-2 lata jest normą i nikt za to nie odpowie.
Zadanie polega na napisaniu agenta, który przy pomocy algorytmu BFS znajdzie rozwiązanie przedstawionego problemu. Problemem jest ułożenie po kolei cyfr w danej matrycy 3x3, przesuwając tylko jeden klocek z '0'. Napisałem to w pythonie, a potem się przerzuciłem na jave, jednak i tutaj i tutaj mam problemy z wydajnością, także pewnie jakieś złe podstawowe założenia mam. W javie wygląda to tak:
- obiekt Stan reprezentuje sobą stan planszy (tablica int [3][3]) oraz ma kilka pól takich jak ref na rodzica (czyli Stan z którego sie wywodzi), głębokość rozgałęzienia, String z kierunkiem ruchu który do tego stanu doprowadził (żeby odtworzyć potem ścieżkę)
- każdy kolejny Stan gry jest dodawany do kolejki (LinkedList)
- szukając stanów "dzieci" dla danego Stanu, kopiuję poprzez Arrays.deepCopy tablicę gry oraz dokonuje na nich zmian (np. jeśli możliwa jest zamiana 0 miejscem z cyfrą nad nim, tworzę nowy Stan - kolejność sprawdzania to up,down,left,right), na ich podstawie tworzę kolejne Stany, które dodaje do kolejki
- dodatkowo mam 2 Hashsety, w których przechowuję Stany już odwiedzone (wrzucam tam tylko hashcode tablicy int[][]) oraz te w kolejce (coby szybciej sprawdzać obecność w queue niż iterować przez całe LinkedList). Chodzi o to, aby nie wrzucać do kolejki duplikatów lub Stanów już sprawdzonych.
Myślalem że dodając sprawdzanie po hashcode w setach znacznie przyspieszy proces w porównaniu do pythona, ale już na 16 poziomie rozgałęzienia komp mi się zdusił (wieeeele tysięcy Stanów). Macie może jakieś wskazówki z czego zrezygnować, jak to zoptymalizować? Albo odeślijcie mnie proszę do jakiejś książki :| #algorytmy #programowanie
W Pythonie też sobie możesz na setach i listach (albo lepiej: numpyArrays) zrobić ;)
P.S. Dla informacji, jakby ktoś miał podobną rozkminę - generalnie dobry pomysł mialem, bo z pythona gdzie przykład liczyło mi 20 minut, tutaj w 3,5 sekundy poszło :D No ale ja nie bardzo into pajton
nie musisz trzymać tych danych.
Ref na rodzica jest zbędny - jak go używasz?
BFS chodzi po grafie poziom po poziomie, więc głębokość możesz liczyć na bieżąco, przetwarzając kolejkę, jeśli użyjesz specjalnego "znacznika" nowego poziomu: zaczynasz
Co do 2 hashset. Mam wrażenie, ze tworzenie nowych obiektów duplikatów i wrzucanie ich do kolejki moze być zasosobozerne. Nie eksperymentowalem z tym. Ale jak sie teraz zastanawiam, to chyba wystarczy jeden set, bo i tak służy do wydania decyzji
Hm, a Twój agent nie ma dostępu do kolejki? Ścieżka sama w sobie nie byłaby zapisana w znaczniku. Ścieżkę budujesz wewnątrz głównej pętli programu. Domyślam się że masz jakąś taką pętlę typu:
while (!finished && !queue.isEmpty()) {// wrzucanie sąsiadów