Droga w labiryncie

Cześć,
Czy ktoś mógłby mi wskazać jak rozwiązać problem przejścia labiryntu? Z tym że problem ten jest trochę utrudniony, ponieważ nie zawsze da się przejść od startu do celu bez konieczności wyburzania ścian. Algorytm ma wskazać nie tyle samą drogę co minimalną ilość ścian jakie należy wyburzyć. Na zajęciach nie mieliśmy jeszcze grafów tak więc tutaj nie musimy korzystać z rozwiązań tego typu. Raczej trzeba zastosować Backtracking/Bruteforce.
Wpadłem na dwa pomysły jednak żaden nie wydaje mi się optymalny:

• Usuwanie kolejno wszystkich kombinacji ścian i puszczanie za każdym razem algorytmu rozwiązującego klasyczny problem labiryntu. Czyli najpierw usuwam jakąś jedną ścianę, puszczam algorytm. Później poprzednią ścianę przywracam i usuwam następną. Jeśli znajdę rozwiązanie to zatrzymuje algorytm. Jeśli nie znajdę to usuwam ściany parami, jeśli to nie przyniesie efektu to po 3 ściany itd....
• Modyfikacja klasycznego algorytmu przechodzenia labiryntu, aby zamiast cofać się gdy napotka ścianę usuwał ją ale naliczał kosz takiej operacji. Natomiast zastanawiam się czy to w ogóle kiedykolwiek by się wykonało i nie zapętliło.

Szukam bardziej rozwiązania teoretycznego, z kodem sobie poradzę jeśli będę teoretycznie wiedzieć jak rozwiązać problem. Może mój problem ma dokładnie jakąś nazwę, o której nie wiem, też byłbym wdzięczny za jej wskazanie.

Wersja druga wydaje się być OK.

Z tego co pamiętam dla problemu labiryntu w każdym polu labiryntu zapisujemy jego minimalną odległość od startu, co znaczy, że jeżeli dochodzisz do jakiegoś pola, w którym już byłeś, to sprawdzasz czy doszedłeś do niego krótszą drogą czy poprzednio (i wtedy idziesz dalej), czy dłuższą lub równą (i wtedy się wycofujesz). Więc się nie zapętli, tylko znajdzie minimalne odległości dla każdego pola.

Pewien problem widzę tu z określeniem jaką wagę nadać wyburzeniu, aby ostateczny wynik zawierał jak najmniej wyburzeń (może to być np. waga większa niż liczba wszystkich pól w labiryncie). Jak to rozwiązałeś?

Yhym, dzięki za podpowiedź, z tym że tutaj tak naprawdę nie jest ważna odległość. Tzn jeśli mam przejść 1000 kratek bez żadnego wyburzenia to to jest lepsze niż na skróty gdzie trzeba coś wyburzyć. Czyli można przyjąć że wagi są zerowe gdzie nie ma ścian.

Musisz z tego labiryntu zbudować graf, w którym wierzchołek symbolizuje zbiór pól, w obrębie których można poruszać się bez wyburzania żadnych ścian. Krawędzie tego grafu (wszystkie o wadze 1), symbolizują zbiory pól, między którymi można się przedostać po wyburzeniu jednej ściany (sąsiadujących komór). Potem w prosty sposób (BFS-em) szukasz najkrótszej ścieżki z komory wejściowej do wyjścia.

Ja bym jednak nie stosował odległości zero, bo te odległości są później wykorzystywane do odtworzenia drogi przez labirynt od wyjścia do wejście (jestem w polu 213, musiałem na nie przyjść z pola 212, które z sąsiednich pól jest 212?) a ścieżka jest potrzebna, żeby wiedzieć przez ile ścian przeszedłeś... Akurat w Twoim przypadku brzmiałoby to dalej tak (... ach nie ma pola 212, więc mogłem się tu dostać przez ścianę ze 113, gdzie jest 113?).

Korzystając z wag możesz po prostu operować na dwuwymiarowej tabeli BFS-em (nie musisz tworzyć osobnego grafu). No chyba, że wygodniej Ci będzie przekształcić labirynt (zakładam, że zapisany w tabeli) na graf, to wtedy tak jak napisał @Hrypa. Myślę, że jego rozwiązanie jest bardziej pracochłonniejsze (poza tym i tak musisz chodzić po labiryncie, żeby zbudować wierzchołki grafu), ale może się okazać pomocne dla niektórych labiryntów.

Jeżeli zdecydujesz się jednak na tabelę, to sugerowałbym BFS z dwoma kolejkami - jedną dla chodnika (z niej wybierasz jeśli można), a drugą dla ścian (jeśli nie ma chodników do wybrania), możesz w ten sposób zaoszczędzić dużo przebijania się przez ściany;)

Skoro ma zwyczajnie podać ile ścian trzeba wyburzyć (zakładam że wszystkie są identyczne), to można by "zalać" labirynt (czyli oznaczać w jakiś sposób pola na których już byłeś oraz sąsiednie na które da się z nich przejść), jak nie dojdzie do wyjścia to wtedy zwiększyć liczbę wyburzanych ścian o jeden i zalewać znowu od suchych pól sąsiadujących z "zalanymi". najkrótszej drogi w ten sposób nie wyznaczy, ale nie o to w tym zadaniu chodzi. Dodatkowo można by zastosować 2 rodzaje "zalań" od początku i końca labiryntu, wtedy kończymy pracę jak zaczną ze sobą sąsiadować.

Przy zastosowaniu odpowiednich wag droga najkrótsza, nie będzie najkrótsza w sensie dystansu do przebycia, tylko w sensie kosztu jej przebycia, czyli ilości wyburzonych ścian. A mając już taką drogę wystarczy policzy ściany na niej (i można to zrobić w tym samym etapie co odtwarzanie tej najkrótszej drogi)...

Algorytm zalewania podany przez @sig istotnie wydaje się być najprostszy. Na pewno w opisie, ale w działaniu jest bliższy przechodzeniu labiryntu, bo:

• sam proces zalewania jest w istocie klasycznym przechodzeniem po labiryncie, tyle, że wpisujemy p=1 zamiast p2=p1+1
• znajdowanie ścian do przebicia oznacza albo przejrzenie całej planszy w poszukiwaniu takich ścian albo znalezieniu ścian ograniczających zalanie (co chyba w praktyce równa się przechodzeniu przez ściany z wagami)
• gdy dojdziemy do wyjścia, to znamy już liczbę ścian - tu faktycznie algorytm hydrauliczny mógłby być lepszy od klasycznego labiryntu, bo nie musimy odtwarzać najkrótszej ścieżki, ale jeżeli waga ściany będzie większa niż całkowite pole planszy, to dochodząc do wyjścia możemy odczytać liczbę ścian poprzez koszt_drogi div waga_sciany...
  Czyli w praktyce wychodzi na to samo, tylko implementacja jest nieco prostsza. Chyba, że coś przeoczyłem;)
  Co nie zmienia tego, że algorytm hydrauliczny jest ciekawym i orzeźwiającym głosem w dyskusji:)