2D矩阵遍历-最优路径记忆
2D矩阵遍历-最优路径记忆
提问于 2013-06-01 02:29:49
我有一个函数，用于在2D矩阵中找到最优路径(整数、值和和的结构)，但它不会记住最优值，它只在到达矩阵底部时返回遍历的最小成本。我们应该使用堆栈以某种方式记住这些最佳值，但不幸的是，我不知道如何做到这一点。这是一种递归算法，因此分析起来有点困难。值由伪随机数(1到10)填充，并将sum初始化为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);
}回答 1
Stack Overflow用户
发布于 2013-06-01 02:49:16
您可以使用两个堆栈来查找路径。一个是临时堆栈，另一个是ANSWER堆栈。
其基本思想是，当您进行移动时，在针对特定移动的“.Also .Then ()”之后，将您前进的方向推入堆栈调用，当您到达底部时，您将该方向弹出()，并且如果以下条件为真：
if(path_cost < *min_cost)
{
*min_cost = path_cost;
}清空应答堆栈，并将临时堆栈的内容复制到其中。
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()从临时堆栈。每次你找到一个“潜在的”解决方案，答案堆栈就会更新，我没有时间做参数传递，.The临时堆栈“.Also”是你想要的本地.Use答案堆栈。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16863608
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号