пазл — Как разработать алгоритм для вычисления математического числа в стиле обратного отсчета

Я всегда хотел сделать это, но каждый раз, когда я начинаю думать о проблеме, она поражает меня своей экспоненциальной природой.

Решатель задач, который я хочу понять, и код для математической задачи обратного отсчета:

По заданному набору чисел от X1 до X5 рассчитайте, как их можно объединить, используя математические операции для создания Y.
Вы можете применять умножение, деление, сложение и вычитание.

Так как же 1,3,7,6,8,3 делать 348?

Ответ: (((8 * 7) + 3) -1) *6 = 348,

Как написать алгоритм, который может решить эту проблему? С чего начать, когда пытаешься решить такую ​​проблему? Какие важные соображения вы должны учитывать при разработке такого алгоритма?

23

Решение

Очень быстрое и грязное решение в Java:

public class JavaApplication1
{

public static void main(String[] args)
{
List<Integer> list = Arrays.asList(1, 3, 7, 6, 8, 3);
for (Integer integer : list) {
List<Integer> runList = new ArrayList<>(list);
runList.remove(integer);
Result result = getOperations(runList, integer, 348);
if (result.success) {
System.out.println(integer + result.output);
return;
}
}
}

public static class Result
{

public String output;
public boolean success;
}

public static Result getOperations(List<Integer> numbers, int midNumber, int target)
{
Result midResult = new Result();
if (midNumber == target) {
midResult.success = true;
midResult.output = "";
return midResult;
}
for (Integer number : numbers) {
List<Integer> newList = new ArrayList<Integer>(numbers);
newList.remove(number);
if (newList.isEmpty()) {
if (midNumber - number == target) {
midResult.success = true;
midResult.output = "-" + number;
return midResult;
}
if (midNumber + number == target) {
midResult.success = true;
midResult.output = "+" + number;
return midResult;
}
if (midNumber * number == target) {
midResult.success = true;
midResult.output = "*" + number;
return midResult;
}
if (midNumber / number == target) {
midResult.success = true;
midResult.output = "/" + number;
return midResult;
}
midResult.success = false;
midResult.output = "f" + number;
return midResult;
} else {
midResult = getOperations(newList, midNumber - number, target);
if (midResult.success) {
midResult.output = "-" + number + midResult.output;
return midResult;
}
midResult = getOperations(newList, midNumber + number, target);
if (midResult.success) {
midResult.output = "+" + number + midResult.output;
return midResult;
}
midResult = getOperations(newList, midNumber * number, target);
if (midResult.success) {
midResult.output = "*" + number + midResult.output;
return midResult;
}
midResult = getOperations(newList, midNumber / number, target);
if (midResult.success) {
midResult.output = "/" + number + midResult.output;
return midResult
}
}

}
return midResult;
}
}

ОБНОВИТЬ

Это в основном простой алгоритм грубой силы с экспоненциальной сложностью.
Тем не менее, вы можете получить некоторые улучшения, используя некоторые эвристические функции, которые помогут вам упорядочить последовательность чисел или (и) операций, которые вы будете обрабатывать на каждом уровне getOperatiosn() функция рекурсии.

Примером такой эвристической функции является, например, разница между средним результатом и общим целевым результатом.

Однако таким образом улучшаются только сложности в лучшем и среднем случаях. В худшем случае сложность остается нетронутой.

В худшем случае сложность может быть улучшена с помощью какого-либо отделения веток. Я не уверен, возможно ли это в этом случае.

6

Другие решения

Конечно, это экспоненциально, но крошечно, так что хорошая (достаточно) наивная реализация была бы хорошим началом. Я предлагаю вам отказаться от обычной инфиксной нотации с помощью скобок и использовать постфикс, это проще для программирования. Вы всегда можете предварительно настроить выходы как отдельный этап.

Начните с перечисления и оценки всех (действительных) последовательностей чисел и операторов. Например (в постфиксе):

1 3 7 6 8 3 + + + + + -> 28
1 3 7 6 8 3 + + + + - -> 26

Моя Java смехотворна, я не прихожу сюда, чтобы смеяться, поэтому я оставлю кодирование вам.

Всем умным людям, которые читают это: да, я знаю, что даже для небольшой проблемы, подобной этой, есть более разумные подходы, которые, вероятно, будут быстрее, я просто указываю OP на первоначальное рабочее решение. Кто-то другой может написать ответ с более умным решением (ями).

Итак, чтобы ответить на ваши вопросы:

  • Я начну с алгоритма, который, я думаю, быстро приведет меня к рабочему решению. В этом случае очевидным (для меня) выбором является исчерпывающий перечень и проверка всех возможных расчетов.
  • Если очевидный алгоритм выглядит непривлекательным по соображениям производительности, я начну задумываться о нем более подробно, вспомнив другие известные мне алгоритмы, которые, вероятно, будут обеспечивать более высокую производительность. Я могу вместо этого начать кодировать один из них.
  • Если я придерживаюсь исчерпывающего алгоритма и обнаружу, что на практике время выполнения слишком велико, я мог бы вернуться к предыдущему шагу и снова написать код. Но это должно стоить моего времени, должна быть сделана оценка затрат / выгод — пока мой код может превзойти Рэйчел Райли, я был бы удовлетворен.
  • Важные соображения включают мое время против компьютерное время у меня чертовски дороже.
6

Рабочее решение на с ++ 11 ниже.

Основная идея заключается в использовании оценки на основе стека (см. RPN) и преобразовать жизнеспособные решения в инфиксная запись только для демонстрации.

Если у нас есть N входные цифры, мы будем использовать (N-1) операторы, так как каждый оператор является двоичным.

Сначала мы создаем действительные перестановки операндов и операторов ( selector_ массив). Допустимая перестановка — это такая, которая может быть оценена без потери значения в стеке и заканчивается ровно одним значением (результатом) в стеке. таким образом 1 1 + действителен, но 1 + 1 не является.

Мы проверяем каждую такую ​​перестановку операндов-операторов с каждой перестановкой операндов ( values_ массив) и каждая комбинация операторов ( ops_ массив). Соответствующие результаты довольно напечатаны.

Аргументы взяты из командной строки как [-s] <target> <digit>[ <digit>...], -s Переключатель предотвращает исчерпывающий поиск, выводится только первый соответствующий результат.

(использование ./mathpuzzle 348 1 3 7 6 8 3 чтобы получить ответ на оригинальный вопрос)

Это решение не позволяет объединять входные цифры в числа. Это может быть добавлено в качестве дополнительного внешнего цикла.

Рабочий код можно скачать с Вот. (Примечание: я обновил этот код с поддержкой объединения входных цифр, чтобы сформировать решение)

Смотрите комментарии к коду для дополнительного объяснения.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iterator>
#include <string>

namespace {

enum class Op {
Add,
Sub,
Mul,
Div,
};

const std::size_t NumOps = static_cast<std::size_t>(Op::Div) + 1;
const Op FirstOp = Op::Add;

using Number = int;

class Evaluator {
std::vector<Number> values_; // stores our digits/number we can use
std::vector<Op> ops_; // stores the operators
std::vector<char> selector_; // used to select digit (0) or operator (1) when evaluating. should be std::vector<bool>, but that's broken

template <typename T>
using Stack = std::stack<T, std::vector<T>>;

// checks if a given number/operator order can be evaluated or not
bool isSelectorValid() const {
int numValues = 0;
for (auto s : selector_) {
if (s) {
if (--numValues <= 0) {
return false;
}
}
else {
++numValues;
}
}
return (numValues == 1);
}

// evaluates the current values_ and ops_ based on selector_
Number eval(Stack<Number> &stack) const {
auto vi = values_.cbegin();
auto oi = ops_.cbegin();
for (auto s : selector_) {
if (!s) {
stack.push(*(vi++));
continue;
}
Number top = stack.top();
stack.pop();
switch (*(oi++)) {
case Op::Add:
stack.top() += top;
break;
case Op::Sub:
stack.top() -= top;
break;
case Op::Mul:
stack.top() *= top;
break;
case Op::Div:
if (top == 0) {
return std::numeric_limits<Number>::max();
}
Number res = stack.top() / top;
if (res * top != stack.top()) {
return std::numeric_limits<Number>::max();
}
stack.top() = res;
break;
}
}
Number res = stack.top();
stack.pop();
return res;
}

bool nextValuesPermutation() {
return std::next_permutation(values_.begin(), values_.end());
}

bool nextOps() {
for (auto i = ops_.rbegin(), end = ops_.rend(); i != end; ++i) {
std::size_t next = static_cast<std::size_t>(*i) + 1;
if (next < NumOps) {
*i = static_cast<Op>(next);
return true;
}
*i = FirstOp;
}
return false;
}

bool nextSelectorPermutation() {
// the start permutation is always valid
do {
if (!std::next_permutation(selector_.begin(), selector_.end())) {
return false;
}
} while (!isSelectorValid());
return true;
}

static std::string buildExpr(const std::string& left, char op, const std::string &right) {
return std::string("(") + left + ' ' + op + ' ' + right + ')';
}

std::string toString() const {
Stack<std::string> stack;
auto vi = values_.cbegin();
auto oi = ops_.cbegin();
for (auto s : selector_) {
if (!s) {
stack.push(std::to_string(*(vi++)));
continue;
}
std::string top = stack.top();
stack.pop();
switch (*(oi++)) {
case Op::Add:
stack.top() = buildExpr(stack.top(), '+', top);
break;
case Op::Sub:
stack.top() = buildExpr(stack.top(), '-', top);
break;
case Op::Mul:
stack.top() = buildExpr(stack.top(), '*', top);
break;
case Op::Div:
stack.top() = buildExpr(stack.top(), '/', top);
break;
}
}
return stack.top();
}

public:
Evaluator(const std::vector<Number>& values) :
values_(values),
ops_(values.size() - 1, FirstOp),
selector_(2 * values.size() - 1, 0) {
std::fill(selector_.begin() + values_.size(), selector_.end(), 1);
std::sort(values_.begin(), values_.end());
}

// check for solutions
// 1) we create valid permutations of our selector_ array (eg: "1 1 + 1 +",
//    "1 1 1 + +", but skip "1 + 1 1 +" as that cannot be evaluated
// 2) for each evaluation order, we permutate our values
// 3) for each value permutation we check with each combination of
//    operators
//
// In the first version I used a local stack in eval() (see toString()) but
// it turned out to be a performance bottleneck, so now I use a cached
// stack. Reusing the stack gives an order of magnitude speed-up (from
// 4.3sec to 0.7sec) due to avoiding repeated allocations.  Using
// std::vector as a backing store also gives a slight performance boost
// over the default std::deque.
std::size_t check(Number target, bool singleResult = false) {
Stack<Number> stack;

std::size_t res = 0;
do {
do {
do {
Number value = eval(stack);
if (value == target) {
++res;
std::cout << target << " = " << toString() << "\n";
if (singleResult) {
return res;
}
}
} while (nextOps());
} while (nextValuesPermutation());
} while (nextSelectorPermutation());
return res;
}
};

} // namespace

