Структура данных для сопоставления коллекций с состояниями в алгоритме динамического программирования

Я кодирую для удовольствия алгоритм для определения наилучшего порядка построения объектов N Building. Конечно, каждое здание имеет свои характеристики (например, стоимость, производство, время постройки и т. д.). Также существует полное упорядочение объектов Building на основе этих характеристик.

В какой-то момент моего динамического программирования мне нужна адаптированная структура данных, чтобы получить наилучший результат, достигнутый на данный момент, для построения k (k‹=N) здания. Мне нужна эта структура данных, чтобы каким-то образом «отобразить» набор k зданий (возможно, отсортированных, поскольку строительство здания b1, а затем b2 или b2, а затем b1 оставляет меня с теми же зданиями Nk, но, скорее всего, может привести к разным состояниям) в «лучший уровень» охвата до сих пор.

Вероятно, я мог бы использовать простой HashMap, но это подразумевает многократное повторение коллекций, содержащих одни и те же элементы, не принимая во внимание, например, что [b1,b2] является подколлекцией [b1,b2,b3,b4].

Я надеюсь, что я достаточно ясно выразился в этом, и я благодарю вас за вашу помощь :)


java algorithm data-structures dynamic-programming
person Jean Logeart    schedule 28.05.2011    source источник
comment
Проблема не ясна на 100%, но, возможно, было бы полезно иметь класс BuildingSet, который может содержать объекты как Building, так и BuildingSet? Тогда у вас может быть BuildingSet x = [b1, b2] и BuildingSet y = [x, b3, b4].   -  person Cephron    schedule 28.05.2011

Ответы (3)


arrow_upward
0
arrow_downward

Невозможно ответить, не зная структуры ваших решений.

Но если решение для k можно получить из решения (k-1) путем вставки здания b в позицию j, то вы можете просто получить хэш-карту, отображающую целое число i в «дельту» между решением для i и решением для i-1, выраженное парой.

Но иметь дело с дельтами явно может быть отвратительно, потому что вам нужно выполнить обход, чтобы получить решение. Вы можете решить эту проблему, сообщив дельте ссылочные дельты (т. е. передав дельту для (k-1) в конструкторе дельты для k), а затем предоставив метод getSolution(), который выполняет фактический обход.

Вы можете распространить эту идею на аналогичные структуры решений.

person akappa    schedule 28.05.2011

arrow_upward
0
arrow_downward

Вы можете использовать LinkedHashSet для ключа, а значение — это стоимость строительства Зданий, содержащихся в наборе, в порядке итерации. Это немного хак, но в соответствии с hashCode и equals он должен работать. Если вы предпочитаете быть более явным, используйте хэш-карту набора для пары стоимости и порядка сборки.

person karmakaze    schedule 28.05.2011

arrow_upward
0
arrow_downward

Если ваши решения выглядят как ABC,cost1, ABCD,cost2, создайте связанный список d->c->b->a. Храните решения в виде кортежей стоимости и ссылки на последний элемент, содержащийся в вашем решении (самый ранний в списке).

person Nicolas78    schedule 29.05.2011