战略规划与多维背包问题

人工智能 研究 启发式 背包问题
2021-10-28 22:21:09

我正在尝试找到一种计划方法来解决尝试对新材料的学习进行建模的问题。我们假设我们只有一个资源,例如 Wikipedia,其中包含一个文章列表,表示为它所包含的知识向量以及阅读该文章的努力。

知识向量和努力

在开始之前,我们根据不同类型知识的数量设置向量的大小。例如,我们可以将向量中的项目定义为(algebra, geometry, dark ages),然后从这个角度对所有文章进行“测量”。所以,一篇数学文章可能会是(5,7,0),因为它会谈论很多关于代数和几何而不是关于黑暗时代的文章。它也将努力读取它,它只是一个整数。

问题

给定所有文章(通过努力表示为知识向量),我们希望找到帮助我们达到知识目标的最佳文章集(也表示为向量)。

因此,一个知识目标可以是(4,4,0),阅读一篇文章就足够了(2,1,0)(2,3,0)因为,当添加时,它加起来就是知识目标。我们希望以最小的努力做到这一点。

问题

我尝试了一些启发式方法来找到近似值,但我想知道是否有任何最先进的战略规划方法可以代替?

1个回答

这是一个将问题转换为旅行商问题的推测性转换,这将导致最短路径算法。

请注意,这个想法提出了不同的探索限制。

  • 给定知识向量和努力,构建一个无环有向图(无环,因为我们不应该忘记)。顶点是一篇文章,由它的知识向量表示。一条边链接两篇文章,加权为“移动”到目标文章/顶点的努力(即获取该文章的知识)。
  • 将零向量分配给新参与者。即图上的起点是顶点 V0 = (0, ..., 0)。
  • 将学习目标定义为向量 V。
  • 使用最短路径算法找到 (V0, V) 计划。

这个过程是不够的,因为有很多方法可以构建图形(换句话说,上面的内容完全没有意义需要额外的约束才能使其实用。例如,我们可以通过沿每个维度对顶点进行排序来对顶点进行排序。这样的设置会导致学习者从“简单”的文章开始(V[i] 较低),然后逐步转向更复杂的主题((V[i] 变得更高)。

图的构造取决于可用的数据。例如,知识向量是“绝对的”,还是可以是相对的?相对可以帮助创建路径,因为从 V 移动到 W 需要努力,这取决于学习者的初始条件(毕竟 V0 可能并非处处为 0)。


这是一个人工智能问题吗?确实。