Droga w labiryncie

PO
  • Rejestracja:około 14 lat
  • Ostatnio:około 3 lata
  • Postów:211
0

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.

edytowany 1x, ostatnio: porschelukas
NO
  • Rejestracja:około 14 lat
  • Ostatnio:około 8 lat
0

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ś?

PO
  • Rejestracja:około 14 lat
  • Ostatnio:około 3 lata
  • Postów:211
0

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.

Hrypa
  • Rejestracja:około 18 lat
  • Ostatnio:około miesiąc
1

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.

NO
  • Rejestracja:około 14 lat
  • Ostatnio:około 8 lat
0

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;)

SI
  • Rejestracja:prawie 14 lat
  • Ostatnio:około 8 godzin
1

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ć.

Hrypa
Ale skąd wiadomo, które ściany wyburzać? Jeśli będziesz wybierać losowo, rozwiązanie najczęściej nie będzie optymalne.
SI
O ile dobrze rozumiem autora wątku, to interesuje go tylko i wyłącznie ilość ścian które trzeba będzie wyburzyć. A w takim przypadku optymalna droga nie ma znaczenia, i można wszystkie ściany w których po jednej stronie jest obszar suchy a po drugiej zalany uznać za pojedynczą ścianę, i zburzyć "naraz".
Hrypa
Rzeczywiście, racja!
PO
yhym, tylko nie bardzo rozumiem jakiej zasady trzymać się wyburzając ściany. Po prostu bruteforce wszystkie kombinacje? i za każdym razem stosować zalewanie? (coś w stylu pomysłu w moim pierwszym poście)
NO
  • Rejestracja:około 14 lat
  • Ostatnio:około 8 lat
1

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:)
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)