найти оптимизированный по стоимости путь через сетку / матрицу в C ++

Question

Я застрял с проблемой и не мог найти много помощи онлайн.Мне нужно найти минимальную стоимость комбинации чисел из нескольких векторов чисел.Размер вектора одинаков для всех векторов.Например, рассмотрим следующее:

row [0]:  a  b  c  d   
row [1]:  e  f  g  h  
row [2]:  i  j  k  l  

Теперь мне нужно найти комбинацию чисел, взяв один элемент из каждой строки, т.е. вектор, например: aei
После этого мне нужно найти три другихкомбинации, которые не пересекаются друг с другом, например: bfj, cgk, dhl.Я рассчитываю стоимость на основе этих четырех выбранных комбинаций.Цель состоит в том, чтобы найти комбинацию, которая дает минимальную стоимость.Другая возможная комбинация может быть: afj, bei, chk, dgl.Если общее количество столбцов равно d, а строк равно k, возможная общая комбинация равна d ^ k.Строки хранятся в виде векторов.Я застрял здесь, мне трудно написать алгоритм для вышеуказанного процесса.Буду очень признателен, если кто-нибудь сможет помочь.
Спасибо.

// I am still working on the algorithm. I just have the vectors and the cost function.  

//Cost Function  , it also depends on the path chosen
float cost(int a, int b, PATH to_a) {  
float costValue;  
...  
...  
return costValue;  
}  

vector< vector < int > > row;  
//populate row  
...   
...
//Suppose  

//    row [0]:  a  b  c  d   
//    row [1]:  e  f  g  h  
//    row [2]:  i  j  k  l   

// If a is chosen from row[0] and e is chosen from row[1] then,  
float subCost1 = cost(a,e, path_to_a);  

// If i is chosen from row[2] ,  
float subCost2 = cost(e,i,path_to_e);  

// Cost for selecting aei combination is  
float cost1 = subCost1 + subCost2;  

//similarly other three costs need to be calculated by selecting other remaining elements  
//The elements should not intersect with each other eg. combinations aei and bej cannot exist on the same set.  

//Suppose the other combinations chosen are bfj with cost cost2, cgk with cost cost3   and dhl with cost cost4  
float totalCost = cost1 + cost2 + cost3 + cost4;   

//This is the cost got from one combination. All the other possible combinations should be enumerated to get the minimum cost combination. 

Answer 1

Отправка большего количества кода утилиты

см. Github: https://gist.github.com/1233012#file_new.cpp

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

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

Pro:

• намного быстрее
  • более умный алгоритм (использует STL и математика :))
  • оптимизация инструкций
  • оптимизация хранения
• универсальная модель задачи
• модель и алгоритмические идеи могут использоваться в качестве основы для правильного алгоритма
• основа для хорошего распараллеливания OpenMP ( n way, для n строк), предназначенная (но не выделенная)

Против:

• Код гораздо эффективнее за счетГибкость: адаптация кода для построения логики об ограничениях и эвристике затрат была бы намного проще с более пошаговым подходом Python

В целом, я чувствую, что мой код C ++ может быть большой выигрыш IFF оказывается, что имитированный отжиг подходит с учетом функции стоимости;Подход, использованный в коде, даст

• высокоэффективную модель хранения
• высокоэффективный способ генерации случайных / тесно связанных новых конфигураций сетки
• удобные функции отображения

---

Обязательная (произвольная ...) контрольная точка данных (сравнение с версией Python:)

  a  b  c  d e
  f  g  h  i j
  k  l  m  n o
  p  q  r  s t

Result: 207360000

real  0m13.016s
user  0m13.000s
sys   0m0.010s

Здесьчто мы получили до сих пор:

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

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

