Вопрос по оптимизации комбинаторных алгоритмов...

Выбираешь самые большие веса, выбираешь самые большие веса в одном шаге от них и так далее.

Это задача поиска кратчайшего пути в графе. Соответственно, и алгоритмы нужны соответствующие. Они легко гуглятся.

Выбираешь самые большие веса, выбираешь самые большие веса в одном шаге от них и так далее

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

Это задача поиска кратчайшего пути в графе

Просто найти кратчайший путь не проблема. И гуглить не нужно. А вот отсортировать длины путей без миллиардов комбинаций? Но, да, это уже направление, куда можно погуглить, спасибо за мысль.

Просто найти кратчайший путь не проблема.

Затем удалить его и повторить. А модификацией функции сравнения с больше на меньше алгоритм преобразуется в поиск длиннейшего пути в графе.

которые имеют малый вес в начале и высокий в конце.

Так по ним ты пройдешься когда начнёшь с больших числе же.

Наилучшую и наихудшую цепочки найти просто (динамическим программированием). Для предложенного примера ищем оптимальный последний выбор (для простоты игнорируем множественные решения):

ARM->Intel (6)
X86->Intel (9)
MIPS->Toshiba (6)

              | Windows | Linux | Android
ARM->Intel    | 3+6     | 9+6   | 9+6
x86->Intel    | 9+9     | 9+9   | 6+9
MIPS->Toshiba | 3+6     | 3+6   | 6+6

Windows->X86->Intel (18)
Linux->X86->Intel (18)
Android->ARM->Intel (15)

                    | Десктоп    | Смартфон    | Сервер
Windows->X86->Intel | 9+18       | 6+18        | 6+18
Linux->X86->Intel   | 6+18       | 3+18        | 9+18
Android->ARM->Intel | 3+15       | 9+15        | 3+15

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

Так по ним ты пройдешься когда начнёшь с больших числе же.

А, понял. Я думал, ты имеешь в виду взять самые большие веса их первой матрицы, потом к ним самые большие из второй...

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

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

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

Угу, так.

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

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

И в конце будет 2.5 млрд цепочек в памяти :)

сортировать придётся гигабайты данных.
Может быть это как-то можно оптимизировать? :)

Применение метода Монте-Карло для решения детерминированных задач оптимизации ©.

Субоптимальные решения находят довольно быстро.

Нет. На каждом шаге их будет не N, как при поиске оптимума, а NK. Это вполне приемлемо.

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

Вроде задача очень похожа на поиск кратчайшего пути в графе, только граф получается довольно разреженный, кроме кратчайшего надо искать длиннейший (наверное можно довольно просто модифицировать), и не один, а несколько (таких алгоритмов есть уже готовых. Штука называется k shortest paths). Ну и для порядку надо будет добавить стартовую и фишиншную вершины-заглушки, чтобы было от чего до чего считать.

Не нужно хранить все возможные пути, чтобы их сравнивать. Ты же когда ищешь максимальный элемент в массиве, не хранишь в еще одном массиве все уже просмотренные элементы. Достаточно знать, что ты уже отбросил «плохие» варианты. С поиском пути в графе та же фигня. Нет смысла хранить новый путь, если ты уже нашел путь заведомо «лучше». Ну или в твоем случае - если он хуже, чем k лучших.

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

Точки входа и выхода это тупо заглушки с нулевыми ребрами до первой/последней матрицы, чтобы можно было оперировать стандартными алгоритмами поиска пути от А до Б.

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

Могу намаливать мэдскиллз в пеинте, чтобы показать, как оно выглядит.

Но если описать словами, то в каждой матрице имена столбцов это вершины в текущем «слое» графа, имена строк - в следующем «слое», а цыферки в ячейках - длины соответствующих направленных ребер. Перед первой матрицей ставим начальную заглушку, посе последней - конечную. Соответствующие ребра зануляем. Вуаля.

В текущей постановке это достаточно легкая полиномиально-разрешимая задача.

Пусть тебе нужно найти 10 лучших путей. Тогда, если ты знаешь по 10 лучших путей, которые ведут в ARM, x86 и MIPS (всего 30 путей), ты можешь рассчитать по 10 лучших путей в Intel, AMD, Toshiba.

Если это не очень понятно, могу расписать подробнее.

И в конце будет 2.5 млрд цепочек в памяти :)

Тебе правильно подсказывают. K — число лучших путей, которые тебе нужно найти. И памяти тебе нужно всего лишь в K раз больше, чем для простого поиска кратчайшего пути.

Вот наваял

http://storage5.static.itmages.com/i/17/0829/h_1504000203_3373219_62c8108edf.png

Динамическое программирование [/thread]

Держи вот прототип реализации (иногда с загадочными решениями типа выбор K наибольших значений сортировкой):

#!/usr/bin/tclsh

set K 5

set graph {
    {{} {Desktop 0 Smartphone 0 Server 0}}
    {Desktop {Windows 9 Linux 6 Android 3}
     Smartphone {Windows 6 Linux 3 Android 9}
     Server {Windows 6 Linux 9 Android 3}}
    {Windows {ARM 3 x86 9 MIPS 3}
     Linux {ARM 9 x86 9 MIPS 3}
     Android {ARM 9 x86 6 MIPS 6}}
    {ARM {Intel 6 AMD 3 Toshiba 3}
     x86 {Intel 9 AMD 9 Toshiba 3}
     MIPS {Intel 3 AMD 3 Toshiba 6}}
}

proc bestK {graph {K 1}} {
    if {[llength $graph] == 1} {
        return $graph
    } else {
        set start [lrange $graph 0 end-2]
        set end1 [lindex $graph end-1]
        set end [lindex $graph end]
        set res [dict create]
        dict for {key val} $end1 {
            dict for {key1 val1} $val {
                dict for {key2 val2} [dict get $end $key1] {
                    dict lappend res $key [concat $key1 $key2] [expr {$val1+$val2}]
                }
            }
        }
        dict for {key val} $res {
            dict set res $key [lrange [lsort -integer -decreasing -stride 2 -index 1 $val] 0 [expr {2*$K-1}]]
        }
        tailcall bestK [linsert $start end $res] $K
    }
}

puts [bestK $graph $K]

Монте-Карло

В таком случае, лучше сразу генетические алгоритмы, если есть функция кодирования генов и конечного решения.

В таком случае, лучше сразу генетические алгоритмы, если есть функция кодирования генов и конечного решения.

Нет, не лучше. Генетические алгоритмы почти никогда не лучше.

Матричное умножение, только вместо операций «+» и «*» используются операции «max» и «+». Классика.

Если ему нужно 10 наилучших, то не max и +, а

(+++) xs ys = take 10 $ sort $ xs ++ ys

(***) xs ys = take 10 $ sort [ x+y | x <- xs, y <- ys ]

reverse $ sort, я думаю. А так да. Но это уже следующий этап.