Temat: Algorytm slepe (sid, temat 2) - zadania (fwd)

Ponizej sa zadania, a rozwiazania w zalaczniku

* [trzeba] wyjasnic eliminacje stanow

  -->> Przy szukaniu optymalnego rozwiazania w grafach nie zawsze wystarczy
       prosta eliminacja stanow wczesniej odwiedzonych
       podana w algorytmie na wykladzie (strona 55).
       W niektorych algorytmach do danego stanu dochodzi sie
       roznymi sciezkami, niekoniecznie w kolejnosci rosnacego kosztu tych sciezek
       (dobrze, zeby studenci sami na to wpadli).

       Zastanowic sie, ktorym algorytmom nie wystarczy prosta eliminacja stanow odwiedzonych
       a) w przypadku rownego kosztu wszystkich przejsc miedzy stanami:
          nie wystarczy w DFS (oczywiste)
           warto, zeby studenci tez zauwazyli i uzasadnili,
           ze w BFS i iteracyjnym poglebianiu wystarczy,
           bo pierwsza sciezka, ktora znajdziemy, bedzie najkrotsza
       b) w przypadku roznych kosztow przejsc:
          w strategii jednolitego kosztu nie wystarczy,
          niech studenci wymysla kontrprzyklad (zob. wskazowki)

          Potem niech studenci wymysla jak uzupelnic algorytm Graph-Search,
          zeby bylo dobrze (zob. wskazowki) 
       

* [trzeba] przyklad wykonania algorytmu jednolitego kosztu dla grafu,
              juz ze sprawdzaniem i poprawianiem dlugosci sciezek,
              mapa Rumunii ze sciezka z Aradu do Bukaresztu
              wydaje mi sie bardzo dobrym przykladem (w zalaczeniu),
              dobrze byloby uwaznie przesledzic zawartosc kolejki priorytetowej 'fringe',
              z zaznaczaniem wyjmowanych miast i poprawianiem kosztu sciezek

* [warto] zadanie 3.13 z ksiazki (zob. wskazowki)
                
 * [trzeba] przeszukiwanie iteracyjnie wydluzane
               zadanie 3.11 z ksiazki, tam jest opis algorytmu,
               niech studenci sami sprobuja wymyslec,
               potem optymalnosc i zlozonosc,
               czyli punkty a,b,c z zad. 3.11  (zob. wskazowki)

* [mozna] Grafy skonczone z ujemnymi kosztami sciezki (zob. wskazowki)
              1) Najpierw przyklad grafu, w ktorym nie ma optymalnej sciezki,
                tzn. koszt moze byc dowolnie ujemny
              2) Pokazac, ze rozwiazanie optymalne nie istnieje
                  <-> graf zawiera cykl z ujemna suma krawedzi taki,
                        ze mozna do niego dojsc ze stanu poczatkowego,
                        a z niego dojsc do stanu docelowego
                 (ale zeby algorytm sie nie petlil, to lepiej, zeby w ogole nie bylo takiego cyklu)
              3) 3.17a
              4) 3.17b

Rozwiazania:
Przyklad, ze nie wystarczy zapamietac stan
przy wkladaniu do kolejki, bo
pierwsza znaleziona sciezka z A do D
w strategii jednolitego kosztu dla grafow
jest nieoptymalna:

      A
   1/   \2
   B     C
   3\   /1
      D

----------------------------

Jak usprawnic graph-search (wyklad, str. 55)
zapamietujac stany przed wlozeniem do kolejki?

jesli znaleziony stan A byl juz odwiedzony,
ale jest jeszcze w kolejce 'fringe',
trzeba sprawdzic,
czy znaleziona sciezka jest krotsza
od poprzednio znalezionej dla stanu A,
jesli tak, wystarczy poprawic
wartosc stanu A w kolejce 'fringe'
na ta krotsza


----------------------------

Zadanie 3.13
Odp. Pojedynczy lancuch: A1 -> A2 -> .......-> An

----------------------------

Zadanie 3.11 (przeszukiwanie iteracyjnie wydluzane)
b) d iteracji
c) liniowa tzn. rowna liczbie wszystkich stanow
   ktore maja krotsza sciezke, niz stan docelowy


----------------------------

Grafy skonczone z ujemnymi kosztami sciezki 

1)graf z ujemna suma krawedzi w jakims cyklu

2) Nieoczywiste moze pokazanie, ze jak dowolnie ujemne sciezki to musi byc cykl.
   Jak rozwazymy sobie wszystkie sciezki zawierajace kazdy stan conajwyzej raz,
   to ich jest skonczona ilosc. No to wezmy sciezke o koszcie mniejszym od
   wszystkich takich. Pewien stan musi wystapic tam conajmniej 2 razy.
   Wycinamy sciezke miedzy dwoma wystapieniami tego stanu (to jest cykl).
   Jak dalej mamy jakis stan z conajmniej dwoma wystapieniami,
   to znowu wycinamy cykl, itd. az dostaniemy sciezke, na ktorej kazdy stan
   wystepuje conajwyzej raz. Z zalozenia koszt tej sciezki jest wyzszy
   niz tej, od ktorej zaczelismy. A wiec przynajmniej jeden z wycietych cyklow
   musial miec ujemna sume krawedzi. CBDU.

3) Warto uzasadniac tylko przy zalozeniu, ze rozwiazanie optymalne istnieje.
   Musimy przejrzec wszystkie osiagalne stany, bo jesli ktorys pominiemy,
   to moze sie zdarzyc, ze akurat z niego jest ujemna krawedz do stanu docelowego,
   dajaca w sumie mniejszy koszt sciezki niz wszystkie pozostale sciezki
   do stanu docelowego.

4) Pomaga. Jak optymalne rozwiazanie istnieje, to musi istniec takie,
   ze ma <=n krawedzi (bo w optymalnym rozwiazaniu kazdy cykl
   musi miec sume 0, i mozna wszystkie wyciac).
    Rozwazmy algorytm jednolitego kosztu graph-search.
   Dziala on dobrze z tym, ze stan moze byc wielokrotnie wkladany
   do kolejki priorytetowej 'fringe'.
   NIech n - liczba stanow.
   Jak mamy juz sciezke do stanu docelowego o koszcie s,
   a w kolejce priorytetowej wszystkie stany maja juz koszt >= s+nc
   to mozna przestac.