Может кто-нибудь помочь с возможным алгоритмом динамического программирования

Question

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

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

54 47 33 58 46 38 48 37 56 52 61 25 ……………… сначаланабор
54 52 33 61 38 58 37 25 48 56 47 46 ……………… второй набор

В этом примере Считывание слева направо чисел 54 52 61 и 25 происходит в обоих наборах втот же порядок.
Таким образом, другими возможными решениями будут…

54 52 61 25
54 33 58 46
54 33 46
54 33 38 48 56
54 4856 ....И т.д.

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

Я понимаю базовую структуру c ++ и виртуальных базовых программ и должен уметь что-то объединять в эфире, но, честно говоря, ясо времен спектра zx не занимался сколько-нибудь серьезным программированием, поэтому, пожалуйста, будьте осторожны со мной.Однако моя главная проблема не в самом языке программы, а в том, что по какой-то причине я считаю невозможным каталогизировать шаги, необходимые для выполнения этой задачи на английском языке, не говоря уже о любом другом языке.

Дарси

Answer 1

Звучит так, будто вы ищете «все общие подпоследовательности (ACS)», что является двоюродным братом (более распространенной) самой длинной проблемы общих подпоследовательностей (LCS) .

Вот статья , в которой обсуждается ACS (хотя они сосредоточены только на подсчете подпоследовательностей, а не на перечислении).

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

1) Применить алгоритм DP для LCS, генерируя матрицу выравнивания / возврата назад

2) Возвратите все возможные LCS, отмечая посещенные позиции выравнивания.

3) Выберите самый большой элемент матрицы, который еще не отмечен (самая длинная оставшаяся подпоследовательность)

4) Возврат, запись последовательности и маркировка посещенных позиций выравнивания.

5) Пока существуют неотмеченные позиции выравнивания, перейдите к (3)

Возврат в вашем случае сложен, потому что вам придется посещать все возможные пути (называемые «все самые длинные общие подпоследовательности»). Вы можете найти примеры реализаций LCS здесь , которые могут помочь вам начать работу.

Answer 2

Я написал этот код, и он выводит самую длинную общую последовательность.Это не супероптимизировано, однако, порядок: O (n * m) n-> размер массива1, м-> размер массива:

private void start() {
    int []a = {54, 47, 33, 58, 46, 38, 48, 37, 56, 52, 61, 25};
    int []b = {54, 52, 33, 61, 38, 58, 37, 25, 48, 56, 47, 46};

    System.out.println(search(a,b));
}

private String search(int[] a, int[] b)
{
    return search(a, b, 0, 0).toString();       
}

private Vector<Integer> search(int[] a, int[] b, int s1, int s2) {

    Vector<Vector<Integer>> v = new Vector<Vector<Integer>>(); 

    for ( int i = s1; i < a.length; i++ )
    {
        int newS2 = find(b, a[i], s2);
        if ( newS2 != -1 )
        {
            Vector<Integer> temp = new Vector<Integer>();
            temp.add(a[i]);
            Vector<Integer> others = search(a, b, i+1, newS2 + 1); 
            for ( int k = 0; k < others.size(); k++)
                temp.add( others.get(k));
            v.add(temp);
        }
    }

    int maxSize = 0;
    Vector<Integer> ret = new Vector<Integer>();
    for ( int i = 0; i < v.size(); i++)
        if ( v.get(i).size() > maxSize )
        {
            maxSize = v.get(i).size(); 
            ret = v.get(i);
        }

    return ret;
}

private int find(int[] b, int elemToFind, int s2) {
    for ( int j = s2; j < b.length; j++)
        if ( b[j] == elemToFind)
            return j;
    return -1;
}