Dobry wieczór! Właśnie odbywam staż w Archives Nationales of France i napotkałem sytuację, którą chciałem rozwiązać za pomocą wykresów ...

I. Zakurzona sytuacja

Chcemy zoptymalizować rozmieszczenie książek w mojej bibliotece zgodnie z ich wysokością, aby zminimalizować koszty archiwizacji. Wysokość i grubość książek są znane. Książki ułożyliśmy już w porządku rosnącym$H_1,H_2,\dots,H_n$(Nie wiem, czy to była najlepsza rzecz, ale ... tak to zrobiliśmy). Znając grubość każdej książki, możemy określić dla każdej z nich$H_i$ określ wymaganą grubość do ich ułożenia, nazwij to $L_i$ (na przykład, które są $H_i = 23\,\mathrm{cm}$ wysoki może mieć całkowitą grubość $L_i = 300\,\mathrm{cm}$).

Biblioteka może produkować niestandardowe półki, wskazując pożądaną długość i wysokość (bez problemu z głębokością). Półka wysokości$H_i$ i długość $x_i$ koszty $F_i+C_ix_i$, gdzie $F_i$ jest kosztem stałym i $C_i$ to koszt półki na jednostkę długości.

Pamiętaj, że półka wysokości $H_i$ może służyć do przechowywania książek wysokości $H_j$ z $j\leq i$. Chcemy zminimalizować koszty.

Mój nauczyciel zasugerował, że modeluję ten problem jako problem ze znalezieniem ścieżki. Model może obejmować$n+1$ forma indeksowana wierzchołków $0$ do $n$. Mój mentor zasugerował, że opracowałem istniejące warunki, znaczenie każdej krawędzi i jak opracować wycenę$v(i,j)$ związane z krawędzią $(i,j)$. Byłbym również w porządku z innymi rozwiązaniami, a także ze spostrzeżeniami.

Na przykład mamy dla konwencji (mroczny okres historii Francji) taką tablicę:

II. Założenia mola szkoleniowego praktykanta

Myślę, że muszę obliczyć algorytm między Djikstrą, Bellmanem lub Bellmanem-Kalabą ... Próbuję dowiedzieć się, który z nich w poniższych podrozdziałach.

1. Warunki

Jesteśmy tutaj z problemem wyszukiwania ścieżki między wierzchołkiem $0$ i wierzchołek $n$, $n$ musi pochodzić z $0$ (to znaczy między ścieżką musi istnieć ścieżka (lub spacer) $0$ i $n$

2.Co obliczyć (zaktualizowano (25/10/2015))

// Nadal pracuję, o ile nie wiem, które wierzchołki i które krawędzie modelować ...

Moje najlepsze przypuszczenie

Myślę, że pozbywamy się co najmniej jednego rodzaju półek za każdym razem, gdy znajdziemy najkrótszą ścieżkę z tablicy, ale to tylko moje założenie ...;).

Myślę, że najlepszy sposób modelowania sposobu kupowania półek i przechowywania naszych książek musi wyglądać jak na poniższym wykresie (ale proszę, nie wahaj się krytykować mojej metody!;))

wierzchołki:

• $i\in[1,4]$ to półki, których możemy użyć do przechowywania naszych książek.
• $0$jest stanem, w którym żadna książka nie jest przechowywana. Korzystanie z tego wierzchołka pozwala mi używać każdej formuły kosztu (krawędzi).

krawędzie: $F_i+C_ix_i,i\in[1,4]$są kosztami przy użyciu rodzaju półki. na przykład:$F_1+C_1x_1$ fom 0 to koszt używania tylko półek typu 1 do przechowywania naszych pergaminów, rękopisów ...

Jednak stąd nie wiem, jak stworzyć mój najkrótszy problem.

Rzeczywiście, nie wiedziałbym, gdzie schowałbym wszystkie moje książki.

To prowadzi mnie do innego pomysłu ...

inny pomysł...

Tutaj szukam najkrótszej ścieżki od danego wierzchołka do stanu 0, czyli wiedząc, że najwyższy dokument to $type \ i$ wysoki, szukam najtańszego sposobu na uporządkowanie dokumentów.

wierzchołki:

• $i\in[1,4]$ to półki, których możemy użyć do przechowywania naszych książek.
• $0$to stan, w którym przechowywane są wszystkie książki. Korzystanie z tego wierzchołka pozwala mi używać każdej formuły kosztu (krawędzi).

krawędzie: $F_i+C_ix_i,i\in[1,4]$są kosztami przy użyciu rodzaju półki. na przykład:$F_1+C_1x_1$ od 3 to koszt użycia $type \ 1$ półki po użyciu $type \ 3$ półki do przechowywania naszych pergaminów, rękopisów ...

Nie wiem jednak, gdzie umieścić $F_4+C_4x_4$.

3.Jak obliczyć

Myślę, że musimy zacząć od wyższych półek, o ile możemy następnie przechowywać mniejsze książki ...

Zrobić

Bierzemy $L_n$ cm z $H_{i=n}$ wysokość w półce o ich wysokości + $z$ cm $H_{i=n-1}$ wysokość, aż stanie się droższy niż biorąc $H_{i=n-1}$odłożyć na półkę. następnie$i=i-1$

Podczas gdy i> <0

Wreszcie, nie wiem, jak różnicować x ...

To znaczy, jak wybrać $x_i$ dokumenty w $4$ lub $3$ na przykład.

Widzę, jak pytasz: „Chcę rozwiązać ten problem za pomocą algorytmu Dijkstry, ale nie mogę ustawić dobrego wykresu do uruchomienia”, dlatego przedstawię ci taki wykres.

