algorithm - 什么是体面的初学者图形拼图？

Question

我正在尝试更熟悉需要解决图形的问题（最好通过图形解决）。

如果有人有一个使用图表的旧 ACM 编程竞赛问题，或者在他们解决问题时发现另一个特别有启发性的问题，我将不胜感激。我想熟悉图形，轻松识别图形类型问题并能够利用基本的图形遍历算法。

任何人有一个甜蜜的问题，他们可以发送我的方式？

score 2 · Accepted Answer

为了更好地掌握图上的操作，您可能只想实现一些已知的图算法。

尝试实现Nurikabe求解器或生成器。它需要相当多的经典图操作。

score 1 · Accepted Answer

您应该熟悉柯尼斯堡桥问题。您还应该真正熟悉图论问题中经常出现的数据结构类型。

score 1 · Accepted Answer

图实际上可以用来模拟几乎任何问题。Topcoder.com马拉松比赛通常适用于基于图形的解决方案。

您可能会检查其中的一些问题——它们的来源还有更多。

score 1 · Accepted Answer

我发现这本书非常有用（亚马逊链接）：编程挑战

它不仅对图、树、基本数据结构进行了非常深入的解释，而且还对涉及每种类型的编程提出了一些挑战！这份文件对我来说比我的教科书更有用！

以下是其中的一些图形问题：

涉及图遍历的问题：

涉及图算法（Dijkstra's、Min Spanning Tree 等）的问题：

score 0 · Accepted Answer

你没有说你正在使用什么语言（考虑使用）。如果可以，我建议使用 Lisp 或 Python。它们都适用于简单的图形操作。如果你想要真正花哨，你可能想使用 PyGame 创建一个漂亮的输出。

至于问题，看一个简单的程序并将其转换为图形。提示，每个令牌都是一个节点。假设您有一些循环和方程式，那么您可以遍历图形并确定可以移出循环的内容。可以重新排列方程以更“有效”。

我对这个问题的基本原理是，它将通过查看编译器优化阶段中可能发生的过程来帮助您作为程序员。

顺便说一句，如果您尝试上述方法，请查看Plex，它将为您节省大量使用解析器的时间。

score 0 · Accepted Answer

提示：DAWG 是一种非常好的方法。

6 回答 6