Является ли это оптимальной проблемой путешествия в сжатые сроки на деревьях?

Один из моих друзей спрашивает меня о следующей проблеме планирования на дереве. Я считаю, что это очень чисто и интересно. Есть ли какая-либо ссылка на это?

Проблема: Существует дерево , каждое ребро имеет симметричную стоимость перемещения 1 . Для каждой вершины есть задача, которую необходимо выполнить до истечения срока . Задача также обозначается как . Каждая задача имеет единое значение 1. Время обработки равно 0 для каждой задачи , т. Е. Посещение задачи до истечения срока ее выполнения равно завершению ее. Не ограничивая общности, пусть обозначает корень и в предположении, что в нет задачи . Есть автомобиль на $T(V,E)$ $v_i$ $d_i$ $v_i$ $v_0$ $v_0$ $v_0$ в момент времени 0 Кроме того, мы предполагаем, что для каждой вершины $d_i \ge dep_i$ , обозначает глубину . Это самоочевидно, вершина с крайним сроком, меньшим ее глубины, должна быть принята как отклонение. Задача состоит в том, чтобы найти расписание, которое завершит как можно больше задач. $dep_i$ $v_i$

Прогресс:

Если дерево ограничено путем, то оно находится в посредством динамического программирования. $\mathsf{P}$
Если дерево обобщено на граф, то оно в -полном. $\mathsf{NP}$
У меня очень простой жадный алгоритм, который считается трехфакторной аппроксимацией. Я не доказал это полностью. Правильно, меня больше интересуют результаты NP-hard. :-)

Спасибо за ваш совет.

ds.algorithms graph-algorithms np-hardness Пэн Чжан
источник

На полном графике задача будет легкой, верно? Просто используйте простой жадный алгоритм ...

Джо,

@Joe: Да. Потому что для каждого края требуется 1 единица перемещения, поэтому среди «перекрестков» нет предпочтений. Вы все еще заинтересованы в этой проблеме, если да. может быть, мы можем поговорить по электронной почте. :-)

Пэн Чжан

Что если все сроки совпадают и / или мы только спрашиваем, можно ли выполнить все задачи?

Domotorp

@domotorp: Если он просит завершить все задачи в один срок, ответ ДА, если и только если единый срок

, Просто глубинный поиск. Что касается оптимальной задачи на случай

Я не знаю, легко ли это. Есть много вариантов этой проблемы, например, что делать, если крайние сроки принимают значения из конечного множества, мощность которого постоянна? Большое спасибо за ваш комментарий.

d \geq | V |

$d\ge |V|$

d < | V |

$d< |V|$

Пэн Чжан

Я бы сказал, что NP-Hard см. Расписание зоопарка , за исключением случаев, когда я неправильно понял вашу проблему.

Гопи

Ответы:

Не уверен, что это ваш ответ (см. Ниже), но слишком долго для комментариев.

Я думал, что ваша проблема была чем-то вроде: $(P|tree;p_i=1|\Sigma T_i)$ , где:

$P$ обозначает идентичные однородные процессоры,
«дерево» обозначает ограничение приоритета в виде дерева,
обозначает вес задачи, равный 1, и $p_i=1$
$\Sigma T_i$ означает минимизацию суммы опозданий (т. Е. Количества задач, которые завершаются после истечения срока).

Если это так, то ваша проблема NP-трудна: вы можете рассматривать это как обобщение минимизации общего опоздания на одной машине с ограничениями приоритета . В самом деле, в этой статье говорится, что для нескольких линейных цепочек это NP-сложный процесс на одном процессоре. Простое преобразование - взять деревья вида один корень и линейные цепочки, начиная с корня.

Однако я удивлен, потому что вы, кажется, говорите, что для случая одной линейной цепочки вы бы использовали динамическое программирование. Я не понимаю, зачем вам нужен DP, так как мне кажется, что при планировании одной линейной цепочки у вас нет большого выбора из-за ограничений приоритета: только один выбор. Так что, возможно, я неправильно понял вашу проблему.

Гопи
источник

Моя проблема, кажется, отличается от вашей. Мое - это «корневое дерево, стоимость путевого ребра за единицу времени, каждая вершина с задачей со сроком исполнения, задача не требует времени для прецессии. Начиная с корня, сколько задач можно выполнить?». Таким образом, нет приоритета, нет времени, необходимого для обработки задачи. Большое спасибо.

Пэн Чжан

