寻找两个十位数字之间正交路径的算法

Question

4

假设有一个由10个数字组成的集合S。对于任意两个在S中的数字v和w，我想知道是否存在一系列数字v=u_0, u_1, ... , u_k=w，满足以下条件：

如果能找到一个算法来找到最短的这样的序列，那就更好了。

理想情况下，我希望得到一个C语言（或伪代码）的解决方案，但我真的非常感谢任何建议！谢谢！

- PengOne

2

如果你们投票关闭的话，能否给我一个提示为什么这样做，我会非常感激。谢谢。 - PengOne

2

我想这是因为没有代码，而是一个高级算法问题。但我不是一个downvoter。我的建议是使用广度优先搜索或A*算法。 - user7116

3

这很荒谬。只是因为人们不理解这些术语，就试图关闭它。这似乎只是一个寻找最短路径的图形问题。 - Aryabhatta

这是什么编程谜题？使用数字来模拟这个问题有点不自然，标准的方法应该是使用向量。 - starblue

我有向量，但觉得问题听起来太复杂了。我真的想在有限域上做一个n维向量空间的这个问题。 - PengOne

显示剩余3条评论

2个回答

0

我会将S转换为节点对象的图形，其中每个节点对象包含指向相邻节点的链接。（在某些编程语言中，将“链接”读作“指针”。）通过您对序列的条件2定义相邻性，因此通过生成的图形的任何路径都是匹配两个条件的序列。

从那里开始，检查图形中两个顶点的连通性就是一个简单的问题。最简单的解决方案是广度优先搜索。（该特定算法也恰好找到最短路径。）

- aschepler

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aryabhatta · Accepted Answer

将S中的元素形成一个图：当且仅当它们在某一坐标上不同，u和v相邻。

现在给定u，进行广度优先搜索直到找到v。