Digraph, w którym wierzchołki to zestawy półek z książkami.

Ok, mamy książki o wysokości $H_n,$ $1 \le n \le N$ i szerokości $W_n,$ z wysokościami w porządku rosnącym dla każdej książki i chcemy pogrupować je w półki.

Ponownie użyj tych liczb dla węzłów rozwiązania $n,$ gdzie ten węzeł reprezentuje stan rozwiązania „wszystkie książki $i \le n$ zostały odłożone. ”Dlatego zaczniemy od węzła $0$ i staraj się dostać do węzła $N$najkrótszą ścieżką z algorytmem Dijkstry. Te węzły są wierzchołkami naszego wykresu.

Następnie rysujemy z węzła $i$ do dowolnego węzła $j \gt i$ skierowana krawędź, która zakłada, że ​​wszystkie te książki pośrednie będą półki z jedną półką, tj. długość tej krawędzi wynosi

Algorytm Dijkstry da nam ścieżkę do węzła o najkrótszej długości $N.$

Myślę, że mam rozwiązanie twojego problemu. Mam nadzieję, że nie zrozumiałem czegoś w definicji twojego problemu. Oto jest:

Opiszę podejście do programowania dynamicznego. To jest$O(n^{2})$ algorytm, co oznacza, że ​​skoro liczba książek jest ogromna, niewiele ci to pomoże. (musisz go trochę zmodyfikować!). Przy odrobinie pracy możesz zamienić wspomniane podejście programowania dynamicznego na przykład znalezienia najkrótszej ścieżki na ukierunkowanym wykresie acyklicznym. (Który sam jest algorytmem programowania dynamicznego: P)

Załóżmy, że są $n$ książki o różnej wysokości.

Załóżmy również, że optymalne koszty osiąga się, przypisując książki do $i$ półki wysokości $h_{1},h_{2},...,h_{i}$ gdzie $h_{1}<h_{2}<...<h_{i}$.

Udowodnijmy następujące dwie rzeczy:

ZA. $C_{a}>C_{a-1}$

Załóżmy, że jest inaczej. Pozwolić$B_{a-1}$ być zestawem książek przypisanych do półki $a-1$ Następnie $cost = other,stuff + C_{a-1}*thickness(B_{a-1})$

Ponieważ zakładaliśmy, $C_{a}<C_{a-1}$, przenieśmy wszystkie książki z półki $a-1$ do $a$ (co jest możliwe od tego czasu $h_{a-1}<h_{a}$.

Więc teraz, $cost =other,stuff + C_{a}*thickness(B_{a})$który jest niższy niż wcześniej. Mamy zatem sprzeczność z powodu założonej przez nas Optymalności.

Więc $C_{a}>C_{a-1}$ dla wszystkich utworzonych półek

B. Niech $j$ być książką przypisaną do półki $a$. Udowodnijmy to$height(j)>h_{a-1}$

To jest dość łatwe. Gdyby$height(j)$ był mniejszy niż $h_{a-1}$ możemy odłożyć książkę na półkę $a-1$ dla lepszego kosztu (ze względu na A).

Z dwóch rzeczy, które udowodniliśmy, B jest znaczący.

Pozwolić $dp[a]$= optymalny koszt półek na książki $1...a$ aby była półka $height(a)$. Musisz znaleźć sposób na zdefiniowanie$dp[a]$ według wartości $dp[1],dp[2],....dp[a-1]$

Zatrzymam się tutaj. Jeśli znasz programowanie dynamiczne, korzystając z faktu B, z łatwością wymyślisz powtórzenie. W przeciwnym razie zapytaj :). Jak powiedziałem, można to zmienić w problem DAG. Znając powyższą relację, łatwo zdać sobie sprawę z tego, co stanowi przewagę$(a,b)$ oznacza i określa jego koszt.

Wreszcie, jak powiedziałem powyżej, ponieważ książki są duże, nie można używać algorytmu dla każdej książki. Myślę, że reprezentowanie jego wysokości przez sumę grubości powinno załatwić sprawę. (Myślę, że tak już jest w twoim oświadczeniu)

(Zgaduję, że liczba różnych wysokości jest znacznie mniejsza niż liczba książek)

Czasami samo „powiększenie” „najbliższego problemu” w literaturze może pomóc w zrozumieniu teorii i tła problemu, zbudować abstrakcję i wyeliminować fałszywe szczegóły. Najbliższym twoim problemem w literaturze jest tak zwany „problem pakowania pojemników o zmiennej wielkości”. Przykładowe dokumenty znajdują się poniżej. Problem ten jest wysoce teoretycznie zbadany i istnieje pewne gotowe oprogramowanie, które ujawnia się w optymalizacji opakowań w np. Kontenerach transportowych ciężarówek. Istnieją również wersje, w których można dostosować rozmiar pojemnika. Istnieje wiele podejść algorytmicznych. na przykład, od 1 ^st papieru:

Problemem poruszonym w tym artykule jest ortogonalne pakowanie danego zestawu przedmiotów w kształcie prostokąta w minimalną liczbę trójwymiarowych prostokątnych pojemników.

• OPTYMALIZACJA TRÓJWYMIAROWEGO OPAKOWANIA NA BINACH POPRZEZ SYMULACJĘ / Dube, Kanavathy

• Problem z pakowaniem pojemników z niepewnymi objętościami i pojemnościami / Peng, Zhang

• 3d algorytmy pakowania bin stosu