Как извлечь сложность алгоритма на основе динамического программирования и турагента? - PullRequest
Новая
       89

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

0 голосов
/ 25 октября 2018

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

do{

    this.addNodeToList(actual, cost);

    this.sortArray();

    Node node = this.arrayElements.get(0);

    roads.add(node.getNode());

    actual = node.getNode();

    totalCost += node.getPese();

    arrayElements.clear();
    x++;

}while(actual != begin);

Переменная actual является узлом, где программа остановлена, иоценивает своих соседей, переменная begin является началом маршрута, begin инициализируется в 0, алгоритм начинается с конца, то есть с graph.length-1

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

Это правда?Даже на него также могут повлиять лучший случай, средний случай и наихудший случай из всех, но я не могу придумать, как их получить.

Определение графика затрат выглядит следующим образом:

private static final int graph[][] = {
        {0, 85, 52, 45, 0, 0, 0, 0, 0, 0, 0, 0},
        {85, 0, 0, 0, 18, 0, 0, 0, 0, 0, 0, 0},
        {52, 0, 0, 0, 45, 28, 0, 0, 0, 0, 0, 0},
        {45, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0},
        {0, 18, 45, 0, 0, 0, 15, 19, 0, 0, 0, 0},
        {0, 0, 28, 15, 0, 0, 30, 15, 0, 0, 0, 0},
        {0, 0, 0, 0, 15, 30, 0, 0, 43, 23, 0, 0},
        {0, 0, 0, 0, 19, 15, 0, 0, 0, 13, 35, 0},
        {0, 0, 0, 0, 0, 0, 43, 0, 0, 0, 0, 40},
        {0, 0, 0, 0, 0, 0, 23, 13, 0, 0, 0, 25},
        {0, 0, 0, 0, 0, 0, 0, 35, 0, 0, 0, 45},
        {0, 0, 0, 0, 0, 0, 0, 0, 40, 25, 45, 0}};
...