我正在努力完成我的CS课程的作业 . 以下是一些说明：
在此分配中，您将编写一个程序，该程序使用称为深度优先搜索的技术通过数字网格查找路径 .
作为输入，您将获得一个数字网格，一个起点，一个终点和一个目标总和 . 您的任务是找到一条正交通过网格的路径，沿路径保持数字的运行总数，并以所需的目标总和结束终点 .
细节：
您可以假设数字网格不会大于10乘10 . 数字网格的示例可能如下所示：34 58 12 10 34 3 91 10 10 41 10 76 10 7 12 10 82 10 81 98 10 10 10 9 17
起始点将使用两个数字指定，即行号和列号 . 请注意，计算行数和列数时，从零开始 . 因此，在下面的示例网格中，我们可以将起点指定为第2行，第0列 . 这将指示直接位于第3行的数字10.同样，将使用行号和列号指定结束点 . 第0行第3列的结束点将指向12和34之间的顶行中的10 . 目标总和只是您希望路径总和的整数值 . 如果您获得了上面的网格，包括起点（2,0），终点（0,3）和目标总和100，那么您可以通过跟随网格中的十个10来找到成功的路径 .
输入：
输入文件将包含以下内容：
第一行：7个整数targetValue，目标总和grid_rows，网格grid_cols中的行数，网格start_row中的列数，起始点start_col的行数，起始点end_row的列数，行结束点的编号end_col，结束点的列号所有后续行：输入文件中将有（grid_rows）附加行 . 每一行都包含（grid_cols）整数，表示该行网格中的数字 . 以下是您的程序应成功查找路径的三个输入文件示例：
pathdata1：此文件有一个不易查找的路径 . pathdata2：这有一个较小的矩形网格 . pathdata3：这有一个更大的网格，有几个死端路径 . 这个文件是一个很好的例子，说明如何设计复杂的迷宫并使用你的程序解决它们！提示：
您的主程序应执行以下任务：打开输入文件"pathdata.txt" . 将第一行的内容读入变量 . 读入网格 . 我建议将其表示为列表列表 . 定义一个类"Problem"，它具有作为类变量的网格，路径历史，起始行和列以及总和 . 创建类Problem的实例，为其实例变量分配适当的值 . 以漂亮的格式打印出变量和网格的值 . 这将确保您正确读取所有内容并按照您希望的方式构建数据结构 . 我强烈建议你为类定义一个很好的 str 方法在这里使用问题，在你的程序执行时显示进度，并帮助你调试 . 调用函数"solve"，如下所述 .
你还应该有一个函数“solve”，它将一个Problem实例作为一个参数，如果找到一个，则返回解决方案路径，如果没有，则返回“None” . “solve”应该执行以下任务：测试以查看Problem实例是否为目标状态，这意味着它当前处于结束状态且总和与目标总和匹配 . 如果是，请打印相应的消息并显示路径历史记录 . 如果它不是目标状态，请检查总和是否超过目标总和 . 如果是这样，请打印一条消息并返回“无” . 如果这样做是合法的举动，请尝试向右移动 . 使用适当的开始行/列创建新的Problem实例 . 将当前网格点设置为“无”（使其成为“已访问过的”） . 更新总和和历史记录 . 打印新的Problem实例，然后使用实例作为参数递归调用“solve” . 如果递归调用返回成功路径，则返回结果 . 如果向右移动不起作用，请尝试向上移动，然后向下移动，然后向左移动 . 如果没有尝试成功，则返回“None” .
编写一个函数“isValid”可能会对您有所帮助，该函数可以让您知道建议的移动是否有效 . isValid将当前网格，其大小以及建议的行和列位置作为参数，如果它是有效位置则返回True，如果是有效位则返回False不是 . 如果您要么尝试移出网格边界，或者您尝试移动到当前路径已访问过的位置（意味着该位置的值为“无”），则该位置将无效 .
这是指示 . 我遇到的问题是回溯 . 我尝试这样做，如果超过目标总和，我将路径历史记录，总和和位置重置为超出之前的状态，然后继续迷宫 . 但这只是让我进入一个无限循环，我会回去，然后去我超过总和的地方，然后回去等等，任何提示？
我不想作弊，所以如果可以，请指出我正确的方向 . 有关如何在我的代码中实现解决方案的提示表示赞赏 .
1 回答
你用过什么算法？我建议你研究基本的图遍历算法 . Dijkstra's algorithm是一个很好的起点，可以在generic Python code中找到 .
基本的想法是，您维护一个已经访问过的节点列表（达到每个节点的最低成本），以及要访问的“待办事项”节点列表（“下一个”，或超出一些访问过的一个节点）节点） . 将顶级节点从“待办事项”列表中删除，将其添加到访问列表（具有到达的成本），并检查连接到它的每个节点 . 如果未访问该节点，请使用当前成本将其添加到“待办事项”列表中;如果已经访问过，请检查到达那里并保持最低成本 .
死胡同将自己死;当您用完要访问的节点时，请查看到达目标节点的路径成本最低 .