Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Najkrótsza droga wyjścia z labiryntu.

Idź do strony 1, 2  Następny

 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
takeshi2318



Dołączył: 28 Gru 2011
Posty: 6

PostWysłany: Sro Gru 28, 2011 2:12 pm  OP    Temat postu: Najkrótsza droga wyjścia z labiryntu. Odpowiedz z cytatem Pisownia

Witam mam takie zadanie o następującej treści: treść posta przeniesiona do posta przez moderatora,
i chciałby się zapytać z czego najlepiej w nim skorzystać gdyż napisałem już 2 programy z własnym algorytmem ale żaden z nich nie chciał działać, z góry dzięki za pomoc.

Treść posta przeniesiona do posta przez moderatora. Po co rozbijasz treść posta na kilka serwisów!? marcin_an



Labirynt.pdf
 Opis:

Pobierz
 Nazwa pliku:  Labirynt.pdf
 Wielkość pliku:  114.61 KB
 Pobierano:  278 raz(y)

Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Sro Gru 28, 2011 2:39 pm      Temat postu: Odpowiedz z cytatem Pisownia

Witam,
niedawno był poruszany tutaj na forum problem perkolacji, w którym podjąłem próbę rozwiązania podobnego problemiku do Twojego (niestety nie w C++): http://www.coderscity.pl/ftopic41385.html?sid=02e1ee237572aaf65793cb36bb1a50dd Wydaje mi się, że metoda losowego błądzenia po kracie powinna rozwiązywać Twój problemik (po dołożeniu odpowiedniego warunku, zmodyfikowaniu kodu i przełożeniu go na C++), jednak może to być metoda czasochłonna... Możliwe, że istnieją bardziej optymalne metody wyszukiwania drogi w labiryncie... Chętnie bym się dowiedział, jak ten problemik można inaczej ugryźć... Pozdrawiam.

_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
takeshi2318



Dołączył: 28 Gru 2011
Posty: 6

PostWysłany: Sro Gru 28, 2011 3:03 pm  OP    Temat postu: Odpowiedz z cytatem Pisownia

Myślałem osobiści o algorytmach wyszukiwania ścieżki typu A-star albo Dijkstra, ale niestety są one trudne w implementacji...
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Sro Gru 28, 2011 3:25 pm      Temat postu: Odpowiedz z cytatem Pisownia

Zastanów się czy wspomniane przez Ciebie algorytmy nadają się do Twojego problemu, wydaje mi się, że są to typowe algorytmy przeznaczone do wyszukiwania minimalnych ścieżek na grafie, a Twój problemik jest chyba zupełnie innego typu, pzdr.
_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
izaw



Dołączył: 12 Wrz 2008
Posty: 2181
Skąd: Łódź

PostWysłany: Sro Gru 28, 2011 3:42 pm      Temat postu: Odpowiedz z cytatem Pisownia

Klasyczne przeszukiwanie wszerz. Na każdym poziomie masz wszystkie pola o danej odległości.
_________________
Program nie robi tego co chce programista, ale to co programista zaprogramował
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
Hashedone



Dołączył: 23 Sie 2008
Posty: 1179

PostWysłany: Sro Gru 28, 2011 4:43 pm      Temat postu: Odpowiedz z cytatem Pisownia

hurgadion napisał:
Zastanów się czy wspomniane przez Ciebie algorytmy nadają się do Twojego problemu, wydaje mi się, że są to typowe algorytmy przeznaczone do wyszukiwania minimalnych ścieżek na grafie, a Twój problemik jest chyba zupełnie innego typu, pzdr.

To jest dokładnie poszukiwanie najkrótszej ścieżki w grafie.

@takeshi2318 - które spośród A* i Djikstry są trudne w implementacji? Djikstra to przeszukiwanie wszerz, A* dodaje do tego tylko cheurystykę (która dla tego typu przypadków jest bardzo prosta).

_________________
"Jeśli profesor będzie wymagał, żeby podczas pisania kodu chodzić po ścianach, to student ma obowiązek chodzić po ścianach, bo inaczej nie zaliczy. Podane informacje dotyczą normalnych sytuacji. Profesorowi pisz jak profesor chce." ~ marcin_an, 2008
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Sro Gru 28, 2011 4:52 pm      Temat postu: Odpowiedz z cytatem Pisownia

Chyba rozumiem... W takim razie problem perkolacji także sprowadza się do klasycznego problemu :)
_________________
miasto nauki praktycznej


Ostatnio zmieniony przez hurgadion dnia Sro Gru 28, 2011 5:02 pm, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
takeshi2318



Dołączył: 28 Gru 2011
Posty: 6

PostWysłany: Sro Gru 28, 2011 4:58 pm  OP    Temat postu: Odpowiedz z cytatem Pisownia

A czy mógłby ktoś, napisać mi (możebyć w pseudo kodzie) jak mniej wiecej ma wyglądać ta cheurystyka? Bo w teorii działanie tych algorytmów rozumiem ale jak otworzyłem kod A* to zgłupiałem...
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
izaw



Dołączył: 12 Wrz 2008
Posty: 2181
Skąd: Łódź

PostWysłany: Sro Gru 28, 2011 5:23 pm      Temat postu: Odpowiedz z cytatem Pisownia

Zacznij od napisania klasycznego przeszukiwania wszerz. W twoim problemie pewnie to wystarczy.

Jeżeli będziesz potrzebował optymalizacji to dodasz A*. Zacznij od wikipedii.

_________________
Program nie robi tego co chce programista, ale to co programista zaprogramował
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
marcin_an



Dołączył: 26 Maj 2005
Posty: 18822

PostWysłany: Sro Gru 28, 2011 5:24 pm      Temat postu: Odpowiedz z cytatem Pisownia

Ciekawi mnie, czy można - skoro zakazano używać znaku [ - skorzystać z ciągu znaków <:

;P

Dla osób, które widziały wcześniejszą, już usuniętą wersję posta: oczywiście mój błąd - nie będzie prostszy w implementacji. Dlatego też usunąłem tę część wypowiedzi.

_________________
Nieaktywny od 2017-04-01
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Wszystkie czasy w strefie CET (Europa)
Idź do strony 1, 2  Następny
Strona 1 z 2

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.16772 sekund, zapytan = 13
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |