Есть ли эффективный для памяти способ исследовать решения, которые генерируются из перестановок входных данных?
РЕДАКТИРОВАТЬ Я, возможно, решил это сам, пожалуйста, прокомментируйте мой ответ ниже.
у меня есть std::vector<Problem> problems и мне нужно создать соответствующий std::vector<Solution> solutions,
У меня есть алгоритм, который может генерировать кандидата Solution для данного Problem но оговорка в том, что порядок Я пытаюсь сгенерировать эти эффекты, можно ли решить весь набор.
// This function exists already. Solution::ok() tells us whether it worked.
Solution solve (
const Problem &,
const std::vector<Solution> & solutions_so_far);
Не только существование Solution меняются в зависимости от того, что уже было решено, но природа решения меняется, поэтому я не могу кэшировать результаты.
Мне нужен алгоритм, который будет исследовать все перестановки problemsвозвращаться по мере необходимости и возвращаться немедленно, когда будет найден полный набор решений.
Мы требуем, чтобы solutions[i] соответствует problems[i] но в остальном конкретный порядок вывода не имеет значения. Обратите внимание, что solutions_so_farвыше, подразумевает, что problems возможно, уже были перетасованы.
Вот интерфейс, который мне нужно реализовать
// Returns a corresponding list, or an empty list if no complete solution found
std::vector<Solution> solve (
std::vector<Problem>::iterator begin,
std::vector<Problem>::iterator end)
{
// ???
}
Теперь я застрял. Как мне это сделать?
Кроме того, я могу сделать это на месте? то есть переупорядочение problems с std :: move нормально но в идеале Я не хочу ничего выделять в куче за это. Я полагаю, что функция могла бы перетасовать ввод перед тем, как повториться, но я не могу конкретизировать эту смутную идею или убедить себя, что полностью покрываю пространство поиска, не повторяя какую-либо работу.
Решение
Вы можете выполнить свой алгоритм на множестве задач, на который ссылаются индексы, поэтому копии не будут сделаны, только перестановка индекса:
std::vector<Solution> solve(std::vector<Problem>::iterator begin,
std::vector<Problem>::iterator end)
{
// Create a solution
std::vector<Solution> ret(std::distance(begin, end));
// Define the search space
std::vector<int> indices(std::distance(begin, end)); // problem space
std::iota(indices.begin(), indices.end(), 0); // fill with the indices
do
{ // The mapping "solution-problem" can be done through the permutation state
int i(0);
for (auto it(indices.begin()), ite(indices.end()); it != ite; ++it)
{
ret[i] = solve(*(begin+(*it)), ret); // solve should acept ret range
if (ret[i++].ok())
{
if (it + 1 == ite) return ret; // all solved !
}
else break; // try another permutation
}
} while (std::next_permutation(indices.begin(), indices.end()));return std::vector<Solution>(); // empty list
}
Вектор индексов является обязательным, потому что std :: next_permutation требует «<«оператор, определенный для (в данном случае) класса задачи (или функции comp), и никаких упоминаний о таких функциях не делается (в MSVC вы получаете« error C2678: binary »<‘: не найден оператор, который принимает левый операнд типа’ Проблема ‘(или нет приемлемого преобразования) «)
Другие решения
Книга комбинаторное поколение имеет функцию, которая отображает лексикографический список перестановок на целые числа на странице 66. Например:
F4(0) = [1,2,3,4]
F4(1) = [1,2,4,3]
Кроме того, все, что вам нужно, — это итератор, который принимает перестановку (представленную в виде массива индексов) и перебирает два ваших списка в указанном порядке. Это потребует от вас выделения одного массива размером N (где N — длина ваших входных векторов) в куче.
Я хотел бы предупредить вас, что, как только вы получите около 8 или около того элементов, вы просто не сможете перебрать все перестановки (их слишком много).
Если вы абсолютно не можете выделить какую-либо память, то можете изменить порядок ввода, но это усложнит ваш код.
Я думаю, что у меня есть, но я не уверен, что это правильно. Может быть, кто-то может сказать с первого взгляда?
Во-первых, решатель на один случай.
typedef std :: vector <Problem> P;
typedef std :: vector <Solution> S;
bool solve (
P :: iterator problem,
S :: iterator so_far_start,
S :: iterator so_far_end,
Solution * output)
{
if (/* can find s consistent with [so_far_start...so_far_end)*/)
{
*output = s;
return true;
}
else
return false;
}
Расширяя это до упорядоченного списка.
bool solve_naive (
P :: iterator begin,
P :: iterator end,
S :: iterator out_begin,
S :: iterator out_end)
{
auto in = begin;
auto out = end;
while (in < end)
{
if (! solve (in, out_begin, out, &*out))
return false;
++in;
++out;
}
return true;
}
Теперь умный бит.
// reordering problems [at...end) as needed,
// write out corresponding solutions [out_at...out_end)
// consistent with [out_begin...out_at)
bool solve_permutations (
P :: iterator at,
P :: iterator end,
S :: iterator out_begin,
S :: iterator out_at,
S :: iterator out_end,
unsigned * limit)
{
if (end == at)
return true;
if (0 == -- *limit)
return false;
if (solve_naive (at, end, out_at, out_end))
return true;
// try each other input in first position, let
// recursion solve for some ordering of the remainder
for (auto in = at + 1; in < end; ++in)
{
std :: swap (*in, *at);
// this one must be solvable in first position
if (! route (at, out_begin, out_at, &*out_at))
continue;
// all the rest must be solvable in any position
if (solve_permutations (
at + 1,
end,
out_begin,
out_at + 1,
out_end,
limit))
{
return true;
}
}
return false;
}
Собираем все это вместе.
S solve_hopefully (P :: iterator begin, P :: iterator end)
{
S solutions (end - begin, {});
if (end - begin < WIDTH_LIMIT)
{
unsigned limit = DEPTH_LIMIT;
// Will help if this high-level function
// is called repeatedly.
std :: random_shuffle (begin, end);
return solve_permutations (
begin,
end,
solutions .begin (),
solutions .begin (),
solutions .end (),
& limit)
? solutions : S ();
}
else for (unsigned i = 0; i < SHUFFLE_LIMIT; ++i)
{
std :: random_shuffle (begin, end);
if (solve_naive (begin, end, solutions .begin (), solutions .end ())
return solutions;
}
return {};
}
Это выглядит хорошо для вас, ребята?
detector