Autor Wątek: Zbieranie przedmiotów na kwadratowej mapie  (Przeczytany 1649 razy)

Offline AS

  • Użytkownik
    • Homepage

# Sierpień 21, 2010, 15:37:23
Mamy mapę o kwadratowych polach. Np.
.X...
....X
X....
.....
X...X
Po kropkach i iksach można chodzić. Poruszać się można tylko w 4 kierunkach, NWSE. Nie można na skos. Iksów trzeba zebrać jak najwięcej. Zaczynamy w dowolnym miejscu na mapie. Nasza liczba kroków jest ograniczona, do np. liczby pól na przekątnej mapy. Na przykładzie - 5 to maksymalna liczba kroków jakie możemy zrobić. Mapa może być dużo większa niż 5x5 oczywiście.
Czy ktoś może podpowiedzieć jak najszybszy algorytm, który wyznaczy taką drogę, żeby zebrać jak najwięcej iksów?
« Ostatnia zmiana: Sierpień 21, 2010, 15:40:37 wysłana przez AS »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Avaj

  • Użytkownik

# Sierpień 21, 2010, 16:00:20
tak na moje oko patrząc od algorytmicznej strony:
- zrób graf, gdzie X-y to są wierzchołki a krawędzie to ilość kroków w jakiej dochodzisz od jednego wierzchołka do drugiego
- zapuść DFSa z maksymalną głębokością 5 (tzn, suma krawędzi, które już przeszliśmy nie może być większa niż 5), zapamiętując jakoś najdłuższą do tej pory ścieżkę (po której wyhaczyliśmy jak najwięcej X-ów)
- jak się DFS skończy to masz rozwiązanie od razu

Offline lethern

  • Użytkownik

# Sierpień 21, 2010, 18:38:25
problem komiwojażera, o ile się nie mylę, pogoogluj. (jeśli wiesz o nim i nie o niego chodzi to sorki ;)

Offline AS

  • Użytkownik
    • Homepage

# Sierpień 21, 2010, 19:29:27
@Java
Rozrysowałem sobie tak jak mówisz. Też myslalem o grafie to chyba dobry pomysł. Ale idąc dalej - DFS nie "bada" wszystkich krawedzi (a wlasnie dlugosc drogi w niej zapisanej ma byc minimalna), tylko wierzcholki. Nie rozumiem co da tez zapamietanie najdluzszej sciezki... I co robic gdy glebokosc rozpatrywanej sciezki jest > 5? Return i nastepny niezbadany wierzcholek? Na kartce mi to nie działa, wez pod uwage, ze tak jak radzisz (ale moge tez Cie nie rozumiec do konca), to opisywany graf jest grafem pełnym... I taki DFS powinien chyba zachłannie wybierać najkrótszą sciężkę, a nie po prostu tylko, aby do następnego, do następnego itd... Graf się konczy, DFS przeszedl po jakiejs tam trasie, z ktorej moge wybrac czesc gdzie przechodzi po maxie wierzcholkow, ale to chyba nie bedzie globalnie najlepszy wynik, jaki mozna uzyskac...

@lethern
Kto o nim nie słyszał ;) Tu nie chodzi o cykl, tylko zwykla sciezke. Priorytem tez nie jest najkrotsza (choc to niejako "pomaga") sciezka, tylko sciezka przechodzaca przez jak najwiecej wierzcholkow.
« Ostatnia zmiana: Sierpień 21, 2010, 19:36:07 wysłana przez AS »

Offline lethern

  • Użytkownik

# Sierpień 21, 2010, 19:44:42
Graf ma wierzchołki (iksy), a na krawędziach odległości (w metryce taksówkarskiej, jak zauważyłeś). wrzuć jakieś przeszukiwanie grafu (chodzi głównie o zaznaczanie, który wierzchołek odwiedzony; czy w głąb czy wszerz wydaje mi się nie robić różnicy), które będzie przechodzić sobie ten graf i zliczać długość, jaką przeszło, i oczywiście urywać, gdy ilość kroków się wyczerpie (czytaj: jeśli wzięcie następnego wierzchołka da drogę 6, a dopuszcalna to 5, to pomija te rozgałęzienie). W każdym momencie aktualizuj sobie jakiś obiekt "najlepsze rozwiązanie", w którym masz listę wierzchołków. Jeśli obecne ustawienie ma więcej wierzchołków (więcej kwadratów), to zapisz. Wydaje się, że skoro długośc drogi jest stała, i jeśli nie robię gdzieś błędu , to to znajduje rozwiązanie.
« Ostatnia zmiana: Sierpień 21, 2010, 19:46:28 wysłana przez lethern »

Offline AS

  • Użytkownik
    • Homepage

# Sierpień 22, 2010, 10:08:51
No algorytm *chyba* działa, dzięki. :P

BTW. Jak w linuxie sprawdzić z konsoli ile program (odpalony w drugiej konsoli o nazwie np. a.out) obecnie zużywa pamięci?
Kombinuję coś z ps czy gdb, ale jak dodaję sobie do kodu np. globalna tablice int[1000] to powinno mi zwiekszyc zuzycie o 4*1000B około 4 KB, a nic takiego niestety nie widac...
« Ostatnia zmiana: Sierpień 22, 2010, 15:50:53 wysłana przez AS »

Offline maciek_slon

  • Użytkownik

# Sierpień 22, 2010, 14:13:14
polecenie top pokazuje wszystkie działające procesy, wraz ze zużyciem procesora i pamięci.