Witam, na studia muszę napisać w javie(BlueJ) program który utworzy możliwie najlepszą ścieżkę w labiryncie. Program ma się opierać na wczytaniu tablicy dwuwymiarowej wypełnionej 0 i 1, 0 - możliwa droga, 1 - blokada, pliku tekstowym znajduje się także pierwsza ścieżka. Program po wczytaniu tablicy i ścieżki ma przejść do skrzyżowania i zmienić drogę, a następnie szukać drogi do wyjścia(dodam, że labirynt zawsze rozpoczyna się w lewym górnym rogu, a kończy w prawym dolnym). Po tej czynności ma sprawdzić czy ścieżka jest lepsza tj. krótsza od poprzedniej, jeśli tak to ją nadpisać i kolejną iterację wykonać dla nowej ścieżki, jeśli nie to sprawdzić inną możliwą drogę na danym skrzyżowaniu lub przejść do kolejnego skrzyżowania. Aktualnie mam napisaną funkcję odpowiedzialną za wyłapanie wszystkich skrzyżowań, tak aby nie uwzględniał skrzyżowania jeśli jest to poprzedni lub następny krok ścieżki, ale nie mam pomysłu jak napisać szukania drogi po ustawieniu go na skrzyżowaniu, tak aby po wybraniu ścieżki na której nie ma wyjścia wrócił do ostatniego rozgałęzienia(nie tylko skrzyżowania na głównej ścieżce) itd. Za wszelkie wskazówki będę bardzo wdzięczny.
Co to opisałeś to algorytm DFS -> Deep First Search
No niestety nie, ten nie ma działać na grafie, tylko na poprawianiu drogi przy każdej iteracji.
O RLY?
Program ma się opierać na wczytaniu tablicy dwuwymiarowej wypełnionej 0 i 1, 0 - możliwa droga, 1 - blokada
Lekcje na dzis:
https://pl.wikipedia.org/wiki/Macierz_sąsiedztwa
https://pl.wikipedia.org/wiki/Macierz_incydencji
I to co opisałeś to jest DFS, czy tego chcesz czy nie.
To nie DFS, tylko przeszukiwanie z nawrotami. Wykonuje DFS dla wielu możliwych dróg, aż znajdzie najlepszą. Poczytaj o przeszukiwanie z nawrotami/backtrackingu. Pisałem to dawno temu i pamiętam tylko, że to nie była żadna przyjemność.
To ma działać na labiryncie, który można interpretować jako graf, tak jak @Shalom napisał.
Kategoria powinna być Algorytmy i Struktury Danych, a nie Java.