@PengZhang, если это корневое дерево, то есть приоритет? Что касается стоимости по краям (приоритет?) Или по задачам, мне кажется, это одно и то же. Я действительно не вижу разницы между ними. Наконец, сколько задач может быть выполнено, если вы минимизируете количество задач, которые завершаются после их крайнего срока, это эквивалентно максимизации количества задач, которые можно выполнить. Может быть, вы могли бы нарисовать картину того, что вы ожидаете?

Гопи

Я не вижу четкой связи между двумя проблемами. В исходной задаче стоимость посещения следующего узла зависит от того, какой узел был посещен на предыдущем шаге. В расписании с ограничением приоритетов стоимость следующего задания для обработки не зависит от того, какое задание было обработано на предыдущем шаге, если выполняется ограничение приоритета.

Йошио Окамото

@Gopi: стоимость ребер не может быть "перенесена" на узлы, насколько я думаю. Если дерево ограничено путем (возможно, цепочкой, на которую вы ссылались), в моей задаче мы можем динамическое программирование следующим образом. Пусть вершины пронумерованы как

слева направо. Обозначим через

максимальные задачи из интервала положения

в момент времени

и транспортное средство стоит в точке

. Пусть

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)$ обозначают то же самое, что и

за исключением того, что автомобиль стоит на

. Тогда у нас

можно вывести из

. Поскольку

полиномиальны, поэтому dp полиномиален.

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$

Пэн Чжан

@PengZhang, ладно, думаю, я лучше понимаю, что ты имеешь в виду. Я все еще верю, что можно легко адаптировать бумагу, которую я дал, рассматривая специальные деревья, где ветви - это пути (отсюда и корневые пути).

Гопи

Чтобы это было правдой, мы должны сделать некоторые предположения. Смотрите комментарии ниже

Я полагаю, что для случая дерева существует алгоритм рекурсивного динамического программирования за полиномиальное время, параметризованный максимальным сроком исполнения. Подзадачи: если мы введем поддерево к моменту времени и выйдем из поддерева к моменту времени $t_a$ $t_b$ , какое максимальное количество задач мы можем выполнить в поддереве? Базовые случаи на листьях легки и мы запоминаем снизу вверх.

Если бы мы действительно параметризовались по максимальному сроку, то алгоритм на самом деле не был бы полиномиальным по размеру дерева. Однако длина самого длинного пути, который посещает каждый узел дерева, является полиномиальной только в и нам никогда не нужно проверять сроки позже, чем это. $|V|$

Джо
источник

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

$f[a, t, t']$

a

$a$

[t, t^{'}]

$[t,t']$

a

$a$

Пэн Чжан

Точка (1) не такая большая проблема, как точка (2). Чтобы моя идея работала так, как я ее представлял, она требует, чтобы вы не выходили и повторно входили в поддерево несколько раз. Не очевидно, что лучшее решение не прыгает по всему дереву: получает лист и что-то около корня и идет к листу, а затем к другому листу, далеко от других 2, и т. Д. Вы можете использовать тот факт, что вы получите все узлы на любом пути, по которому вы идете. В частности, если какой-либо ребенок был посещен, тогда родитель уже посещен.

Джо

На мой взгляд, пункт (1) действительно является проблемой . Для пункта (2) я назвал ограничение «нет повторного ввода» как ограничение «Поиск в глубину». Ограничение DFS обычно принимается в литературе. И при этом ограничении моя проблема действительно полиномиальна, пока максимальная степень дерева постоянна . Поэтому мне интересно, что у меня вопрос NP-сложный. Большое спасибо.

Пэн Чжан

Что касается ограничения DFS, легко построить пример, где оптимальная последовательность нарушает это ограничение. Рассмотрим полное сбалансированное бинарное дерево с 7 узлами. Пусть 2 листа в левом поддереве имеют сроки 2 и 12, 2 листа в правом поддереве имеют сроки 8 и 6, а внутренние узлы имеют сроки 100. Вы можете посетить все узлы, посетив листья в порядке 2,6,8 , 12; любой другой заказ нарушает хотя бы один срок.

Мм

Проблема получения постоянной аппроксимации для этого случая или доказательства его NP-Hard все еще остается открытой, и любой результат может стать хорошей публикацией. Некоторые особые случаи были раскрыты. У меня, наряду с другими, есть некоторые частичные результаты, которые решают особые случаи, такие как пауки, деревья постоянной высоты. Но общая проблема для деревьев не решена.

vgta
источник