目标:在满足未探索格不包含2*3矩阵的条件下使得已探索格数量最小,且已探索格之间必须是连通的
直觉:假设大网格也是简单的n*m矩阵,将其划分为规则的(n/2)*(m/3)个不相交的2*3矩阵,每个矩阵至少要有一格被探索,这样需要大约1/6 mn格。而每个被探索的格子之间应当是连通的,一个最简单的策略就是每一行2*3矩阵之间连一条线,再用一列把每行连起来,这样大约是1/3 mn格,直觉上这也是最优的。
这里抛砖引玉一个分析角度:将每个落于2*3矩阵的单元格连起来是复杂的,因为每个单元格在2*3中的位置是不固定的。但可以将2*3矩阵整体看成一个单位格,而修改连通花费,即横向跨越一个2*3矩阵的花费为2,纵向跨越一个2*3矩阵的花费为3(原来都是1)。从这个角度看,探索策略应当尽量多地横向走而不是纵向走。
期待吧友提供严格的思路证明。
同时提供两个常见的探索路径


直觉:假设大网格也是简单的n*m矩阵,将其划分为规则的(n/2)*(m/3)个不相交的2*3矩阵,每个矩阵至少要有一格被探索,这样需要大约1/6 mn格。而每个被探索的格子之间应当是连通的,一个最简单的策略就是每一行2*3矩阵之间连一条线,再用一列把每行连起来,这样大约是1/3 mn格,直觉上这也是最优的。
这里抛砖引玉一个分析角度:将每个落于2*3矩阵的单元格连起来是复杂的,因为每个单元格在2*3中的位置是不固定的。但可以将2*3矩阵整体看成一个单位格,而修改连通花费,即横向跨越一个2*3矩阵的花费为2,纵向跨越一个2*3矩阵的花费为3(原来都是1)。从这个角度看,探索策略应当尽量多地横向走而不是纵向走。
期待吧友提供严格的思路证明。
同时提供两个常见的探索路径












