Czy ten optymalny problem z podróżą w terminach NP-trudnych na drzewach?

Jeden z moich znajomych pyta mnie o następujący problem z planowaniem na drzewie. Uważam, że jest bardzo czysty i interesujący. Czy jest na to jakieś odniesienie?

Problem: Istnieje drzewo , każda krawędź ma symetryczny koszt podróży 1 . Dla każdego wierzchołka nie jest to zadanie, które musi być wykonane przed jego termin . Zadanie jest również oznaczone jako . Każde zadanie ma jednolitą wartość 1. Czas przetwarzania wynosi 0 dla każdego zadania , tzn. Odwiedzenie zadania przed upływem terminu jest równe jego ukończeniu. Bez utraty ogólności, niech oznacza rdzeń i zakładając, że nie ma zadania zlokalizowanego na . W znajduje się pojazd $T(V,E)$ $v_i$ $d_i$ $v_i$ $v_0$ $v_0$ $v_0$ w czasie 0. Ponadto zakładamy, że dla każdego wierzchołka $d_i \ge dep_i$ , oznacza głębokość . Jest to oczywiste, ponieważ wierzchołek z terminem krótszym niż jego głębokość należy traktować jako odstający. Problem polega na znalezieniu harmonogramu, który zakończy jak najwięcej zadań. $dep_i$ $v_i$

Postęp:

Jeśli drzewo jest ograniczone do ścieżki, to jest w za pomocą programowania dynamicznego. $\mathsf{P}$
Jeżeli drzewo uogólnić na wykresie, to jest -Complete. $\mathsf{NP}$
Mam bardzo prosty, zachłanny algorytm, który uważa się za aporoksymację 3-czynnikową. Nie udowodniłem tego całkowicie. Teraz bardziej interesują mnie wyniki trudne dla NP. :-)

Dzięki za radę.

ds.algorithms graph-algorithms np-hardness Peng Zhang
źródło

Na pełnym wykresie zadanie byłoby łatwe, prawda? Wystarczy użyć prostego algorytmu chciwości ...

Joe,

@Joe: Tak. Ponieważ każda krawędź potrzebuje 1 jednostki podróży, więc nie ma preferencji wśród „skrzyżowań”. Czy nadal jesteś zainteresowany tym problemem, jeśli tak. może możemy porozmawiać przez e-mail. :-)

Peng Zhang,

Co jeśli wszystkie terminy są takie same i / lub pytamy tylko, czy wszystkie zadania można ukończyć?

domotorp

@domotorp: Jeśli prosi o zakończenie wszystkich zadań w jednym terminie, odpowiedź brzmi TAK, jeśli tylko jednolity termin

. Tylko głębokie pierwsze wyszukiwanie. Jeśli chodzi o optymalny problem w sprawie

, Nie wiem czy to łatwe. Istnieje wiele wariantów tego problemu, na przykład rozważenie, czy terminy przyjmują wartości ze zbioru skończonego, którego liczność jest stała? Dziękuję bardzo za komentarz.

d \geq | V |

$d\ge |V|$

d < | V |

$d< |V|$

Peng Zhang

Powiedziałbym, że NP-hard widzi zoo planowania , chyba że źle zrozumiałem twój problem.

Gopi

Odpowiedzi:

Nie jestem pewien, czy to jest twoja odpowiedź (patrz poniżej), ale trochę za długo na komentarze.

Myślałem, że twój problem był taki: $(P|tree;p_i=1|\Sigma T_i)$ , gdzie:

oznacza identyczne jednorodne procesory, $P$
„drzewo” oznacza pierwszeństwo ograniczenia formy drzewa,
oznacza wagę zadań równą 1, a $p_i=1$
$\Sigma T_i$

W takim przypadku problem jest trudny do rozwiązania: można go postrzegać jako uogólnienie minimalizowania całkowitej spóźnienia na pojedynczej maszynie z ograniczeniami pierwszeństwa . Rzeczywiście w tym dokumencie stwierdzono, że w przypadku wielu łańcuchów liniowych jest trudny do przeprowadzenia na jednym procesorze. Łatwa transformacja polega na wzięciu drzew z jednego korzenia i liniowych łańcuchów zaczynających się od korzenia.

Jestem jednak zaskoczony, ponieważ wydaje się, że w przypadku pojedynczego łańcucha liniowego użyłbyś programowania dynamicznego. Nie rozumiem, dlaczego miałbyś potrzebować DP, ponieważ wydaje mi się, że planując pojedynczy łańcuch liniowy, nie masz dużego wyboru z powodu ograniczeń pierwszeństwa: tylko jeden wybór. Więc może źle zrozumiałem twój problem.

Gopi
źródło

