0

我了解如何在树结构中使用广度优先搜索和 A*，但鉴于下图，它将如何实现？换句话说，搜索将如何遍历图形？S 是开始状态

图表在这里

4

5 回答 5

3

It's exactly the same as doing it in a tree. You just need to somehow keep track of which nodes you've already visited so that you don't end up going in circles.

于 2009-10-20T20:29:58.517 回答
2

基本上，您对待图表的方式与对待树的方式相同，只是您需要跟踪已经访问过的节点。这对 BFS 来说很好。最重要的是，在 A* 的情况下，考虑当你重新访问一个节点但找到了更便宜的路径时你会做什么。

于 2009-10-20T20:31:06.767 回答
0

绘制图形 - 递归搜索每个节点并将您访问的节点标记为脏。仅当图不脏时才递归。

如果内存不是问题，请复制图表，而不是标记节点，而是将它们从复制图表中删除。

于 2009-10-20T20:31:13.287 回答
0

是加权图。你想找到最短路径还是只是遍历它？如果你只想遍历，这里是：

1) 队列中只有 S
2）我们在队列中添加C和A，只有它们可以直接从S到达（有一条边）
3) D, G2 - 从 C
4) B, E - 从 A
5) G1 - 来自 D (G2 已经在队列中)
6) G2没有出边
7) 没有 B 的相邻节点不在队列中

所以这里是节点添加到队列中的顺序：S、C、A、D、G2、B、E、G1

于 2009-10-20T20:32:57.480 回答
0

我不知道你会发现这个有多大帮助，但这里有一个用功能语言 J 编码的完整解决方案（可从 jsoftware.com 免费获得）。

首先，直接从您在图片中显示的图形表示中工作可能是最简单的。我将其表示为 (# 个节点) x (# 个节点) 表，其中 (i,j) 处的数字表示节点 i 和节点 j 之间的链接值。此外，沿着对角线，我放置了与每个节点本身相关的数字。

所以，我输入如下——不要太担心不熟悉的符号，你很快就会看到结果是什么样子的：

     grph=: <;.1&>TAB,&.><;._2 ] 0 : 0
    A   B   C   D   E   G1  G2  S
A   2   1           8           2
B       1   1   1       4       2
C       3   1               5   
D               1       5   2   
E                   6   9   7   
G1                      0       
G2                          0   
S   2       3                   5
)

因此，我将变量“grph”分配为 9x9 表，其中第一行和第一列是标签“A”-“E”、“G1”、“G2”和“S”；我使用制表符来分隔项目，因此可以根据需要将其剪切并粘贴到电子表格中或从电子表格中粘贴。

现在，我将检查我的表格的大小并显示它：

   $grph
9 9
   grph
+---+--+--+--+--+--+---+---+--+
|   | A| B| C| D| E| G1| G2| S|
+---+--+--+--+--+--+---+---+--+
| A | 2| 1|  |  | 8|   |   | 2|
+---+--+--+--+--+--+---+---+--+
| B |  | 1| 1| 1|  | 4 |   | 2|
+---+--+--+--+--+--+---+---+--+
| C |  | 3| 1|  |  |   | 5 |  |
+---+--+--+--+--+--+---+---+--+
| D |  |  |  | 1|  | 5 | 2 |  |
+---+--+--+--+--+--+---+---+--+
| E |  |  |  |  | 6| 9 | 7 |  |
+---+--+--+--+--+--+---+---+--+
| G1|  |  |  |  |  | 0 |   |  |
+---+--+--+--+--+--+---+---+--+
| G2|  |  |  |  |  |   | 0 |  |
+---+--+--+--+--+--+---+---+--+
| S | 2|  | 3|  |  |   |   | 5|
+---+--+--+--+--+--+---+---+--+

它看起来不错，很容易将其与图表的图片进行比较以进行检查。现在我将删除第一行和第一列，因此我们只剩下数字（作为盒装文字），并删除任何无关的制表符。

   grn=. TAB-.~&.>}.}."1 grph

您可以看到我将此结果分配给变量“grn”。

接下来，我将用代表无穷大的“_”替换任何空单元格，然后将文字转换为数字表示（将结果重新分配给同名的“grn”）：

   grn=. ".&>(0=#&>grn)}grn,:<'_'

最后，我将把最后一列和最后一行移到开头，因为这是“S”的列，它应该是第一个。我还将显示结果以确认它看起来正确。

   ]grn=. _1|."1]_1|.grn   NB. "S" goes first.
5 2 _ 3 _ _ _ _
2 2 1 _ _ 8 _ _
2 _ 1 1 1 _ 4 _
_ _ 3 1 _ _ _ 5
_ _ _ _ 1 _ 5 2
_ _ _ _ _ 6 9 7
_ _ _ _ _ _ 0 _
_ _ _ _ _ _ _ 0

所以，既然我有一个简单的 8x8 数字表来表示图形，那么遍历它就很简单了。

这里有一个简单的 J 函数，叫做“traverseGraph”，用来读取这个表，遍历它所代表的图，并返回两个结果：访问的节点的索引（从 0 开始），以及图中点和边的值订单访问。

traverseGraph=: 3 : 0
   pts=. ,_-.~,ix{y [ nxt=. ix=. ,0
   while. 0~:#nxt=. ~.ix-.~;([:I._~:])&.><"1 nxt{y do.
        ix=. ix,nxt [ pts=. pts,_-.~,nxt{y
   end.
   ix;pts
)

我们首先初始化三个变量：索引列表“ix”（为零，因为我们想从表的第 0 行开始），一个变量“nxt”指向下一组节点（最初与起始节点）和点值列表“pts”（从输入表的第 0 行开始，内部称为“y”，删除了所有无限值。）

在“一会儿”。循环，只要将当前行从表中拉出并删除我们已经访问过的任何节点（在“ix”中）产生的“nxt”值超过零，我们就会继续。在循环内部，我们将下一组索引累积到“nxt”的末尾，并将点值累积到“pts”。最后，我们返回索引和点值作为我们的（二元素）结果。

我们像这样运行它 - 它默认显示结果：

   traverseGraph grn
+---------------+---------------------------------------------+
|0 1 3 2 5 7 4 6|5 2 3 2 2 1 8 3 1 5 2 1 1 1 4 6 9 7 0 1 5 2 0|
+---------------+---------------------------------------------+

因此，第一个框包含以“0”开头并以“6”结尾的索引。第二个装箱项是按我们累积顺序的点值向量。我不知道你用这些做什么，所以我只是给他们看。

我们可以使用索引来显示节点名称，如下所示：

   0 1 3 2 5 7 4 6{(<"0'SABCDE'),'G1';'G2'
+-+-+-+-+-+--+-+--+
|S|A|C|B|E|G2|D|G1|
+-+-+-+-+-+--+-+--+

我不知道您会发现它有多大用处，但它确实为您的问题提供了一个简单的解决方案。

于 2009-10-30T21:17:14.573 回答