int main(int argc, const char **argv) {
int i = 1;
bool singleResult = false;
if (argc > 1 && std::string("-s") == argv[1]) {
singleResult = true;
++i;
}
if (argc < i + 2) {
std::cerr << argv[0] << " [-s] <target> <digit>[ <digit>]...\n";
std::exit(1);
}
Number target = std::stoi(argv[i]);
std::vector<Number> values;
while (++i <  argc) {
values.push_back(std::stoi(argv[i]));
}
Evaluator evaluator{values};
std::size_t res = evaluator.check(target, singleResult);
if (!singleResult) {
std::cout << "Number of solutions: " << res << "\n";
}
return 0;
}
6

Ввод, очевидно, представляет собой набор цифр и операторов: D = {1,3,3,6,7,8,3} и Op = {+, -, *, /}. Самый простой алгоритм будет грубая сила решатель, который перечисляет все возможные комбинации этих наборов. Где элементы множества Op могут использоваться так часто, как хотелось бы, но элементы из множества D используются ровно один раз. Псевдокод:

D={1,3,3,6,7,8,3}
Op={+,-,*,/}
Solution=348
for each permutation D_ of D:
for each binary tree T with D_ as its leafs:
for each sequence of operators Op_ from Op with length |D_|-1:
label each inner tree node with operators from Op_
result = compute T using infix traversal
if result==Solution
return T
return nil

Кроме этого: прочитайте ответы jedrus07 и HPM.

5

Я думаю, вам нужно строго определить проблему в первую очередь. Что вам разрешено делать, а что нет. Вы можете начать с простого и умножения, деления, вычитания и сложения.

Теперь вы знаете свое проблемное пространство — набор входов, набор доступных операций и желаемый вход. Если у вас есть только 4 операции и x входов, количество комбинаций меньше чем:

Номер порядка, в котором вы можете выполнять операции (x!), Умноженный на возможные варианты операций на каждом шаге: 4 ^ x. Как видно из 6 номеров, это дает разумные 2949120 операций. Это означает, что это может быть вашим пределом для алгоритма перебора.

Если у вас есть грубая сила, и вы знаете, что это работает, вы можете начать улучшать свой алгоритм с Алгоритм * что потребует от вас определить эвристические функции.

На мой взгляд, лучший способ думать об этом — это проблема поиска. Основной трудностью будет поиск хорошей эвристики или способов уменьшить пространство проблем (если у вас есть числа, которые не суммируют с ответом, вам потребуется хотя бы одно умножение и т. Д.). Начните с малого, постройте это и задавайте дополнительные вопросы, как только у вас появится код.

0

Я нашел отличный алгоритм из Оксфордские документы по информатике (с исходным кодом Java) давно. И я восхищаюсь этим каждый раз, когда читаю это решение. Я верю, что это будет полезно.

-1