Mój problem wydaje się inny niż twój. Moim jest: „ukorzenione drzewo, jednostkowa krawędź kosztu podróży, każdy wierzchołek z zadaniem z terminem, zadanie nie potrzebuje czasu na precesję. Począwszy od korzenia, ile zadań można ukończyć?”. Więc nie ma pierwszeństwa, nie ma czasu potrzebnego na przetworzenie zadania. Dziękuję Ci bardzo.

Peng Zhang

@PengZhang, jeśli jest to ukorzenione drzewo, to są pierwszeństwo? Jeśli chodzi o koszty na krawędziach (pierwszeństwo?) Lub na zadaniach, wydaje mi się, że to samo. Naprawdę nie widzę różnicy między nimi. Wreszcie, ile zadań można ukończyć, jeśli zminimalizujesz liczbę zadań, które kończą się po ich terminie, jest to równoważne maksymalizacji liczby zadań, które można ukończyć. Może mógłbyś narysować obraz tego, czego oczekujesz?

Gopi

Nie widzę wyraźnego związku między dwoma problemami. W pierwotnym problemie koszt wizyty w kolejnym węźle zależy od tego, który węzeł odwiedzono w poprzednim kroku. W harmonogramie z ograniczeniami pierwszeństwa koszt następnego zadania do przetworzenia nie zależy od tego, które zadanie zostało przetworzone w poprzednim kroku, o ile spełnione jest ograniczenie pierwszeństwa.

Yoshio Okamoto

1, 2, \dots, n

$1,2,\cdots, n$

f (t, l, r)

$f(t,l,r)$

[l, r]

$[l,r]$

t

$t$

l

$l$

g (t, l, r)

$g(t,l,r)$

f (t, l, r)

$f(t,l,r)$

r

$r$

f (t, l, r)

$f(t,l,r)$

{f (\cdot, l + 1, r), g (\cdot, l, r - 1)

$\{f(\cdot,l+1,r), g(\cdot,l,r-1)$

t, l, r

$t,l,r$

Peng Zhang,

@PengZhang, ok, myślę, że lepiej rozumiem, co masz na myśli. Nadal uważam, że można łatwo dostosować papier, który podałem, biorąc pod uwagę specjalne drzewa, w których gałęzie są ścieżkami (stąd ukorzenione ścieżki).

Gopi

Aby było to prawdą, musimy poczynić pewne założenia. Zobacz komentarze poniżej

$t_a$ $t_b$

$|V|$

Joe
źródło

f [a, t, t^{'}]

$f[a, t, t']$

a

$a$

[t, t^{'}]

$[t,t']$

a

$a$

punkt (1) nie stanowi tak dużego problemu jak punkt (2). Aby mój pomysł zadziałał tak, jak go sobie wyobrażałem, wymaga, abyś nie wychodził i nie wchodził ponownie do drzewa podrzędnego wiele razy. Nie jest oczywiste, że najlepsze rozwiązanie nie przeskakuje dookoła drzewa: dostaje liść i coś blisko korzenia i podchodzi do liścia, a następnie do innego liścia daleko od pozostałych 2 itd. Być może uda ci się aby wykorzystać fakt, że wszystkie węzły będą dostępne na dowolnej ścieżce, którą idziesz. W szczególności, jeśli odwiedzono jakieś dziecko, rodzic już jest odwiedzany.

Joe

: W mojej opinii punkt (1) jest rzeczywiście problemem . Dla punktu (2) nazwałem ograniczenie „brakiem ponownego wprowadzania” jako ograniczenie „Głębokie pierwsze wyszukiwanie”. Ograniczenie DFS jest powszechnie przyjęte w literaturze. I pod tym ograniczeniem mój problem jest rzeczywiście wielomianowy, o ile maksymalny stopień drzewa jest stały . Zastanawiam się więc, czy moje pytanie jest trudne NP. Dziękuję Ci bardzo.

Peng Zhang

Jeśli chodzi o ograniczenie DFS, łatwo jest skonstruować przykład, w którym optymalna sekwencja narusza to ograniczenie. Rozważ kompletne, zrównoważone drzewo binarne z 7 węzłami. Niech 2 liście w lewym poddrzewie mają terminy 2 i 12, 2 liście w prawym poddrzewie mają terminy 8 i 6, a wewnętrzne węzły mają terminy 100. Możesz odwiedzić wszystkie węzły, odwiedzając liście w kolejności 2,6,8 , 12; każde inne zamówienie narusza co najmniej jeden termin.

mhum,

Problem uzyskania stałego przybliżenia dla tego przypadku lub udowodnienia, że NP-Hard jest nadal otwarty i każdy wynik byłby dobrą publikacją. Niektóre specjalne przypadki zostały rozwiązane. Ja wraz z innymi mam częściowe wyniki, które rozwiązują specjalne przypadki, takie jak pająki, drzewa o stałej wysokości. Ale ogólny problem drzew jest nierozwiązany.

VGTA
źródło