对于Data Structures项目,我必须找到两个单词之间的最短路径(例如"cat"和"dog"),一次只能更改一个字母.我们给出了一个拼字游戏单词列表,用于查找我们的路径.例如:
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度优先搜索解决了这个问题,但我正在寻找更好的东西(我用trie代表字典).
请给我一些更有效的方法(在速度和记忆方面)的想法.有些荒谬和/或挑战是首选.
我问过我的一个朋友(他是一名大三学生),他说这个问题没有有效的解决办法.他说我会学习为什么我参加算法课程.对此有何评论？
我们必须一个接一个地移动.我们不能去cat -> dat -> dag -> dog.我们还必须打印出遍历.
我下学期参加comp 2210(数据结构),我一直在网上发布夏季学期的作业.到现在为止,我在完成作业时没有遇到任何问题.看一下下面的作业4,看看你是否可以给我一个如何处理它的提示.请不要提供完整的算法,只是一种方法.谢谢!
"成本排序"是一种算法,其中值序列必须按升序排列.通过一次一个地交换两个值的位置来执行排序,直到序列处于正确的顺序.每个交换产生一个成本,该成本计算为交换中涉及的两个值的总和.该类别的总成本是交换成本的总和.
例如,假设起始序列是{3,2,1}.一系列可能的交换是
Interchange 1: {3, 1, 2} interchange cost = 0
Interchange 2: {1, 3, 2} interchange cost = 4
Interchange 3: {1, 2, 3} interchange cost = 5,
given a total cost of 9
您要编写一个程序来确定排列特定数字序列的最低成本.
编辑:教授不允许暴力强迫.
在我的数据结构课程中,我们已经分配了,我们都需要做出一个全功能的量子井字棋游戏中,玩家面临的播放,赢得了BOT项目.
教授建议我们在AI中使用游戏树.然而,像往常一样,我正在寻找更具挑战性的东西.
任何人都可以提出一个更好,更先进的方法,我可以研究和实施吗？
我不是在寻找一些完全荒谬的东西,这会使问题变得更加复杂.相反,我正在寻找一种先进的方法 - 比如使用A*算法而不是BFS.
我们刚刚在我的数据结构类中分配了一个新项目 - 使用马尔可夫链生成文本.
概观
给定输入文本文件,我们创建长度为n个字符的初始种子.我们将它添加到输出字符串中,并根据频率分析选择下一个字符.
这是猫,有两只狗.
Initial seed: "Th"
Possible next letters -- i, e, e
Therefore, probability of choosing i is 1/3, e is 2/3.
Now, say we choose i. We add "i" to the output string. Then our seed becomes
hi and the process continues.
我的解决方案
我有3个类,Node,ConcreteTrie和Driver
当然,ConcreteTrie类不是传统意义上的Trie.下面是它的工作原理:
鉴于k = 2的句子:
这是猫,有两只狗.
我生成节点Th,嗨,是...... + ...,gs,s.这些节点中的每个节点都有子节点,这些子节点跟随它们.例如,Node Th将有孩子i和e.我在每个节点中维护计数,以便稍后我可以生成选择下一个字母的概率.
我的问题:
首先,完成这个项目的最有效方法是什么？我的解决方案似乎非常快,但我真的想把我的教授打掉.(在我的上一个项目编辑距离问题的一个变体,我做了A*,遗传算法,BFS和模拟退火 - 我知道问题是NP-Hard)
第二,这项任务的重点是什么？它似乎与我们课堂上所涉及的很多内容无关.我们应该学习什么？