Я пытался решить эту проблему тремя различными способами - оптимизированной грубой силой, подходом динамического программирования и жадным алгоритмом.Первые два не могли обрабатывать входные данные для n > 17, но генерировали оптимальные решения, поэтому я мог использовать их для проверки средней производительности жадного метода.Сначала я начну с подхода динамического программирования, а затем опишу жадный.
Динамическое программирование
Во-первых, обратите внимание, что мы можем, если определим, что (1, 2, 3, 4) и (5, 6, 7, 8) суммадо меньшего значения, чем (3, 4, 5, 6) и (1, 2, 7, 8), тогда ваше оптимальное решение не может содержать как (3, 4, 5, 6), так и (1, 2, 7, 8) - потому что вы можете поменять их на первое и иметь меньшую сумму.Расширяя эту логику, мы получим одну оптимальную комбинацию (a, b, c, d) и (e, f, g, h), которая дает минимальную сумму из всех комбинаций x0, x1, x2, x3, x4, x5, x6, x7, и поэтому мы можем исключить все остальные.
Использованиеэто знание, мы можем быть словарным отображением всех x0, x1, x2, x3, x4, x5, x6, x7 комбинаций из набора [0, n), к их минимальным суммам путем грубого форсирования сумм всех комбинаций x0, x1, x2, x3.Затем мы можем использовать эти сопоставления, чтобы повторить процесс для x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11 из x0, x1, x2, x3, x4, x5, x6, x7 и x0, x1, x2, x3 пар.Мы повторяем этот процесс до тех пор, пока не получим все минимальные суммы для x0, x1 ... x_(4*m-1), которые затем итерируем, чтобы найти минимальную сумму.
def dp_solve(const_dict, n, m):
lookup = {comb:(comb,) for comb in const_dict.keys()}
keys = set(range(n))
for size in range(8, 4 * m + 1, 4):
for key_total in combinations(keys, size):
key_set = set(key_total)
min_keys = (key_total[:4], key_total[4:])
min_val = const_dict[min_keys[0]] + const_dict[min_keys[1]]
key1, key2 = min(zip(combinations(key_total, 4), reversed(list(combinations(key_total, size - 4)))), key=lambda x:const_dict[x[0]]+const_dict[x[1]])
k = tuple(sorted(x for x in key1 + key2))
const_dict[k] = const_dict[key1] + const_dict[key2]
lookup[k] = lookup[key1] + lookup[key2]
key, val = min(((key, val) for key, val in const_dict.items() if len(key) == 4 * m), key=lambda x: x[1])
return lookup[key], val
По общему признанию, эта реализация довольно грубая, потому что я продолжал микро-оптимизирующую часть послекусок, надеющийся сделать это достаточно быстро, без необходимости переключаться на жадный подход.
Greedy
Это, вероятно, тот, который вас волнует, так как он обрабатывает довольно большие входные данные быстро и довольно точно.
Начните с создания списка для частичных сумм и начните перебирать элементы в словаре, увеличивая значение.Для каждого элемента найдите все частичные суммы, которые не создают коллизий с их ключами, и «объедините» их в новую частичную сумму и добавьте в список.При этом вы создаете список минимальных частичных сумм, которые можно создать из наименьших значений k в вашем словаре.Чтобы ускорить все это, я использую хэш-наборы, чтобы быстро проверить, какие частичные суммы содержат пары одного и того же ключа.
В «быстром» жадном подходе вы прервите момент, когда найдете частичную сумму, которая имеетдлина ключа 4 * m (или, что эквивалентно, m 4-кортежа).Это обычно дает довольно хорошие результаты в моем опыте, но я хотел добавить немного логики, чтобы сделать его более точным, если это необходимо.Для этого я добавляю два множителя -
extra_runs - которые определяют, сколько дополнительных итераций нужно искать для поиска лучших решений, прежде чем ломать check_factor - которые задают кратноетекущий поиск "глубина" для сканирования вперед для одного нового целого числа, которое создает лучшее решение с текущим состоянием.Это отличается от вышеупомянутого тем, что он не «сохраняет» каждое новое проверенное целое число - он только делает быструю сумму, чтобы увидеть, создает ли он новый минимум.Это делает это значительно быстрее, за счет того, что другие m - 1 4-кортежи уже должны существовать в одной из частичных сумм.
В сочетании эти проверки, кажется, всегда находят истинную минимальную сумму,по стоимости примерно в 5 раз дольше (хотя все еще довольно быстро).Чтобы отключить их, просто передайте 0 для обоих факторов.
def greedy_solve(const_dict, n, m, extra_runs=10, check_factor=2):
pairs = sorted(const_dict.items(), key=lambda x: x[1])
lookup = [set([]) for _ in range(n)]
nset = set([])
min_sums = []
min_key, min_val = None, None
for i, (pkey, pval) in enumerate(pairs):
valid = set(nset)
for x in pkey:
valid -= lookup[x]
lookup[x].add(len(min_sums))
nset.add(len(min_sums))
min_sums.append(((pkey,), pval))
for x in pkey:
lookup[x].update(range(len(min_sums), len(min_sums) + len(valid)))
for idx in valid:
comb, val = min_sums[idx]
for key in comb:
for x in key:
lookup[x].add(len(min_sums))
nset.add(len(min_sums))
min_sums.append((comb + (pkey,), val + pval))
if len(comb) == m - 1 and (not min_key or min_val > val + pval):
min_key, min_val = min_sums[-1]
if min_key:
if not extra_runs: break
extra_runs -= 1
for pkey, pval in pairs[:int(check_factor*i)]:
valid = set(nset)
for x in pkey:
valid -= lookup[x]
for idx in valid:
comb, val = min_sums[idx]
if len(comb) < m - 1:
nset.remove(idx)
elif min_val > val + pval:
min_key, min_val = comb + (pkey,), val + pval
return min_key, min_val
Я проверил это для n < 36 и m < 9, и, похоже, он работал довольно быстро (пару секунд, чтобы завершить в худшем случае),Я предполагаю, что это должно работать для вашего случая 12 <= n <= 24 довольно быстро.