[Algorytmy] Skarby, labirynty. Najdroższa ścieżka.

gryxon · Post autor: **gryxon** » 15 gru 2014, o 18:30

Witajcie,
W zadaniu mamy podany labirynt, oraz rozrzucone po nim skarby. Muszę znaleźć ścieżkę prowadzącą od wejścia do wyjścia, która pozwoli zebrać jak najwięcej skarbów.

Format zadania(a raczej wygląd grafu):

Kod: Zaznacz cały

###E#######
###   SSS #              
### #####W
###   SS  #
##########

E-Wejście
W-wyjście
S-skarby
#-ściana

Czy dobrze myślę, że to się sprowadza do znalezienia najdłuższej ścieżki między dwoma wierzchołkami? Czy może da się to rozwiązać w czasie wielomianowym?

93Michu93 · Post autor: **93Michu93** » 15 gru 2014, o 23:55

Najdłuższą ścieżkę pomiędzy E i W?

Kod: Zaznacz cały

#       E
#     # S
#     # S
#       W

jeżeli mamy taki przypadek, to w trzech ruchach możemy dojść do wyjścia, zbierając przy tym oba skarby lub możemy iść dłuższą drogą i nie zebrać żadnego skarbu. Może po prostu przejść ten labirynt rekurencyjnie, szukać wyjścia i jeżeli już się dojdzie do wyjścia, to zapisać ile skarbów się znalazło. Na końcu wybrać tą ścieżkę, gdzie skarbów było najwięcej. Pewnie prolog ładnie by sobie z tym poradził. Złożoność będzie jakaś masakryczna ale chyba żadna rozsądna wielomianowa nie jest możliwa.

gryxon · Post autor: **gryxon** » 16 gru 2014, o 00:00

Poprzez, sformułowanie sprowadzenie do problemu najdłuższej ścieżki w grafie, domyślnie dałem wagę skarbom jeden natomiast pozostałym wierzchołkom(krawędziom) zero.

Dzięki za opinie. ;p Jak ktoś będzie miał jeszcze inne zdanie to niech pisze. Najwyżej zaklepie wykładnika.

Post autor: **Afish** » 16 gru 2014, o 15:25

Nigdzie nie ma wymogu, że musi to być ścieżka prosta, więc po prostu idź kolei po wszystkie skarby omijając wyjście, a potem wyjdź z labiryntu.

gryxon · Post autor: **gryxon** » 16 gru 2014, o 16:58

Ścieżka oczywiście musi być prosta , nie można dwa razy stanąć na to samo pole

Post autor: **Afish** » 17 gru 2014, o 17:14

No to obawiam się, że jest to , czyli NP.
Możesz spróbować przybliżać wykorzystując coś takiego:
1. Znajdujesz najkrótszą ścieżkę między wejściem a wyjściem.
2. Znajdujesz wszystkie mosty. Jeżeli most jest na ścieżce z punktu 1, to efektywnie rozbija graf na dwa rozłączne podgrafy, więc masz do rozwiązania dwa mniejsze problemy. Jeżeli most nie jest na ścieżce z punktu 1, to nie ma sensu przez niego przechodzić, więc wywalasz część grafu.
3. Pałujesz BFSem każdy graf i sprawdzasz wszystkie ścieżki. Można też próbować algorytmu zachłannego, zależy od charakterystyki danych i rozmiaru problemu.
Skąd to zadanie?

gryxon · Post autor: **gryxon** » 18 gru 2014, o 00:36

Nie jest to żadne zadanie, raczej projekt z programowania na I semie. Początkowy projekt zakładał znalezienia jakiejkolwiek ścieżki z wejścia do wyjścia. Jako, że to raczej byłoby za proste jak na większy program to stwierdziłem, że sobie utrudnię temat. Prowadzący przedmiotu go zaakceptował . Tak myślałem, że to np. Trudno jeszcze pomyśle, może zaproponuje jakiś algorytm heurystyczny(albo zostawię wykładnika...) . Wielkie dzięki za pomoc.

btw. wykładnik jak nie ma dużych "komnat" to daje rade dla rozsądnych wymiarów plansz.