2

我目前正在开始为人工智能课程做最后的项目（作为我的计算机科学学士学位的一部分）。在这个项目中，我们需要在人工智能领域选择一个有趣的问题，扩展课堂上的一个或多个主题，并解决它。我们稍后会写一份报告来讨论我们的结果并提交报告和我们编写的代码。

显然，我们不希望在经典问题的研究中达到最先进的水平，而是要么检查并解决（在很大程度上）一个不常见的问题（大多数选择这种方法的人选择解决一些简单的计算机，要么AI 研究社区尚未彻底解决的棋盘游戏）或以某种新颖的方式检查更常见的问题，可能提出一种新的有趣的启发式或对现有算法的一些修改。在后一种情况下，我们预计不会超越现代研究结果，只是提供一些新的视角。

我和我的伙伴为该项目选择的主题是推箱子，这使我们处于第二组（它没有被研究死，因为只有三分之二的常见测试集可以由最好的求解器解决，但状态这个问题的最先进的解决方案似乎太复杂了，我们希望通过一个为期两周的兼职项目来接近他们）。我们想尝试使用搜索问题方法解决推箱子问题。

无论如何，在开始实现我们的推箱子求解器之前，我开始想知道我们熟悉的几种语言（C、C++、Java 和 Python）中的哪一种更适合用于实现基于搜索的求解器来执行在一个非常大的搜索空间上搜索（推箱子有一个非常深的搜索树，有些问题需要超过 300 步才能解决，并且分支因子非常高[在某些问题中超过 100]；请注意，这个高分支因子是在以下情况下实现的只考虑石头\盒子移动，不考虑玩家移动，因此在每种状态下，我们可以将任何石头移动到四个方向中的任何一个）。

我开始考虑这个问题的主要原因是因为在另一门关于人工智能的课程中——处理将人工智能技术应用于产品设计——我创建了一个自动化房间设计师，它将通过搜索所有可能的房间设计的状态空间来设计一个房间（具有给定的房间大小和一套家具）并返回得分最高的状态（通过一些启发式方法测量）。该程序是用 Java 编写的，每次运行时都会耗尽内存，只搜索了数万个搜索节点。我认为发生这种情况的主要原因是因为我为那个项目选择了一种非常面向对象的方法；它是用 Java 编写的，每个搜索状态都由一个对象表示，每个这样的状态，当由一个搜索器对象到达时，

现在，我知道问题的一部分是使用内存密集型算法 (A*)，以及我选择实现它的方式，但我想知道使用 Java 是否也存在问题。所以这让我想到了两个问题：
1. 一般来说，在实现搜索问题和搜索算法时，哪种编程方法更合适？（面向对象、函数式或其他）
2. 在实现搜索问题和搜索算法时，哪种编程语言更合适，Java、C、C++ 还是 Python？（其他语言也是可能的，但前提是它们的语法与上述语言之一非常相似）

具体来说，这些语言的哪些特性和特性可用于实现一个问题解决程序，该程序旨在以内存（和运行时）有效的方式在非常大的搜索空间上进行搜索？

4

5 回答 5

1

我认识一些人，他们都在做像你在 Java 中描述的那样的内存密集型算法。你可以让它工作，但你必须求助于原始集合和数组。

话虽如此，我认为这不是很聪明。如果您想编写高效的 Java 代码，您基本上可以编写类似于 C/C++ 代码的代码。然后你也可以采取最后一步，直接编写 C/C++，获得进一步优化的机会（可能在速度和内存方面再获得 2 倍）。

这让我想到了你的问题：

  1. 一般来说，在实现搜索问题和搜索算法时，哪种编程方法更合适？（面向对象、功能或其他）

函数式程序通常看起来非常漂亮，并且看起来很适合算法问题。问题在于，大多数命令式算法通常更快（并且在没有错误的情况下更难编写）。面向对象，嗯，我不知道，我把它算作命令式的。对象层次结构引入了您通常不想要的计算开销（与它购买的东西相比）。

  1. 在实现搜索问题和搜索算法时，哪种编程语言更合适，Java、C、C++ 还是 Python？（其他语言也是可能的，但前提是它们的语法与上述语言之一非常相似）

我认为 Python 在简洁性上类似于函数式语言（它具有一流的功能），但对于任何严肃的事情来说它都太慢了。在您提出的语言中，我可能会选择 C++，因为 Java 不是更好但可能更慢。一种可能性是使用 Scala 之类的东西，它允许以接近或等于 Java 的速度进行简洁的编程（类似于 Python）。

于 2013-02-22T08:05:18.623 回答
0

我的意见：

Java：过于冗长/丑陋的语法，尤其是对于数学事物。并且使用了太多的内存/cpu 资源。

C：绝对可怕，如果你习惯于面向对象的无指针语言

