линейная комбинаторная оптимизация - PullRequest
Новая
       7

линейная комбинаторная оптимизация

1 голос
/ 01 марта 2012

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

Пример проблемы: Для достижения 2a + b при минимальной / максимальной стоимости, объединяющей доступные линейные уравнения 1. 2a + b = 4 2. а = 1 3. a + b = 2 (RHS стоит)

Ответ: Объедините 2 и 3, чтобы получить 2a + b = 3

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

Является ли проблема вариантом проблемы с ранцем? Любые указатели на то, кто это может быть сделано оптимально?

Ответы [ 3 ]

1 голос
/ 15 мая 2012

Эта проблема может быть сформулирована с использованием линейного программирования. Вы можете использовать Gnu Linear Programming Kit (GLPK) и его оболочку Ruby 'rglpk', чтобы решить его.

Загрузите GLPK 4.44 с http://www.gnu.org/software/glpk/ для вашей операционной системы. Разархивируйте пакет и установите приложение, используя следующую команду. 

./configure && sudo make clean && sudo make && sudo make install

Откройте командную строку и установите 'rglpk' с помощью команды ниже. 

gem install rglpk

Запустите этот код. 

require 'rglpk'

#min/max 2a+b
#1. 2a+b=4 
#2. a=1 
#3. a+b=2

p = Rglpk::Problem.new
p.name = "sample"
p.obj.dir = Rglpk::GLP_MAX

rows = p.add_rows(3)
rows[0].name = "2a+b=4"
rows[0].set_bounds(Rglpk::GLP_UP, 0, 4)
rows[1].name = "a=1"
rows[1].set_bounds(Rglpk::GLP_UP, 0, 1)
rows[2].name = "a+b=2"
rows[2].set_bounds(Rglpk::GLP_UP, 0, 2)

cols = p.add_cols(2)
cols[0].name = "a"
cols[0].set_bounds(Rglpk::GLP_LO, 0.0, 0.0)
cols[1].name = "b"
cols[1].set_bounds(Rglpk::GLP_LO, 0.0, 0.0)

p.obj.coefs = [2, 1]

p.set_matrix([
2, 1,
1, 0,
1, 1
])

p.simplex
z = p.obj.get
x1 = cols[0].get_prim
x2 = cols[1].get_prim

printf("z = %g; x1 = %g; x2 = %g\n", z, x1, x2)
#=> z = 3; x1 = 1; x2 = 1
1 голос
/ 01 марта 2012

Это определенно не рюкзак. Это просто проблема линейной оптимизации ( линейное программирование ). Для Ruby вы можете использовать RGLPK

0 голосов
/ 01 марта 2012

Если я правильно понимаю проблему, она является вариантом проблемы с ранцем.В каждой коробке есть яблоки и бананы.Это также имеет стоимость.Вы должны выбрать несколько ящиков, чтобы получить определенное количество яблок и бананов, минимизируя общую стоимость.

Я бы использовал алгоритм DP Knapsack с 2D-кешем вместо 1D-кеша: кеш [5] [10] - это сколько стоит получить 5 яблок и 10 бананов.

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

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

...