Как называется алгоритм, в котором заданный отрезок собирается из набора отрезков меньшей длины?
Собственно, есть набор отрезков различной длины, и есть линия заданной длины, вдоль которой нужно уложить эти отрезки так, чтобы полностью её заполнить (т.е. от самого начала до самого конца - ни больше, ни меньше). Как называется алгоритм, при помощи которого это можно сделать?
Например, есть набор цепей Маркова (фразы из 1, 2, 3 слов) и предложение из, например, 12 слов. Нужно уложить все эти фразы в предложении так, чтобы каждая из них обязательно встречалась в предложении. Т.е. должен использоваться весь набор.
Или, например, в архитектуре: у нас есть заданная длина фасада и набор типовых блоков по 2, 3 и 6 метров, которые нужно разложить вдоль этого фасада.
Что-то никак не могу сформулировать запрос в Гугль, чтобы найти алгоритмы для решения этой задачи :(
Уточните задачу. В задачи про цепи маркова есть набор отрезков, даны правила, как их можно накладывать друг на друга и надо набрать определенную длину. К тому же надо и спользовать все блоки. Во второй задаче, судя по условию, отрезки нельзя пересекать и надо лишь набрать заданную длину. Ничего не сказано про обязательность использования всех отрезков.
Это принципиально разные задачи. Сформулируйте конкретно, что за задача у вас, и вам, возможно, смогут помочь.
Пока первая задача звучит как упаковка строк, а вторая - как задача о рюкзаке или размена сдачи монетами.
Wataru, с цепями Маркова, возможно, не самый удачный пример привёл. Тут скорее задача про размен монет. Т.е можно разменять и так и сяк, но по возможности насыпать монет как можно более разнообразно, т.е. каждой по одному разу как минимум выдать.
Но цепи Маркова приводил, скорее, для задачи по архитектуре. Потому как там есть критерий эстетической сочетаемости соседних блоков (т.е. есть правила).
Мне, почему-то, кажется, что это не разные задачи, а разновидность одной (просто с доп. условиями).
Дмитрий, Нет, если можно пересекать отрезки, то это гораздо более сложная задача.
Что касается эстетической сочетемости соседних блоков - то вам надо придумать метрику. Формальный способ сказать, какая из комбинаций более эстетичная. В самом простом случае - у вас будет матрица штрафа за расположение двух заданных плиток рядом и в решении надо общую сумму штрафа минимизировать.
То, что каждую монету надо хоть раз взять - ну вы просто из всей длины вычтите длины всех "монет" по одному разу, а дальше ограничения уже и нет.
Скорее всего, ваша задача решается динамическим программированием, как и задача о размене монет.
Wataru, эстетическая сочетаемость как раз и задаётся в виде Марковских цепей (ну, по крайней мере я так себе это представлял :) Т.е. одна фраза заканчивается этим словом, а другая с него же и начинается, т.е. своего рода константное перекрытие в 1 блок.
Но мне нужно иметь возможность как-то эту "сочетаемость" иногда отключать, и тогда задача вырождается до простого размена монет.
Подойдёт ли тут алгоритм поиска пути? Что-то вроде Дейкстры или A*? Они, вроде бы, универсальны для любых графовых структур?
Дмитрий, поиск пути будет работать, если у вас всегда есть перекрытие по всем словам, кроме одного, и надо обязательно использовать все фразы по ровно одному разу. Это будет задача о эйлеровом пути.
Спасибо за помощь!
Да, задача раскроя может сводиться к задаче о рюкзаке. А вот то, что все эти задачи имеют целый набор алгоритмов для их решения, включая точные и неточные, алгоритмы поиска пути, полный перебор и даже генетические алгоритмы - всё это определённости не добавляет...
Дмитрий, сформулируйте свою задачу максимально точно, указав все требования, ограничения и возможные пределы значений. Тогда я смогу вам подсказать конкретный алгоритм.
Wataru, сформулировать точно задачу - для меня на данном этапе это и есть часть задачи, с которой мне уже никто не поможет :) Спасибо вам ещё раз за участие. Дальше попробую самостоятельно.
Простой
Простой