Puzzle wywiadu na temat podróżowania na odcinku linii

Na linii liczbowej długości M, gdzie 0 < M <= 1,000,000,000podałeś N( 1 < N <= 100,000) liczby całkowite par punktów. W każdej parze pierwszy punkt reprezentuje miejsce, w którym aktualnie znajduje się obiekt, a drugi punkt reprezentuje miejsce, w którym należy przenieść obiekt. (Pamiętaj, że secondpunkt może być mniejszy niż first).

Załóżmy, że zaczynasz od punktu 0i masz wózek, który może pomieścić 1przedmiot. Chcesz przenieść wszystkie obiekty z ich początkowych pozycji do odpowiednich końcowych pozycji podczas podróży najmniejszą odległości wzdłuż linii liczbowej ( nie przesunięcia). Musisz skończyć na punkcie M.

Teraz staram się zredukować ten problem do prostszego. Szczerze mówiąc, nie mogę nawet wymyślić rozwiązania brutalnej siły ( być może zachłannego). Jednak moją pierwszą myślą było zdegenerowanie ruchu wstecz do dwóch ruchów do przodu, ale nie wydaje się to działać we wszystkich przypadkach.

Narysowałem tutaj 3przykładowe przypadki testowe:

Odpowiedź na pierwsze testcase jest 12. Najpierw podnosisz redprzedmiot w punkcie 0. Następnie przejdź do punktu 6(odległość = 6), redtymczasowo upuść element, a następnie podnieś greenelement. Następnie przejdź do punktu 5(odległość = 1) i upuść greenelement. Następnie wróć do punktu 6(odległość = 1) i podnieś redupuszczony przedmiot, przejdź do punktu 9 (odległość = 3), a następnie przejdź do punktu 10(odległość = 1), aby zakończyć sekwencję.

Całkowity przebyty dystans wynosił 6 + 1 + 1 + 3 + 1 = 12minimalną możliwą odległość.

12Wierzę, że pozostałe dwa przypadki mają odpowiedzi . Nie mogę jednak znaleźć ogólnej zasady, aby ją rozwiązać.

Czy ktoś ma jakieś pomysły?

1. Jeśli jesteś pusty, zacznij przesuwać się w prawo.

2. Ilekroć dotrzesz do obiektu i będziesz pusty, podnieś go (duh) i idź w kierunku jego celu.

3. Ilekroć dotrzesz do przedmiotu, aktóry już nosisz b, zawsze wybieraj którykolwiek z obiektów ma najmniejszy numerycznie cel (najdalej w lewo).

4. Jeśli nie jesteś jeszcze w M, wróć do kroku 1.

Jest to optymalne: Jedynym miejscem, w którym masz prawdziwy wybór, jest krok 3. Najpierw obsłużenie najbardziej wysuniętego na lewo miejsca docelowego gwarantuje, że do czasu wysłania obu obiektów znajdziesz się jak najdalej po prawej stronie.

Dlaczego to pytanie dotyczy programmers.sx? Tak, „pytanie do wywiadu”, ale to tylko fajna zagadka.

PS. Jeśli chodzi o implementację, wystarczy lista zadań (całkowite pary punktów) posortowane według oryginalnej pozycji.

Załóżmy, że otrzymujesz te ruchy, (a, b), (c, d), (e, f), ...to minimalna odległość do przebycia to abs(b - a) + abs(d - c) + abs(f - e) + ...faktyczna odległość, którą podróżujesz abs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ....
Zasadniczo, biorąc pod uwagę tablicę ruchów, celem jest zminimalizowanie funkcji „odległości podróży” poprzez zamianę elementów. Jeśli weźmiesz pod uwagę konkretną kombinację jako węzeł, a wszystkie kombinacje, które możesz z niej wyciągnąć jako krawędzie, możesz użyć jednego z wielu algorytmów wyszukiwania grafów, wokół których wykorzystuje się heurystykę. Jednym z przykładów jest wyszukiwanie wiązki .

Być może nie rozumiem problemu, ale co z następującymi kwestiami:

1. Posortuj pary według pierwszego numeru pary, która jest bieżącą lokalizacją
2. Przesuń wzdłuż linii zamieniając elementy do ich właściwej lokalizacji (masz zmienną temp)

Fakt, że jest posortowany, gwarantuje, że nie będziesz chodził tam i z powrotem po elementach, aby umieścić je w odpowiednim miejscu (niezależnie od tego, czy linia jest reprezentowana jako tablica czy lista)

Zaktualizuj po komentarzu @templatetypedef:
Użyj a, HashTableaby zapisać wszystkie pary. Użyj bieżącej lokalizacji każdej pary jako klucza indeksu.
Użyj drugiego indeksu nad parami.

 1. Get next pair according to index from the line.
 2. If current pair exists in hashtable then place element to its target location.  
    2.a Remove pair from hashtable.  
    2.b Make current pair the target location. Then go to step 1  
 ELSE 
        Increment current index until you get a pair present in the hashtable. Go to step 2  

Moja skłonność do algorytmu, który jest w zasadzie chciwy:

Zbuduj listę punktów, które należy przenieść. Ponieważ optymalizacja tego nie jest częścią wymaganego problemu, nie będę się martwić o jego zorganizowanie.

while !Done
    if CartIsEmpty()
        FindClosestObjectToMove()
        MoveToObject()
       LoadCart()
    else
        Destination = Cart.Contains.Target
        CurrentMove = [Location, Destination]
        SubList = List.Where(Move.Within(CurrentMove))
        if !SubList.Empty
            Destination = SubList.FindSmallest(Location, Move.Origin)
        MoveTo(Destination)
        if !Destination.Empty
            SwapCart()
            UpdateTaskList()
        else
            EmptyCart()
            DeleteTask()

Myślę, że dotyczy to wszystkich przypadków. W pewnym sensie jest rekurencyjny, ale poprzez aktualizację listy zamiast wywoływania siebie.

Jest to asymetryczny problem sprzedawcy podróżującego . Możesz myśleć o tym jak o wykresie. Krawędzie będą każdą parą (początek, koniec), jedną dla każdej (0, początek) i wszystkimi innymi parami (koniec, początek).

Zakładając, że NP! = P, będzie miał wykładniczy oczekiwany czas działania.