Извините, я не могу придумать название алгоритма или задачи для следующего алгоритма. Я изложу проблему, а затем то, что я пробовал, и, возможно, кто-то может указать мне правильное направление.
Представьте, что у вас есть сумка с предметами (неупорядоченными, дубликаты разрешены). На практике сумка может содержать от 2 до 20 предметов, если это поможет.
Цель состоит в том, чтобы найти цепочку минимальной длины (нумерованный список ссылок, если у нас разные представления о цепочке), которая содержит все предметы в мешке в любом порядке.
Цепочка состоит из начального жетона (его нет в сумке), за которым следует любое количество предметов, за которым следует конечный жетон (тоже не в сумке).
Цепочка формируется путем объединения n-кортежей (порядок важен), и в качестве дополнительной послабления допустим, что значение n одинаково для всех кортежей. На практике я работаю с n = 3. Цепочки могут быть «смешанными», а не конкатенированными, если они имеют перекрывающиеся элементы. Например, рассмотрим (a,b,c) и (c,d,e). Могут быть соединены как (a,b,c,d,e). Точно так же (a,b,c) и (b,c,d) могут быть соединены как (a,b,c,d). Некоторые кортежи могут иметь начальный токен в первой позиции, а некоторые токены имеют конечный токен в последней позиции, что, конечно, позволяет найти решение проблемы.
Так что мне кажется, что точное решение задачи вообще неразрешимо. Для получения «хорошего» решения проблемы потребуется какой-то алгоритм оптимизации. «Хорошие» решения, с которыми я могу жить.
Я начал с жадного подхода, когда при первом проходе вы находите кортеж, содержащий наибольшее количество элементов в мешке, произвольно разрывая связи. Создайте структуру данных, содержащую построенную нами цепочку, и вставьте выбранный кортеж в эту структуру данных. Разделите проблему на 2 подзадачи: сторону начального маркера и сторону конечного маркера. До тех пор, пока первый токен структуры данных подзадачи 1 не станет начальным токеном, а последний токен подзадачи 2 не будет конечным токеном, наращивайте цепочку так, чтобы мы пытались как можно скорее найти условие остановки (начальный или конечный токен в зависимости от над подзадачей), одновременно пытаясь исчерпать содержимое мешка как можно скорее. Это может быть нехорошо, потому что каждая подзадача должна сообщаться друг с другом относительно того, сколько предметов осталось в сумке, которые необходимо включить.
Кто-нибудь видел эту проблему где-нибудь? Любые мысли о том, как улучшить (или заставить работать правильно) этот алгоритм? Это реальная проблема, которую я решаю, которая является умной частью гораздо более крупной системы, а не игрушечной проблемой или проблемой домашнего задания.
ИЗМЕНИТЬ
Извините все, что я был далеко от компьютера сегодня. Я постараюсь опубликовать пример решения, которое не слишком тривиально, но и не слишком сложно, чтобы его увидеть.
Данный:
Bag = {A, B, C, D}(я делаю набор для примера, но каждый элемент может появляться более одного раза)/ = Start Token\ = End Token3-Tuples (тройки): я обозначаю их буквами g для простоты именования. Строчные буквы не имеют реальной функции в задаче.
(/,A, E) a (/,C, D) b (/,G, H) c (D,B, A) d (C,G, H) e (B,A, \) f (G,H, \) g
Решение: если соединить вместе b, d и f, получится (/,C,D,B,A,\).
Это кратчайшая возможная цепочка, содержащая все элементы в мешке, длина которой равна 6, если считать начальный и конечный маркеры. В общем случае кратчайший путь имеет длину |BAG| + 2, если он действительно существует. Я надеюсь, что моя формулировка проблемы теперь имеет больше смысла.