C++：功能强大且速度快，但编译过于繁重/慢，无法使用许多不同的算法进行实验。

Python：它们中最慢的。可能很适合创建原型，但不太适合大型计算。

于 2013-02-21T16:47:25.297 回答
0

通过使用 C++ 结构，您可能会在 Java 的对象上节省一些空间，但问题的根源在于您当前的算法实现：看起来您的内存需求呈指数级增长。

伪计算：假设您的n = 10 000. 因此，您需要100 000 000转换为1 GbRAM 的对象。假设通过从 Java 切换到 C++（并将已知问题换成未知问题），您将其降低到0.5 GBRAM。太好了，除了如果你的 n 翻倍，你的内存分配会翻四倍......所以对于 n = 20 000，你需要4 GBJava RAM 和2 GBC++ RAM......

相反，如果您专注于内存效率更高的算法实现，您会发现突然之间您使用的是 MB，而不是带有大 n 的 GB。通过实现即时选择（将基于列表的体系结构换成基于迭代器的体系结构），我已经非常深刻地体验了这一点。

于 2013-02-22T09:05:54.760 回答
0

使用最佳优先搜索 (BFS) 时，空间需求通常最难管理，因为您实际上存储了整个搜索空间，而且它的大小通常是指数级的。

可以通过丢弃看起来没有希望（低分）的部分搜索空间来管理空间，或者导致放弃搜索的完整性（当“足够好”的答案是可以的）或者如果抛出部分则导致重新搜索的搜索需要重新访问。这个想法的极端版本​​被称为“深度优先搜索”（DFS），它只保留当前最有希望的分支。DFS 和 BFS 之间的折衷是所谓的束搜索。这种空间权衡方案独立于编程语言；您将它们连接到您的搜索算法中。

一旦你意识到你可以而且必须有效地管理空间，现在你必须管理搜索时间。一般来说，最好的算法总是获胜，而且通常不是原始搜索。在人工智能世界中，您通常不知道“最佳算法”，因此求助于蛮力搜索。对于原始蛮力搜索，您需要针对您可以获得的问题的最佳启发式算法，这不是算法问题；这是您必须以某种方式获得的领域知识。大多数人工智能可以说是关于试图捕捉和利用领域知识。算法和启发式知识都与语言无关。

最后，您可以通过使用并行语言来帮助管理搜索时间（尽管这最多只能为您购买 N 加速的恒定因子）。为此，您需要一种能够按需大量廉价生成并行计算的语言。我们的许多现代语言（Java、C#）都有笨拙的内置“线程”结构和笨拙的调用。C 和 C++ 没有这个内置的，但你可以使用“fork”库；不幸的是，这些使用起来更加笨拙并且通常有限制（例如，您不能拥有比操作系统提供给您的线程更多的并行粒度，最多限制为几千个，或者因为大堆栈假设。一个实用的在这种情况下，方案是将您的线程视为工作线程，每个线程扩展一个单元的一部分边界。

另一种方案是有足够的颗粒来很好地匹配你的问题结构；您基本上使用并行性来管理搜索空间中的节点。为此，您必须解决大堆栈问题，否则堆栈空间不足 :-( 我们使用称为 PARLANSE 的专有语言执行一些基于搜索的算法来支持软件工程工具，该语言几乎可以轻松地分叉子项。PARLANSE 类似于 lisp ; 它有一个 (|| ABC )内置并行运算符，用于分叉子计算 ABC 等，以及偏序并行和通用并行(spawn X)分叉子计算 X。所有这些运算符都很便宜；他们只需要几百个周期来分叉一个并行的工作；这是可能的，因为运算符是语言内置的，编译器可以理解它们。您可以看到使用 PARLANSE 编码的深度优先搜索。，您必须努力寻找(||运算符，但它在那里（提示：找到内部循环！）。PARLANSE 并行性的一个非常有用的属性是能够中止计算及其子项；这允许“最佳答案”在搜索空间中传播其结果并杀死其他搜索子节点。

IBM 的X-10 并行超级计算语言具有生成看起来很有希望的动态子代（完成构造）的设施。

于 2013-02-22T10:25:55.503 回答
0

如果您仅限于使用大多数人熟悉的语言，我可能会推荐 c++。

如果你想分支到人工智能领域常见的语言，并且我发现在其中实现求解器相对容易，我会使用 prolog。我知道你可以在网上找到启发式算法的例子。我相信您知道，Minimax 和 alpha-beta 修剪很常见。

另外，我使用了一种与 prolog 相关联的语言，称为 GDL。请参阅：http ://en.wikipedia.org/wiki/Game_Description_Language 。它包含您可能在 lisp 语法中称为 prolog 谓词的内容。

于 2013-02-21T18:06:23.477 回答