Вместо того, чтобы делать эту домашнюю задачу для вас, я спрошу вас через мыслительный процесс, который получает ответ ...
1) Что бы вы сделали с графом abc (три вершины,два ребра и однозначно ациклические)?Представьте на мгновение, что вам нужно наложить несколько меток на некоторые вершины, вы знаете, что вы получите минимум самого длинного пути в «центральной» вершине.(б, с возможной меткой «1») Но для того, чтобы сделать это за один шаг, нужны психические силы.Так что спросите себя, от чего б 1 шаг.Если самый длинный путь к b равен 1, и мы только что сделали шаг назад по этому пути, какова длина нашего пути до сих пор?(самый длинный путь = 1, -1 для заднего шага. Ага: 0).Так что это должна быть метка для листьев.
2) Что это предлагает в качестве первого сокращения для алгоритма?Отметьте листья "0", отметьте их восходящие "1", отметьте их восходящие "2" и так далее.Маршируя по листьям и подсчитывая расстояние по ходу дела ...
3) Хмм ... У нас проблема с графиком abcd.(Отныне помеченная вершина будет заменена на ее метку.) Маркировка листьев "0" дает 0-bc-0 ... Мы не можем получить два центра ... Черт, что мы делаем в более простомусловие 0-б-1?Мы хотим пометить b как «1», так и «2» ... Обрабатывать их в обратном порядке ...
В 0-b-1, если мы продолжим путь от b слева до одного, мыполучить путь длины 1. Если мы продолжим путь справа от b, мы получим 2. Мы хотим отслеживать «длину самого длинного пути от v до любого другого узла», поэтому мы хотим отслеживать самый длинный путь доб.Это означает, что мы помечаем b как «2».
0-b-1 -> 0-2-1
В 0-bc-0 компьютер на самом деле одновременно не обновляет b и c.Он обновляет один из них, давая либо 0-1-c-0, либо 0-b-1-0, а следующее обновление дает 0-1-2-0 или 0-2-1-0.Оба b и c являются «центрами» этого графа, поскольку каждый из них отвечает требованию «узел v в дереве, который минимизирует длину самого длинного пути от v до любого другого узла».(Эта длина равна 2).
Это приводит к другому наблюдению: результат вычисления не в том, чтобы пометить граф, а в том, чтобы найти последнюю вершину, которую мы помечаем, и / или вершину, которая заканчивается наибольшимэтикетка.(Возможно, нам не удастся найти хороший способ заказа этикеток, поэтому в конечном итоге нам понадобится найти максимум в конце. Или, может быть, мы найдем. Кто знает.)
4) Так что теперьу нас есть что-то вроде: сделайте две копии графика - помеченную копию и полную копию.Первый из них будет хранить метки, и это тот, который будет иметь окончательный ответ.Сгоревшая копия будет становиться все меньше и меньше по мере удаления из нее немеченых вершин (чтобы найти новые помечаемые вершины).(Есть другие способы организовать это так, чтобы использовалась только одна копия графика. Когда вы дойдете до конца, поняв этот ответ, вы должны будете найти способ уменьшить эти потери.) Краткое содержание:
label = 0
while the burndown graph is nonempty
collect all the leaves in the burndown-graph into the set X
for each leaf in the set X
if the leaf does not have a label
set the leaf's label (to the current value of label)
delete the leaf from the burn-down graph (these leafs are two copies of the same leaf in the input graph)
label = label+1
find the vertex with the largest label and return it
5) Если вы действительно посмотрите этот прогон, вы заметите несколько возможностей для сокращения.Включая замену поиска в последней строке схемы гораздо более быстрым методом распознавания ответа.
А теперь общие советы по стратегии для задач с алгоритмом:
* Сделайте несколько небольших примеров вручную.Если вы не понимаете, как делать маленькие дела, вы не сможете сразу же подсказать и рассказать компьютеру, как делать большие дела.* Если какой-либо из вышеперечисленных шагов казался немотивированным или совершенно непрозрачным, вам нужно будет учиться намного, намного сложнее, чтобы преуспеть в области компьютерных наук.Это может быть информатика не для тебя ...