Ćwiczenia 20: Przeszukiwanie z nawrotami (ang. back-tracking)

  1. Napisz procedurę pierwsze, która dla danej liczby całkowitej \(n\) (\(n>1\)) wyznacza
    rozbicie \(n\) na sumę minimalnej liczby składników będących liczbami pierwszymi.
    (Możesz założyć prawdziwość hipotezy Goldbacha.)
  2. Dany jest (multi-)zbiór kostek domina.
    Należy wyznaczyć maksymalny łańcuch, jaki można ułożyć z danych kostek, oczywiście zgodnie z zasadami domina.
    Rozwiązanie powinno mieć postać procedury domino : (α * α) list → (α * α) list.
    Klocki można obracać.
  3. [XIV OI] Atrakcje turystyczne (uproszczone).
    Mamy \(n\) miejscowości, ponumerowanych od 1 do \(n\).
    Odległości między miejscowościami są dane w postaci (symetrycznej) tablicy liczb całkowitych, o wymiarach \(n \times n\).

    Chcemy zwiedzić wszystkie te miejscowości, jednak nie w dowolnej kolejności.
    Mamy daną listę ograniczeń postaci \([(i_1, j_1); \dots; (i_k,j_k)]\).
    Ograniczenie \((i,j)\) oznacza, że miasto \(i\) musi być zwiedzone przed miastem \(j\).
    Możesz założyć, że ograniczenia da się spełnić.

    Na początku wyruszamy z miasta 1, a kończymy podróż w mieście \(n\).
    Wyznacz minimalną drogę jaką trzeba przejechać, żeby zwiedzić wszystkie miasta.