1

2Dマトリックス（整数、値、合計の構造）で最適なパスを見つけるために使用される関数がありますが、最適な値を記憶せず、最下部に到達するとトラバーサルの最小コストのみを返しますマトリックスの。スタックを使用してこれらの最適値を何らかの方法で記憶することになっていますが、残念ながらその方法はわかりません。これは再帰的なアルゴリズムであるため、分析が少し難しくなります。値は疑似乱数 (1 から 10) で埋められ、合計は に初期化されINT_MAXます。これは、三分木に少し似ているようです。

スタック関数のプロトタイプは次のとおりです。

stack_t stack_new(); // already done in main
void stack_delete(stack_t stack); // -||-
void stack_push(stack_t stack, stack_element_t elem);
stack_element_t stack_pop(stack_t stack);
stack_element_t stack_top(stack_t stack);
int stack_is_empty(stack_t stack);

/* recursively seeks the optimal path in a 2D matrix */

void traverse(struct path **matrix, unsigned row, unsigned col, int path_cost, int *min_cost, int *cnt, stack_t stack, FILE *f)
{
    char buffer[16];
    path_cost += matrix[row][col].value;
    matrix[row][col].sum = path_cost;
    (*cnt)++; // counting calls
    fprintf(f, "call_counter: %d, min_cost: %s, path_cost: %d, value: %d, sum: %d\n", *cnt, *min_cost == INT_MAX ? "Inf" : itoa(*min_cost, buffer, 10), path_cost, matrix[row][col].value, matrix[row][col].sum); // logging
    if(matrix[row][col].sum > *min_cost) // if we've been here before and it wasn't as costly, return
    {
        return;
    }
    if(row == MATRIX_ROW - 1) // if we're at the bottom of the matrix
    {
        if(path_cost < *min_cost)
        {
            *min_cost = path_cost;
        }
        return;
    }
    if (col < MATRIX_COL - 1) // go down and right
        traverse(matrix, row + 1, col + 1, path_cost, min_cost, cnt, stack, f);

    traverse(matrix, row + 1, col, path_cost, min_cost, cnt, stack, f); // go down

    if (col > 0) // go down and left
        traverse(matrix, row + 1, col - 1, path_cost, min_cost, cnt, stack, f);
}
4

1 に答える 1