• Дополнительным ограничением является то, что последующие узлы должны быть взяты из следующего rank (ad, да, il является тремя ranks ; после посещения узла из последнего rank путь должен продолжаться с любого не посещенного узла из первого rank

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

В свете этого я полагаю, что мы находимся в области проблем с «полным покрытием» (требуется алгоритм A *, наиболее известный из статьи Knuths Dancing Links).

Конкретно Без дополнительной информации (эквивалентность путей, конкретные свойства функции стоимости) наилучшим известным алгоритмом для получения «самого дешевого» гамильтонова пути, который удовлетворяет ограничениям, будет

• generate все возможностиible такие пути
• вычисляют функцию фактической стоимости для каждого
• выбирают путь минимальной стоимости

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

Конец Вселенной

Выход для сетки выборки 3 × 4 равен 4! ³ = 13824 возможных путей ... Экстраполируя это на 6 × 48 столбцов, можно получить 6! ⁴⁸ = 1,4 × 10 ¹³⁷ возможностей.Очень ясно , что без дальнейшей оптимизации проблема не поддается решению (NP Hard или что-то - я никогда не помню довольно тонкие определения).

Взрыв времени выполненияоглушает:

• 3 × 4 (измерено) занимает около 0,175 с
• 4 × 5 (измерено) заняло около 6 м5 с (работает без выхода и под PyPy 1.6 на быстрой машине)
• 5 × 6 заняло бы примерно 10 лет и 9+ месяцев ...

В 48x6 мы будем смотреть на ... что ... 8,3x10 ¹⁰⁷ lightyears (прочитайте внимательно)

Посмотрите вживую: http://ideone.com/YsVRE

В любом случае, вот код Python (все предустановлены для сетки 2 × 3)

#!/usr/bin/python
ROWS = 2
COLS = 3

## different cell representations
def cell(r,c): 
    ## exercise for the reader: _gues_ which of the following is the fastest
    ## ...
    ## then profile it :)
    index = COLS*(r) + c
    # return [ r,c ]
    # return ( r,c )
    # return index
    # return "(%i,%i)" % (r,c)

    def baseN(num,b,numerals="abcdefghijklmnopqrstuvwxyz"):
        return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

    return baseN(index, 26)

ORIGIN = cell(0,0)

def debug(t): pass; #print t
def dump(grid): print("\n".join(map(str, grid)))

def print_path(path):
    ## Note: to 'normalize' to start at (1,1) node:
    # while ORIGIN != path[0]: path = path[1:] + path[:1] 
    print " -> ".join(map(str, path))

def bruteforce_hamiltonians(grid, whenfound):
    def inner(grid, whenfound, partial):

        cols = len(grid[-1]) # number of columns remaining in last rank
        if cols<1:
            # assert 1 == len(set([ len(r) for r in grid ])) # for debug only
            whenfound(partial)                             # disable when benchmarking
            pass
        else:
            #debug(" ------ cols: %i ------- " % cols)

            for i,rank in enumerate(grid):
                if len(rank)<cols: continue
                #debug("debug: %i, %s (partial: %s%s)" % (i,rank, "... " if len(partial)>3 else "", partial[-3:]))
                for ci,cell in enumerate(rank):
                    partial.append(cell)
                    grid[i] = rank[:ci]+rank[ci+1:] # modify grid in-place, keeps rank

                    inner(grid, whenfound, partial)

                    grid[i] = rank # restore in-place
                    partial.pop()
                break
        pass
    # start of recursion
    inner(grid, whenfound, [])

grid = [ [ cell(c,r) for r in range(COLS) ] for c in range(ROWS) ]

dump(grid)

bruteforce_hamiltonians(grid, print_path)

Answer 2

Во-первых, одно наблюдение, которое очень мало помогает.

Я думаю, что результат 4! ^ 3 не отражает тот факт, что {aei, bfj, cgk, dhl} и (например) {bfj, aei, cgk, dhl} имеют то же самое стоимость.

Это означает, что нам нужно рассматривать только последовательности вида

{ a??, b??, c??, d?? }

Эта эквивалентность сокращает число отдельных случаев на 4!

С другой стороны@sehe имеет 3x4, дает 4! ^ 3 (я согласен), поэтому 6x48 также требует 48! ^ 6 .Из этих «только» 48! ^ 5 отличаются.Теперь это 2.95 × 10 ^ 305.

На примере 3x4 приведен алгоритм, который дает своего рода ответ.

Enumerate all the triplets and their costs. 
Pick the lowest cost triplet.
Remove all remaining triplets containing a letter from that triplet.
Now find the lowest cost triplet remaining.
And so on.

Обратите внимание, что не полный исчерпывающий поиск.

Я также вижу из этого, что это все еще много вычислений.Этот первый проход все еще требует 48 ^ 6 (12,230, 590, 464) затрат для расчета.Я думаю, что это можно сделать, но потребует много усилий.Последующие проходы будут дешевыми в сравнении.

Answer 3

РЕДАКТИРОВАТЬ: ДОБАВЛЕНО ПОЛНОЕ РЕШЕНИЕ

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

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

Я создал шаблонную функцию, поэтому вам нужно просто предоставить необходимые функциональные объекты и структуру.

#include <iostream>
#include <cmath>
#include <ctime>
#include <vector>
#include <algorithm>
#include <functional>

//row [0]:  c00  c01  c02  c03   
//row [1]:  c10  c11  c12  c13  
//row [2]:  c20  c21  c22  c23 


typedef std::pair<int,int> RowColIndex;
// the deeper vector has size 3 (aei for example)
// the outer vector has size 4
typedef std::vector<std::vector<RowColIndex> > Matrix;

size_t getRandomNumber(size_t up)
{
    return rand() % up;
}

struct Configuration
{
    Configuration(const Matrix& matrix) : matrix_(matrix){}
    Matrix matrix_;
};

std::ostream& operator<<(std::ostream& os,const Configuration& toPrint)
{
    for (size_t row = 0; row < toPrint.matrix_.at(0).size(); row++)
    {
        for (size_t col = 0; col < toPrint.matrix_.size(); col++)
        {
            os << toPrint.matrix_.at(col).at(row).first  << "," 
               << toPrint.matrix_.at(col).at(row).second << '\t';
        }
        os << '\n';
    }   
    return os;
}

struct Energy 
{ 
    double operator()(const Configuration& conf)
    {
        double result = 0;
        for (size_t col = 0; col < conf.matrix_.size(); col++)
        {
            for (size_t row =0; row < conf.matrix_.at(col).size(); row++)
            {
                result += pow(static_cast<double>(row) - static_cast<double>(conf.matrix_.at(col).at(row).first),2) +
                          pow(static_cast<double>(col) - static_cast<double>(conf.matrix_.at(col).at(row).second),2);
            }
        }
        return result;
    }
};

size_t calculateNewColumn(std::vector<int>& isAlreadyUse)
{
    size_t random;
    do
    {
        random = getRandomNumber(isAlreadyUse.size());
    }
    while (isAlreadyUse.at(random) != 0);

    isAlreadyUse.at(random) = 1;
    return random;
}

Configuration createConfiguration(size_t numberOfRow,size_t numberOfColumn)
{
    //create suitable matrix
    Matrix matrix;
    //add empty column vector
    for (size_t col = 0; col < numberOfColumn; col++)
        matrix.push_back(std::vector<RowColIndex>());

    //loop over all the element
    for (size_t row = 0; row < numberOfRow; row++)
    {
        std::vector<int> isAlreadyUse(numberOfColumn);
        for (size_t col = 0; col < numberOfColumn; col++)
        {
            size_t newCol = calculateNewColumn(isAlreadyUse);
            matrix.at(newCol).push_back(std::make_pair(row,col));
        }
    }   

    return Configuration(matrix);
}


struct CreateNewConfiguration
{
    Configuration operator()(const Configuration& conf)
    {
        Configuration result(conf);

        size_t fromRow = getRandomNumber(result.matrix_.at(0).size());

        size_t fromCol = getRandomNumber(result.matrix_.size());
        size_t toCol = getRandomNumber(result.matrix_.size());

        result.matrix_.at(fromCol).at(fromRow) = conf.matrix_.at(toCol).at(fromRow);
        result.matrix_.at(toCol).at(fromRow) = conf.matrix_.at(fromCol).at(fromRow);

        return result;
    }
};

template<typename Conf,typename CalcEnergy,typename CreateRandomConf>
Conf Annealing(const Conf& start,CalcEnergy energy,CreateRandomConf createNewConfiguration,
               int maxIter = 100000,double minimumEnergy = 1.0e-005)
{
    Conf first(start);
    int iter = 0;
    while (iter < maxIter && energy(first) > minimumEnergy )
    {
        Configuration newConf(createNewConfiguration(first));
        if( energy(first) > energy(newConf))
        {
            first = newConf;
        }
        iter++;
    }
    return first;
}

int main(int argc,char* argv[])
{

    size_t nRows = 25;
    size_t nCols = 25;
    std::vector<Configuration> res;
    for (int i =0; i < 10; i++)
    {
        std::cout << "Configuration #" << i << std::endl;
        Configuration c = createConfiguration(nRows,nCols);
        res.push_back(Annealing(c,Energy(),CreateNewConfiguration()));
    }

    std::vector<Configuration>::iterator it = res.begin();


    std::vector<Configuration>::iterator lowest = it;
    while (++it != res.end())
    {
        if (Energy()(*it) < Energy()(*lowest))
            lowest = it;
    }

    std::cout << Energy()(*lowest) << std::endl;

    std::cout << std::endl;

    std::cout << *lowest << std::endl;


    std::cin.get();
    return 0;
}

Конечно, у вас нет гарантии, что решение является лучшим (это эвристический метод). Однако это хорошая отправная точка.

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

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

Сложность

Сложность алгоритма составляет E * I * C, где I = количество итераций C = номер случайной конфигурации (чтобы избежать локального минимума) E = расчет функции энергии (или стоимости функции)

В этом случае E фактически является N * M, где N и M - размеры исходной матрицы.

Если вас не устраивает результат имитации отжига, вы можете попробовать генетических алгоритмов .

Answer 4

Вы можете решить проблему рекурсивно.

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

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

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

Когда поток вернется к первому вектору, вы можете объединить результат в качестве окончательного.

Answer 5

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