在图表中查找最大的唯一组合 [英] Find max unique combinations in a graph
问题描述
经典的数字键盘如下所示
A classic numeric keypad looks like this
<br />
1 2 3<br />
4 5 6<br />
7 8 9<br />
0<br />
国际象棋中的一匹马可以水平或垂直移动两个字段然后向左或向右：
示例：
从键盘上的数字3开始，马可以移动到8或4
从键盘上的数字6开始，马可以移动到7,1或0
如果你从数字1开始，然后按照马的方式选择下一个数字在国际象棋中移动，
在10个步骤中有多少唯一的路径？
路径可以多次访问相同的号码。
示例路径：1 6 1 6 1 6 1 6 1 8
好的。所以让我感到困惑的是，我必须做10个步骤才能重复。如果这是一个寻找所有可能动作的简单案例，我想我可以找到所有组合。
我确定了连接图，但我认为这对解决方案来说是多余的。
任何想法或伪代码赞赏！
所有允许的步骤
A horse in chess can move horizontally or vertically two fields and then one to the left or right:
Example:
From the number 3 on the keypad the horse can move to 8 or 4
From the number 6 on the keyboard the horse can move to 7, 1 or 0
If you start on the number 1, and pick next number the way a horse moves in chess,
How many unique paths within 10 steps exists?
A path can visit the same number more than once.
Example path: 1 6 1 6 1 6 1 6 1 8
Ok. So the thing that confuses me is the fact that I have to do 10 steps and they can repeat. If it was a simple case of finding all possible moves I think I could find all combinations.
I identified a connected graph but I think it is redundant to the solution.
any ideas or pseudo code appreciated!
all allowed steps
1, 6, 8<br />
2, 7, 9<br />
3, 4, 8<br />
4, 3, 9, 0<br />
6, 1, 7, 0<br />
7, 2, 6<br />
8, 1, 3<br />
9, 4, 2<br />
0, 4, 6
选择此策略查找合法节点
Choosing this strategy to find legal nodes
public static int Find(int node, int index)
{
if (index == 0)
{
switch (node)
{
case 1 : return 6;
case 2 : return 7;
case 3 : return 4;
case 4 : return 3;
case 6 : return 1;
case 7 : return 2;
case 8 : return 1;
case 9 : return 4;
case 0 : return 4;
}
}
else if (index == 1)
{
switch (node)
{
case 1 : return 8;
case 2 : return 9;
case 3 : return 8;
case 4 : return 9;
case 6 : return 7;
case 7 : return 6;
case 8 : return 3;
case 9 : return 2;
case 0 : return 6;
}
}
else if (index == 2)
{
switch (node)
{
case 4 : return 0;
case 6 : return 0;
}
}
return -1;
}
第一个变化，但去哪里1 6 1 6 1 6 1 6 1 6
我需要在下一个节点找到这个模式的所有排列，我想我可以在节点树中向左移动并忽略所有正确的节点并简单地将2获取正确的节点。但是我对0节点有一个问题（我认为）
First variation, but where to go after 1 6 1 6 1 6 1 6 1 6
I need to find all permutations of this pattern with the next node, I think I can move left in the node tree and ignore all right nodes and simply multiply answer with 2 to get the right nodes. But then I have an issue with the 0 node (I think)
HashSet<string> paths = new HashSet<string>();
paths.Add("1 6 1 6 1 6 1 6 1 6");
int start = 1;
//int depth = 1;
int k = start;
for (int j = 0; j < 3; j++)
{
string path = "";
for(int i = 0; i < 10; i++)
{
int n = k;
path += string.Format("{0} ", n);
k = Find(n, j);
}
Console.WriteLine(path);
}
推荐答案
只是一套想法：
迪克斯特拉斯算法 [ ^ ]
从树到图（对数据结构的广泛检查） [ ^ ]
C＃Pathfinding [ ^ ]
使用SQL的基于图形的最短路径分析 [ ^ ]
C＃中的算法：多边形周围的最短路径（折线路由） [ ^ ]
Just set of ideas:
Dijkstra's algorithm[^]
From Trees To Graphs (An Extensive Examination of Data Structures)[^]
C# Pathfinding[^]
Graph-Based Shortest-Path Analysis with SQL[^]
Algorithms in C#: shortest path around a polygon (polyline routing)[^]
我们不做你的作业：它是有原因的。它就是为了让你思考你被告知的事情，并试着理解它。它也在那里，以便您的导师可以识别您身体虚弱的区域，并将更多的注意力集中在补救措施上。
亲自尝试，你可能会发现它不是和你想的一样困难！
如果遇到具体问题，请询问相关问题，我们会尽力提供帮助。但我们不打算为你做这一切！
We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.
Try it yourself, you may find it is not as difficult as you think!
If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!
这篇关于在图表中查找最大的唯一组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
