Kilka lat temu wziąłem kurs algorytmów, w którym podawaliśmy następujący problem (lub jeden taki):

Jest budynekn podłogi z windą, które mogą poruszać się tylko po 2 piętra naraz i 3 piętra naraz. Korzystając z programowania dynamicznego, napisz funkcję, która obliczy liczbę kroków potrzebnych windy do przejścia z podłogii na podłogęj.

Jest to oczywiście łatwe dzięki podejściu stanowemu, tworzysz tablicę n elementów długo i wypełniasz ją wartościami. Można nawet użyć technicznie niepaństwowego podejścia, które polega na akumulowaniu wyniku jako rekurencyjnego przekazywania go. Moje pytanie brzmi: jak to zrobić w sposób niepaństwowy, używając leniwej oceny i wiążąc węzeł.

Myślę, że opracowałem poprawny wzór matematyczny:

gdziei+2 ii-3 mieszczą się w dozwolonych wartościach.

Niestety nie mogę go przerwać. Jeśli umieściłemi+2 sprawa najpierw, a następnie wybierz równą podłogę Mogę ją oszacować na równych piętrach poniżej poziomu docelowego, ale to wszystko. Podejrzewam, że strzela prosto do najwyższej równej podłogi dla wszystkiego innego, spada 3 poziomy, a następnie powtarza się, na zawsze oscylując między kilkoma górnymi piętrami.

Prawdopodobnie więc bada nieskończoną przestrzeń (lub skończoną, ale z pętlami) w pierwszej głębi. Nie mogę wymyślić, jak zbadać przestrzeń w pierwszej kolejności, bez korzystania z wielu struktur danych, które skutecznie naśladują podejście stanowe.

Chociaż ten prosty problem jest rozczarowująco trudny, podejrzewam, że widząc rozwiązanie w 1 wymiarze, mógłbym sprawić, by działało ono w dwuwymiarowej wariacji problemu.

EDYCJA: Wiele odpowiedzi próbowało rozwiązać problem w inny sposób. Sam problem nie jest dla mnie interesujący, pytanie dotyczy zastosowanej metody. Podejście Chaosmattera do tworzeniaminimal funkcja, która może porównywać potencjalnie nieskończone liczby, jest prawdopodobnie krokiem we właściwym kierunku. Niestety, jeśli próbuję utworzyć listę reprezentującą budynek o 100 piętrach, obliczenie trwa zbyt długo, ponieważ rozwiązania problemów podrzędnych nie są ponownie wykorzystywane.

Podjąłem próbę użycia struktury danych, do której można się odwoływać, ale nie kończy się, istnieje jakaś nieskończona pętla. Opublikuję mój kod, abyś mógł zrozumieć, na co mam zamiar. Zmienię zaakceptowaną odpowiedź, jeśli ktoś może faktycznie rozwiązać problem, używając dynamicznego programowania w strukturze danych z własnym odniesieniem, używając lenistwa, aby uniknąć obliczania rzeczy więcej niż jeden raz.

levels = go [0..10]
  where
    go [] = []
    go (x:xs) = minimum
      [ if i == 7
          then 0
          else 1 + levels !! i
        | i <- filter (\n -> n >= 0 && n <= 10) [x+2,x-3] ]
      : go xs

Możesz zobaczyć jak1 + levels !! i próbuje odnieść się do wcześniej obliczonego wyniku i jakfilter (\n -> n >= 0 && n <= 10) [x+2,x-3] próbuje ograniczyć wartościi do ważnych. Jak powiedziałem, to nie działa, to po prostu pokazujemetoda przez które chcę rozwiązać ten problem. Inne sposoby rozwiązania tego problemunie interesujące mnie.