Program wyszukujący drogę w labiryncie.

0

Mój brat ma do napisania program:

  1. Wczytujący labirynt z pliku tekstowego;
  2. Znajdujący drogę metodą "ort!" i "wszerz";
  3. Porównujący obie drogi;
  4. Zapisujący wynik w drugim pliku tekstowym.

O ile pkt 1. jest OK i znalezienie samej drogi też jest OK, o tyle problemem jest znalezienie NAJKRÓTSZEJ drogi.

Może ktoś pomóc? Ktoś może takie coś robił?

Za wszelkie rady/wskazówki będziemy zobowiązani.

0

Jeśli labirynt wczytujecie z pliku to jest tam jakaś jednostka odległości.
Na jej bazie możenie po porównaniu podać sporo parametrów:

  • najkrótsza droga przez labirynt - w jednostach i ew. mapka, kolejność kroków, azymutowo czy jak tam pasuje najlepiej (np. dwa kroki w przód, obrót w prawo, krok w przód, obrót ...) - najoczywistszy i najmniej interesujący element przy porównywaniu dróg
  • najszybciej znaleziona droga w czasie - ile algorytmowi zajęło odnalezienie drogi - na czas składają się 2 elementy - czas decyzji (czyli an każdym skrzyżowaniu wybór drogi, oraz czas przejścia - czyli długość PRZEBYTEJ NIE NAJKRÓTSZEJ drogi razy jednostka czasu przypadająca na przebycie pojedyńczej jednoski drogi)
  • droga przebyta pomiędzy wejściem a wyjściem podczas szukania
    Mozna jeszcze kilka innych parametrów wymysleć, potem zrobić zestawienie dla labiryntów takiego a takiego typu najlepszy jest algorytm taki bo to i tamto, ale pod względem takim jest lepszy taki, a dla innego typu labiryntu .... (najczęściej jest potrzebny najszybszy algorytm... ale nie zawsze)
    No i jak zrobicie ładne porównanie algorytmów to od razu wyjdzie do jakich zastosowań który lepszy, a nauczyciel z zachwytu zrobi pod siebie
0

Polecam lekturę o 2 algorytmach: algorytm mrówkowy i algorym komiwojagera - na sieci jest sporo informacji na ten temat.. no a gdybyś nie znalazł to zapraszam na stronę politechniki wrocławskiej -> wydział zastosowań informatyki -> katedra sztucznej inteligencji...

0

Być może nie potrafię czytać ze zrozumieniem, ale autor chyba napisał że nie ma problemów ze znalezieniem drogi tyle że nie wie jaka jest najkrótsza - ale jesli już znalazł to chyba jest banalne wybrać krótszą ... Najprościej jest policzyć ile "kroków" należy zrobić od wejścia do wyjścia - ale zanim ktoś mi zarzuci że skoro kroki będą po tej samej drodze to się zdublują to zaproponuję aby zdublowane wycinać prostym algorymem: Niech są 4 kierunki N,E,W,S oraz każdy krok to krok oznaczany jako jeden z tych 4. Teraz mając końcowy wzór przejścia (zapis krok po kroku) wycinamy pary N-S - oraz E-W (czyli kombinacje prawo lewo i przód-tył). Teraz tzreba przepuścić całość trasy w pętli przez wycinaczkę tak długo aż przestanie wycinać (długość ścieżki po kolejnym przejściu pętli będzie taka sama) i mamy najkrótszą droge wg. konkretnego algorytmu.

0
Andrzej Dąbrowski napisał(a)

Być może nie potrafię czytać ze zrozumieniem, ale autor chyba napisał że nie ma problemów ze znalezieniem drogi tyle że nie wie jaka jest najkrótsza - ale jesli już znalazł to chyba jest banalne wybrać krótszą ... Najprościej jest policzyć ile "kroków" należy zrobić od wejścia do wyjścia - ale zanim ktoś mi zarzuci że skoro kroki będą po tej samej drodze to się zdublują to zaproponuję aby zdublowane wycinać prostym algorymem: Niech są 4 kierunki N,E,W,S oraz każdy krok to krok oznaczany jako jeden z tych 4. Teraz mając końcowy wzór przejścia (zapis krok po kroku) wycinamy pary N-S - oraz E-W (czyli kombinacje prawo lewo i przód-tył). Teraz tzreba przepuścić całość trasy w pętli przez wycinaczkę tak długo aż przestanie wycinać (długość ścieżki po kolejnym przejściu pętli będzie taka sama) i mamy najkrótszą droge wg. konkretnego algorytmu.

ale to są algorytmy wyszukujące najkrótszą drogę a nie ma być algorytm wyszukującą najkrótszą z milionami dróg zwróconych przez inny algorytm, do drugiego punktu można prawie zawsze dojść na setki sposobów

0

Chyba trzebaby autora zapytać cop miał na myśli, choć jeśli podaje 2 algorytmy to zakładam że nie może implementować innych - bo inaczej zapytałby jakei znacie dobre algorytmy do mojego zadania. Co do milionów alternatyw - owszem ale gdy ktoś mówi labirynt to sądzę że liczba dróg jest mocno ograniczona, a w optymalnym przypadku do 1 .... Ale nie będę kopii kruszył, zawsze można mu zaproponować aby odwzorował labirynt na grafie, a może nawet jakiejś sieci i zaimplementował 5 najpopularniejszych algorytmów .... tylko czy na pewno o to mu chodziło ....

1 użytkowników online, w tym zalogowanych: 0, gości: 1