układanie w stosy w teorii grafów

Proszę, pomóżcie mi znaleźć dobre rozwiązanie tego problemu.układanie w stosy w teorii grafów

Mamy n pudełek z 3 wymiarami. Możemy je ukierunkować, a my chcemy umieścić je na górze, aby mieć wysokość maksymum. Możemy umieścić pudełko na innym pudełku, jeśli 2 wymiary (szerokość i długość) są niższe niż wymiary pudełka poniżej.

Dla przykładu mamy 3 wymiary w * D * h, możemy pokazać to w (h * d, d * h, w * d, d * W, h * w, w * h) proszę o pomoc mi rozwiązać to w teorii grafów. w tym problemie nie możemy umieścić (2 * 3) powyżej (2 * 4), ponieważ ma on taką samą szerokość. 2-wymiar powinien być mniejszy niż pole

Źródło

2010-12-26 mozhdeh

Czy istnieje jakiś konkretny powód, aby rozwiązać ten problem za pomocą teorii grafów? – TalentTuner

Pomóżcie rozwiązać co? Powiedziałeś, że możesz układać pola, ale nie zadałeś tego pytania. – marcog

@Saurabh, ponieważ prawdopodobnie musi pokazać, że jest to NP-complete. Myślę o tagu pracy domowej. –

AKTUALIZACJA (poprawna? Ale prawdopodobnie nie najskuteczniejsza):

Każde pole staje się 3 wierzchołkami (wywołaj te wierzchołki). Uzyskaj ważoną DAG. Zmodyfikuj algorytm opisany here Sortuj topologicznie (ignorując fakt, że niektóre wierzchołki są powiązane), postępuj zgodnie z algorytmem, ale zamiast tablicy liczb całkowitych zachowaj listę ścieżek, które prowadzą do każdego wierzchołka. Następnie dodając ścieżki do nowego wierzchołka ("w" w algerze wiki) utwórz listę ścieżek, które do niej prowadzą, upuszczając ścieżki do v, które zawierają wierzchołek powiązany z w. W przeciwieństwie do oryginalnego algorytmu, ten jest wykładniczy.

ORIGINAL ODPOWIEDŹ ŹLE (patrz komentarze):

Każde opakowanie staje się 3 węzły na jego powierzchni 3 rozmiarach. Następnie utwórz ukierunkowany wykres łączący każdą powierzchnię ze wszystkimi powierzchniami o mniejszych rozmiarach. Przypisz cenę do każdej krawędzi, aby była równa 3. wymiarowi węzła (tj. Wysokości), do której prowadzi krawędź. Teraz jest problem ze znalezieniem longest path problem in a DAG.

Źródło

2010-12-26 18:50:55

Niezupełnie, ponieważ jeśli używasz jednego węzła, dwa inne są wykluczone. –

@Keith Randall doskonały punkt! Więc nie rozdzielaj pól na 3 węzły. Ponieważ przypisujemy wagi do krawędzi, a nie do węzłów, masa krawędzi jest po prostu maksymalną wysokością możliwą do uzyskania od węzła źródłowego przechodzącego do węzła docelowego. Zatem przejście do węzła X z węzłów A i B może mieć wyższą wagę dla A, jeśli A jest większe niż B. Zatem jest to nadal najdłuższa ścieżka w DAG możliwa do rozwiązania w czasie wielomianowym. –

@Keith Randall nie, nieważne, to też nie działa, ponieważ waga zależy od tego, jak dotarliśmy do węzłów A i B. Cholera, tak blisko! –

Edytuj: Działa tylko wtedy, gdy nie można obrócić pól wokół wszystkich osi.

Jeśli dobrze rozumiem pytanie, można je rozwiązać za pomocą programowania dynamicznego. Prostym algorytmem określającym wysokość maksymalnego stosu jest:

Zacznij od obracania wszystkich pudełek, tak aby dla Box B_i, w_i < = d_i. Zajmuje to czas O (n).

Teraz posortuj pola zgodnie z dolnym obszarem w_i * d_i i pozwól, aby indeksowanie to pokazało. Zajmuje to czas O (n log n).

Teraz B_i można umieścić na B_j tylko, jeśli I < j, ale i < j nie oznacza, że B_i może być na B_j.

Największy z B_j stos na górze jest albo

B_j na ziemi
Stos z pierwszych pól J-1, w B_j na górze.

Teraz można utworzyć rekurencyjnego wzoru do obliczania wysokości maksymalnej stosu

H (J) = max (h_j max (H (i) | i < j d_i < d_j, w_i < w_j) + h_j)

i obliczając max (H (j), i < = j < = n) otrzymamy wysokość maksymalnego stosu.

Jeśli chcemy rzeczywisty stos, możemy dołączyć pewne informacje do funkcji H i zapamiętać indeksy.

Źródło

2010-12-26 21:34:37 utdiscant

Myślę, że brakuje ci ważnego faktu, że pole można obrócić dowolnie, tak, że szerokość może stać się wysokością i na odwrót. –

@MK: Jesteś absolutnie poprawny , I missed this – utdiscant

@utdiscant Niewielka korekta do formuły H (j) = max (h_j, max (H (i) | i

układanie w stosy w teorii grafów

Odpowiedz

Powiązane problemy