以树形图为支持的自顶向下分析方法

Patrice T

5.00/5 (2投票s)

2023年7月22日

CPOL

5分钟阅读

3213

树形图用作自顶向下分析方法的基础

下载源代码 - 30.6 KB

引言

我使用树形图作为自顶向下分析方法的辅助工具。因为一张纸永远不够大。以下是我的做法。

背景

yEd 图形编辑器

yEd 是由 yWorks 制作的免费图形编辑器。yWorks 是一家围绕一个库开发的公司，该库允许轻松地将图形集成到分层应用程序中。

yEd 有两种版本：Java 应用程序或浏览器在线版本。

我使用 yEd 的主要原因是其出色的自动布局功能。每次我在树中进行更改时，只需单击一下，树就会根据设置重新构建。

逐步求精、结构化编程、自顶向下分析方法

三个名称，或多或少代表相似的范例和相同的结果：一个将算法转化为结构化程序的指导方针，也有助于定义算法本身。

逐步求精是一种通用的方法，并非专门针对编程
Edsger W. Dijkstra 等人的结构化编程
Nicklaus Wirth 的自顶向下分析方法

我并不拘泥于其中一种方法，而是混合使用这三种。

将典型结构转化为树

程序流程图是源代码到二维图形的翻译，问题在于它无助于定义算法。

借助这些分析方法，我们从一个普遍的想法开始，然后逐步求精，树有助于在不同级别上可视化算法解决方案。

基本原理是从一个复杂的单一问题开始，将其分解为几个更简单的问题，并不断细化，直到每个小问题都足够简单，可以无需进一步解释就能编写代码。

元素	图形
块矩形
条件菱形。
循环圆角矩形

模式	树形翻译
序列序列 A 序列 B
选择如果 A 为真序列 A 结束 if
选择如果 A 为真序列 A else 默认序列结束 if
选择如果 A 为真序列 A 否则如果 B 为真序列 B else 默认序列结束 if
重复当 A 为真时序列 A 结束 while
重复 do 序列 A 当 A 为真时
重复 do 序列 A 直到 A 为真

您可以随意使用任何形状和模式来满足您的需求，但如果您共享树形图，则需要解释它们。

模式	树形翻译
接下来
Start 当达到结束条件时序列 A 步长结束 while
计数器= 起始值当计数器 <= 结束值时序列 A 计数器= 计数器+ 步长结束 while

当有足够的信息可以转化为代码时，您就停止深入细节。

实际案例：N皇后问题

八皇后问题 - 维基百科[^]

目标是在相同大小的棋盘上放置 8 个皇后。同样的问题也可以用不同大小的棋盘来解决。

手动解决。仅描述方法的大致思路。

如果棋盘已满，则这是一个解决方案。
对于新的一行，搜索第一个可能的皇后位置。然后转到下一行。
对于已有的皇后，搜索下一个可能的位置。然后转到下一行。
当一行中没有更多可能的位置时，返回上一行并移动皇后。

该方法称为**回溯**。

增量分析

我将使用一种回溯版本的求解算法。基本上，求解算法会寻找所有解决方案，我将在找到第一个解决方案后停止它。

注释	树形翻译
N皇后求解器需要棋盘大小需要存储每个皇后的位置皇后的位置就是结果

我选择了一个非递归的回溯算法。它是一个大循环，内部有两个部分：一个前向循环和一个回溯部分。

模式	树形翻译
当搜索未完成时前进回溯 End While

注释	树形翻译
需要跟踪当前行如果列在棋盘上，则尝试它，否则回溯
前进如果位置是空的，下一行和第 0 列，否则下一列回溯上一行下一列

现在，只需检查给定单元格是否为空或被占用。

注释	树形翻译
位置为空，如果没有皇后占用该单元格在垂直线或对角线上
最后

转化为代码

// NQueens Solver
#include <iostream>
using namespace std;

// Persistant Initialisation
const int BSize = 8;
int QPos[BSize + 1];

int IsFree(int Row) {
	for (int Index = 1; Index < Row; Index++) {
		// Check column
		if (QPos[Row] == QPos[Index])
			return 0;
		// Check diag /
		if (QPos[Row] == QPos[Index] + (Row - Index))
			return 0;
		// Check diag \
		if (QPos[Row] == QPos[Index] - (Row - Index))
			return 0;
	}
	return 1;
}

int NQ_Solver() {
	// Local Initialisation
	int Row = 1;
	QPos[Row] = 0;
	// BackTracking Search
	while (Row > 0) {
		if (QPos[Row] < BSize) {
			// Go Forward
			if (IsFree(Row)) {
				// Ok, Solution or Next Row
				if (Row < BSize) {
					Row++;
					QPos[Row] = 0;
				} else {
					//	Solution found, Abort
					return 1;
				}
			} else {
				// Next Column
				QPos[Row]++;
			}
		} else {
			// Go Backward
			Row--;
			QPos[Row]++;
		}
	}
	return 0;
}

int main() {
	cout << "NQueens Solver" << endl;
// Call Solver
	if (NQ_Solver()) {
		// Result
		for (int Index = 1; Index <= BSize; Index++) {
			cout << " " << QPos[Index] + 1;
		}
		cout << endl;
		// Board Solution
		for (int Index = 0; Index < BSize; Index++) {
			for (int Col = 0; Col < BSize; Col++) {
				if (QPos[Col + 1] == Index) {
					cout << " *";
				} else {
					cout << " .";
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << "fini" << endl;
	return 0;
}

NQueens.cpp 在 TopDown.zip 中.

结果

NQueens Solver
 1 5 8 6 3 7 2 4
 * . . . . . . .
 . . . . . . * .
 . . . . * . . .
 . . . . . . . *
 . * . . . . . .
 . . . * . . . .
 . . . . . * . .
 . . * . . . . .

fini

关注点

在创建算法时，构建树形图非常有助于我可视化想法，但由于树的形状会随着每次添加而改变，因此操作很繁琐。

相对于流程图的主要优点在于，我们不必拘泥于编程语言的语法，而是可以利用这种方法来组织算法的高级描述。

yEd 的自动布局功能简化了树形图的创建过程。

链接

历史

2022 年 9 月 11 日：初稿
2023 年 7 月 22 日：首次发布

元素	图形
块矩形
条件菱形。
循环圆角矩形

模式	树形翻译
序列序列 A 序列 B
选择如果 A 为真序列 A 结束 if
选择如果 A 为真序列 A else 默认序列结束 if
选择如果 A 为真序列 A 否则如果 B 为真序列 B else 默认序列结束 if
重复当 A 为真时序列 A 结束 while
重复 do 序列 A 当 A 为真时
重复 do 序列 A 直到 A 为真