Минимизация суммы специальной функции над списком

Question

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

Например, рассмотрим список { 1, 2, 3, 4 } и сумму a^b для последовательных пар (a,b) по всему списку. то есть. 1^2 + 2^3 + 3^4 = 90. При проверке минимальная сумма достигается, когда список имеет вид { 2, 3, 1, 4 } => (2^3 + 3^1 + 1^4 = 12).

Обратите внимание, что сумма не циклична (т. Е. Я не считаю last^first), и важен порядок (2^3 != 3^2), а также a^b может быть любой функцией, работающей с любым числом последовательных элементов.

Существует ли название для такого алгоритма и существуют ли способы его реализации?

РЕДАКТИРОВАТЬ: Я перефразировал вопрос, так как я неправильно обозначил это как проблему сортировки. Как уже отмечалось, это скорее проблема оптимизации.

Answer 1

«Сортировка» обычно определяется с помощью бинарного оператора сравнения («меньше или равно»). То, что вы ищете, это «лучшая» перестановка списка, где «лучшая» определяется как критерий, который определяется для всего списка (в то время как «определенная функция» определяется для соседних элементов, сумма для всего списка делает его глобальным свойством).

Если я правильно понимаю, «коммивояжер» - это пример вашей проблемы, так что ваша проблема в любом случае NP-полная; -)

Answer 2

Поскольку нет ограничений на используемую функцию

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

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

Так что я не вижу ничего быстрее, чем вычисление функции и суммы для всех перестановок.

(Вы можете запоминать результаты для каждого кортежа, чтобы ускорить оценку, но я думаю, что вам все равно нужно просмотреть их все)

РЕДАКТИРОВАТЬ: Кроме того, поскольку это может быть функция, действующая на все элементы, у вас может быть функция, которая возвращает 0 для всех перестановок, кроме одной, для которой она возвращает 1.

Так что для общего случая вам определенно потребуется оценить функцию для всех перестановок.

Answer 3

Я вижу только одно решение:

перебор

    public static int Calculate(Func<int, int, int> f, IList<int> l)
    {
        int sum = 0;
        for (int i = 0; i < l.Count-1; i++)
        {
            sum += f(l[i], l[i + 1]);
        }
        return sum;
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list, int count)
    {
        if (count == 0)
        {
            yield return new T[0];
        }
        else
        {
            int startingElementIndex = 0;
            foreach (T startingElement in list)
            {
                IEnumerable<T> remainingItems = AllExcept(list, startingElementIndex);

                foreach (IEnumerable<T> permutationOfRemainder in Permute(remainingItems, count - 1))
                {
                    yield return Concat<T>(
                        new T[] { startingElement },
                        permutationOfRemainder);
                }
                startingElementIndex += 1;
            }
        }
    }

    // Enumerates over contents of both lists.
    public static IEnumerable<T> Concat<T>(IEnumerable<T> a, IEnumerable<T> b)
    {
        foreach (T item in a) { yield return item; }
        foreach (T item in b) { yield return item; }
    }

    // Enumerates over all items in the input, skipping over the item
    // with the specified offset.
    public static IEnumerable<T> AllExcept<T>(IEnumerable<T> input, int indexToSkip)
    {
        int index = 0;
        foreach (T item in input)
        {
            if (index != indexToSkip) yield return item;
            index += 1;
        }
    }

    public static void Main(string[] args)
    {
        List<int> result = null;
        int min = Int32.MaxValue;
        foreach (var p in Permute<int>(new List<int>() { 1, 2, 3, 4 }, 4))
        {
            int sum = Calculate((a, b) => (int)Math.Pow(a, b), new List<int>(p));
            if (sum < min)
            {
                min = sum;
                result = new List<int>(p);
            }
        }
        // print list
        foreach (var item in result)
        {
            Console.Write(item);
        }
    }

Я украл код перестановки из Ian Griffiths blog .

Answer 4

Это домашнее задание?

Если нет, то это проблема динамического программирования. Чтобы увидеть это, вы должны преобразовать свою проблему в следующую, используя ваш пример в качестве основы. Вы в начале. Вы можете выбрать один из {1,2,3,4}. Оттуда вы можете перейти к {1,2,3,4}. Сделайте это 4 раза, и у вас будет все расположение длины 4 списка {1,2,3,4}.

Теперь вам нужна функция стоимости, которая определяется как:

f(prev, next) = prev ^ next
              = 0 if the solution is not valid for your original problem 
              = 0 if prev is the start

Общая стоимость выражена как

cost(i|a|X) = min(i in {1,2,3,4}, f(i, a) + cost(X))

обратите внимание, что i|a|X представляет список, начинающийся с элемента a, а затем i, а остальная часть списка - X.

Глядя на функцию cost, вы должны распознать динамическое программирование.

Оттуда вы можете получить алгоритм. Посмотрите в википедии введение в динамическое программирование .

Реализация моей схемы, которую вы можете протестировать с помощью схемы PLT:

