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

Запутал? Вот ответы для приведённой матрицы:



Нужен алгоритм.

если

последовательность строк, то

- строка,
а

- ее элемент, т.е. он не число, а набор чисел
как такие элементы сравниваются друг с другом?

Давай, попроще.
Есть список вида:
Надо найти самые длинные последовательности элементов, таких, что a[i+1]<a[i].
Ответ:Другие варианты короче, а эти самые длинные.

Вот нужен алгоритм.

хм... вроде помню такую тему на форуме, а не нашел
в общем, схема обычная - динамическое программирование
создаем еще один массив L такой же длины из целых чисел
в i-ю ячейку пишем максимальную длину возрастающей подпоследовательности, которая заканчивается на i-м числе
как это делается:
для чисел, перед которыми нет меньших чисел, просто пишем 1
если есть - выбираем из предшествующих меньших чисел то, для которого L[j]=max и добавляем к нему 1
пример:
a=10, 1, 5, 3, 9, 4
L[0]=1//перед ним вообще нету чисел
L[1]=1//10 не меньше, потому не подходит
L[2]=L[1]+1=2
L[3]=L[1]+1=2
L[4]=L[2]+1=L[3]+1=3 (оба варианта подходят)
L[5]=L[3]+1=3

в конце просто выбираем максимальное значение из L[i]
чтобы упростить поиск самой последовательности (а не только ее длины), можно сделать еще один массив, в котором для каждого элемента записывать, какой элемент в оптимальной последовательности ему предшествует...

Теперь я хммм.. буду разбираться.
Вот бы пример на каком-нибудь языке программирования вроде Pascal, C, или вообще, не важно на каком.
Добавлено @ 15:27
Я вообще думал, получаются деревья "кто кого меньше", и как-то с учётом последовательности. Потом происходит поиск самых длинных путей в деревьях, а потом опять возвращаемся к той же задаче, но уже с меньшим количество членов в списке и так, пока не дойдём до точки.

Пример хочется.

Это сообщение отредактировал(а) tishaishii - 5.3.2006, 15:50

ну, например, так:


Это сообщение отредактировал(а) maxim1000 - 5.3.2006, 16:00

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

а почему он быстрее - вот ответ:
наше дерево будет необычным - в одну и ту же вершину можно будет добраться несколькими путями
теперь посмотрим, к чему это приведет:
возьмем такой пример
a=10, 2, 6, 1, 5, 3, 9, 4, 6, 7
и посмотрим, какие подпоследовательности есть вообще:
2,5,9
2,5,6,7
2,5,7
1,5,9
1,5,6,7
1,5,7
5,9
5,6,7
5,7
(для примера я выделил только те, которые содержат 5)
можно все их просмотреть и найти самую длинную - по сути, к этому и сводится рекурсивный способ
если мы начнем просматривать последовательности вручную, мы заметим некоторую повторяемость:
слева от 5-ки может стоять 1,2 или пусто
справа от5-ки может стоять 9, 6-7 или 7
они комбинируются всеми возможными способами (т.е. 3*3=9 способов)
и длина последовательности может быть посчитана как (длина левой части)+1+(длина правой части)
т.е. левая часть и правая абсолютно независимы и максимумы можно искать независимо
в некотором приближении это называется свойством марковости (от процессов Маркова)
обычно, это свойство создает хорошие возможности для оптимизации
в нашем случае вместо того, чтобы перебирать 3*3 вариантов можно пойти другим путем:
сначала возьмем самую длинную девую часть (переберем 3 варианта и получим, например, 2)
потом - самую длинную правую часть - тоже 3 варианта - 6,7
а потом просто соединим все это: 2,5,6,7
(именно на этом и построен алгоритм, приведенный выше - до каждого элемента считаем без забегания вперед - т.е. оптимальную левую часть)
что мы получили - вместо 9 вариантов 6
если бы было по 10 вариантов левой и правой частей, получили бы 20 переборов вместо 100
в общем, сделали декомпозицию задач, когда вместо того, чтобы перемножаться сложности складываются, что получается иногда НАМНОГО быстрее...

Ошибка между 29 и 30й строкой в листинге.
Вообще-то мне нужно найти все максимально-длинные последовательности.
А некоторые я могу найти и так:
Но вот интересно найти все (для моего примера их 3).

Вот примерно чего я хотел-то этим добиться:


Вывод:

Ну ещё надо оптимизировать, но цель уже почти достигнута.
Добавлено @ 23:13
Я раньше пытался пользоваться для этих целей алгоритмом LCS, но сумел его приладить только для работы с 2мя строками. Пришлось придумать свой алгоритм.
Добавлено @ 23:15
Вот этот алгоритм (вложение).

Теперь ещё надо выводить все наиболее точные регвыры, а для этого надо найти все наиболее длинные те последовательности, которые мы обсуждаем.

Это сообщение отредактировал(а) tishaishii - 5.3.2006, 23:16

Присоединённый файл ( Кол-во скачиваний: 0 )
 ________.zip 7,18 Kb

ну так это совсем несложно:
упраздняем массив from (в принципе, можно было бы сделать его массивом массивов, но можно и без этого)
а дальше выводим так (функция принимает на вход массив L, который был вычислен):


а вот с Perl'ом у меня, к сожалению, проблемы

1. Видимо здесь a[i+1]<a[i] имеется ввиду a[i+1]>a[i].
2.Лирическое отступление:
Это я к тому, что в этом примере возрастающая последовательность это:
и т.е. последовательность подряд идущих по возрастанию элементов. Короче, нужно разобраться.

Из учебника по мат.анализу
И ещё добавлю, что в такой последовательности должно быть более одного элемента.

Прошу, не надо запутывать.

tishaishii, я хочу тебе помочь, а ты мне рот затыкаешь. Посмотри ещё раз на свой пример:
a[i+1]<a[i] - это значит, что каждый последующий элемент меньше текущего, а в твоём ответе всё наоборот. То же касается и этого. Говоришь, что a[i+1]<a[i], т.е. каждый последующий элемент , а сам прыгаешь через один.

Так кто из нас запутывает?