Adam Owczarek Łódź, dn. 13 kwietnia 2011
318194
Grupa 3
Zaawansowane algorytmy
Projekt 2
Grafy
Ogólnie o problemie
Zadanie:
Pomóż Jasiowi uciec z labiryntu.
Jasio zagubił się w labiryncie. Niestety (dla Jasia) w tym samym labiryncie grasuje wilk,
dla którego Jasio stanowi smakowity kąsek. Jasio może na dwa sposoby uchronić się przed
wilkiem:
1)Uciec do wyjścia
2)Wysadzić dynamitem skrzyżowanie, które rozdziela labirynt na dwie rozłączne części
Aby któryś z tych planów się powiódł musi zachodzić jeden z warunków:
1)Jasio jest bliżej(w sensie ilości korytarzy) wyjścia niż wilk
2)Jasio jest bliżej(w sensie ilości korytarzy) skrzyżowania rozdzielającego labirynt niż wilk
Wejście:
ilość_skrzyżowań
numer_wyjścia
numer_skrzyżowania_na_którym_znajduje_się_Jasio numer_na_którym_znajduje_się_wilk
Labirynt:
nr_skrzyżowania skrzyżowania sąsiednie
....
Wyjście:
TAK oraz numer skrzyżowania(wyjścia) do którego ma uciec Jasio lub NIE jeśli ucieczka jest niemożliwa
Przykład:
Wejście:
5
0
2 4
0 1
1 0 2 3
2 1 3 4
3 1 2 4
4 3 2
Wyjście:
TAK 1
Rozwiązanie
Metodą rozwiązania problemu będą grafy. Skrzyżowania reprezentują wierzchołki grafu. Z uwagi na to, że będą to głównie grafy małe i rzadkie, użyjemy reprezentacji listowej. Dla uproszczenia zakładamy, że graf jest spójny.
Ucieczka do wyjścia będzie możliwa, jeśli droga Jasia do wyjścia będzie krótsza niż droga wilka do wyjścia. W tym celu użyjemy algorytmu BFS (przeszukiwania wszerz). Należy zacząć przeglądanie grafu od miejsca, w którym znajduje się wyjście(wyjście będzie korzeniem drzewa BFS). Sprawdzamy, czy Jasio jest w bliższym sąsiedztwie niż wilk. Jeżeli tak - wyświetlamy sukces. Jeżeli nie, rozwiązujemy problem dalej:
Detonacja dynamitu musi odbyć się w punkcie artykulacji. Należy znaleźć punkty artykulacji w grafie, następnie zmierzyć odległość miedzy nimi a wilkiem i Jasiem. Ponownie stosujemy metodę z punktu 1).
Implementacja
Do dyspozycji mamy pakiet funkcji odpowiadających za budowę grafu, algorytm BFS oraz
Zaawansowane algorytmy
Strona 2 Projekt 2: Grafy
Projekt 2: Grafy Strona 3