(define (cost lst f)
  (if (null? lst)
      0
      (let ((h (car lst))
            (t (cdr lst)))
        (if (null? t)
            0
            (+ (f h (car t))
               (cost t f))))))

(define (solve lst f)
  (let loop ((s '()))
    (if (= (length s) (length lst))
        s
        (loop
         (let choose ((candidate lst)
                      (optimal #f)
                      (optimal-cost #f))
           (if (null? candidate)
               optimal
               (let ((c (car candidate)))
                 (if (memq c s)
                     (choose (cdr candidate) optimal optimal-cost)
                     (if (not optimal) 
                         (choose (cdr candidate) (cons c s) (cost (cons c s) f))
                         (if (<= (cost (cons c s) f)
                                 (cost optimal f))
                             (choose (cdr candidate) (cons c s) (cost (cons c s) f))
                             (choose (cdr candidate) optimal optimal-cost)))))))))))

Тогда вызов (solve '(1 2 3 4) expt) дает другое минимальное решение '(3 2 1 4).

Answer 5

Кажется, что это Оптимизация Probelm , а не проблема сортировки.

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

Answer 6

Эта проблема является полной проблемой NP, поскольку алгоритм неизвестен (обратите внимание, что для данной функции a ^ b это не NP Complete, это можно сделать за один проход после сортировки, см. Пример ниже для решения)

Невозможно заранее написать общий алгоритм "алгоритма сортировки" без вычисления результатов данной функции для всех возможных перестановок списка.

Однако, получив функцию, вы можете (возможно) разработать метод сортировки для этого, например. для a ^ b выше упорядочите список таким образом (без применения функции к каким-либо элементам): «Макс, мин, следующий макс, следующий мин. , . »И обратный порядок.

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

Спасибо

Answer 7

Это определенно не отсортированный список. Если у вас есть отсортированный список [x ~ 0 ~ ... x ~ n ~], список [x ~ 0 ~ ..x ~ i-1 ~, x ~ i + 1 ~ ..x ~ n ~] (т.е. x ~ i ~ удалено) по определению также будут отсортированы. В вашем примере удаление 0 из подпоследовательности 100,0,100 вполне могло бы привести к несортировке списка.

Answer 8

Это то, что я имею до сих пор. Я создал класс Calc, в который я могу передать каждую из своих комбинаций, затем он вычисляет сумму и имеет метод ToString (), поэтому вам не нужно беспокоиться об итерациях для вывода строки и значения суммы. Вы можете получить общее количество и список, переданный в конструкторе. Затем вы можете просто добавить каждый из ваших наборов комбинаций в список, который вы можете отсортировать по LINQ в inst .Total ..., как я продемонстрировал. Все еще работаем над средством генерации каждой комбинации ...

class Calc
{
    private int[] items;
    private double total;
    public double Total 
    { 
        get
        { 
            return total; 
        } 
    }
    public int[] Items
    {
        get { return items;  }
        set { total = Calculate(value); }
    }
    public static double Calculate(int[] n)
    {
        double t = 0;
        for (int i = 0; i < n.Length - 1; i++)
        {
            int a = n[i]; int b = n[i + 1];
            t += a^b;
        }
        return t;
    }
    public Calc(int[] n)
    {
        this.items = n;
        this.total = Calculate(n);
    }
    public override string ToString()
    {
        var s = String.Empty;
        for (int i = 0; i < items.Length - 1; i++)
        {
            int a = items[i]; int b = items[i + 1];
            s += String.Format("{0}^{1}", a, b);
            s += i < items.Length - 2 ? "+" : "=";
        }
        s += total;
        return s;
    }
}

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

class Program
{
    static void Main(string[] args)
    {
        var Calculations = new List<Calc>();

        ////Add a new item to totals for every combination of...working on this
        Calculations.Add(new Calc(new int[] { 1, 2, 3, 4 }));
        //...

        //Grab the item with the lowest total... if we wanted the highest, we'd
        //just change .First() to .Last()
        var item = Calculations.OrderBy(i=>i.Total).First();
        Console.WriteLine(item);
        //Or if we wanted all of them:
        //Calculations.OrderBy(i=>i.Total).ForEach(Console.WriteLine);
    }
}

Answer 9

не проверено и недоказано:

1. Сортировка списка
2. Создание пар из отсортированного списка, захват первого и последнего числа, затем 2-го и 2-го числа до последнего и т. Д. (Т. Е. 1,2,3,4 становится 1,4 и 2,3)
3. Для каждой пары сохраните значение ^ b. Обратный сортировать этот список
4. Замените значения a ^ b в вашем новом списке значениями a & b

Полагаю, все не так просто ... но это работает для вашего примера, и разве это не имеет значения?

Answer 10

Хм, это интересная проблема. Использование существующих сортирующих конструкций (IComparable) не будет работать хорошо, потому что вам нужно больше информации, чем доступно для метода CompareTo.

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

Мне нужно сделать попытку и посмотреть, что я могу придумать.