c - 二维矩阵遍历——最优路径内存

Question

我有一个函数用于在 2D 矩阵(整数、值和总和的结构)中找到最优路径，但它不会记住最优值，它只会在遍历下来后返回遍历的最小成本到矩阵的底部。我们应该使用堆栈以某种方式记住这些最佳值，但不幸的是我不知道如何做到这一点。它是一种递归算法，因此有点难以分析。值用伪随机数(1 到 10)填充，总和初始化为 INT_MAX。这个好像有点像三叉树。

堆栈函数原型(prototype)是:

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);
}

Answer 1

您可以使用两个堆栈来查找路径。 一个是临时堆栈，另一个是ANSWER堆栈。

基本的想法是，当你移动时，你将你前进的方向插入堆栈。同样在该特定移动的“函数调用()”之后，你 pop() 那个方向.然后，到达底部的步骤，如果满足以下条件:

if(path_cost < *min_cost)
{
  *min_cost = path_cost;
}

您清空 Answer 堆栈，并将 Temporary 堆栈的内容复制到其中。

stack answer ;
stack temporary;

/* 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;
            
            /*
            
            just empyty teh Answer stack here;
            then copy the Temp stack into answer stack
            
            */
            
        }
        return;
    }
    
    // 1 for (row +1 ,col +1 )
    // 2 for (row +1 ,col )
    // 3 for (row +1 ,col -1 )
    
    if (col < MATRIX_COL - 1) // go down and right
    {
        temporary.push(1);
        traverse(matrix, row + 1, col + 1, path_cost, min_cost, cnt, stack, f);
        temporary.pop(1);
    }
    
    temporary.push(2);  
    traverse(matrix, row + 1, col, path_cost, min_cost, cnt, stack, f); // go down
    temporary.pop(2);
    
    if (col > 0) // go down and left
    {
        temporary.push(3);      
       traverse(matrix, row + 1, col - 1, path_cost, min_cost, cnt, stack, f);
       temporary.pop(3);
    }
}

编辑:

来自临时堆栈的 pop() 和 push()。每次找到“潜在”解决方案时，答案堆栈都会更新。此外，我没有时间进行参数传递。临时堆栈“必须”是本地的。根据需要使用答案堆栈。