热门标签：
Mac 多显示器 显示器扩展 requests patch 并发 Alpine Linux BSD Linux 电动汽车 全部标签

从数小时到 360 毫秒：过度工程的数独难题求解

2025-02-08

作者尝试解决一个数独难题，目标是找到使得所有行组成的九个九位数的最大公约数最大的解。最初使用 Z3 求解器，但运行数小时仍未找到结果。作者随后尝试了多种优化方法：首先通过数学分析缩小搜索空间，然后使用 BFS 算法，并逐步优化 `is_good` 函数，从使用 HashSet 到使用 bitset，最后利用 SIMD 技术进行向量化计算。通过多线程和改进线程同步机制，最终将求解时间从数小时缩短到 360 毫秒，实现了超过 1600 倍的加速。虽然最终发现直接硬编码答案是最快的，但这篇文章展示了即使是看似简单的算术问题，也能通过精细的算法优化获得巨大的性能提升。

阅读更多
(blog.danielh.cc)
开发

Minecraft服务器选址引发的投票系统思考

2024-12-21

一个Minecraft服务器的选址问题，引发了对不同投票系统的深入探讨。最初使用的简单多数投票制（Plurality voting）由于“破坏者效应”导致最不受欢迎的选择获胜。随后尝试了即时决选投票制（Instant runoff），虽然解决了部分问题，但在候选人变化时，却出现了违反单调性（Monotonicity）的情况。作者进一步介绍了博达计分法（Borda method）和阿罗不可能定理（Arrow's theorem），并最终推荐了评分投票制（Score voting）和认可投票制（Approval voting）作为更优方案，因为它们满足阿罗不可能定理的三个条件：一致性、非独裁性和无关选项独立性。

阅读更多
(blog.danielh.cc)
游戏 阿罗不可能定理

意外编写了一个快速的SAT求解器

2024-12-06

作者最初为了解决大学课程注册的难题，编写了一个程序来寻找最佳的课程组合，避免时间冲突。该程序使用了回溯算法，类似于解决八皇后问题的思路。作者发现这个程序实际上解决了一个更普遍的问题——布尔可满足性问题（SAT）。通过将布尔公式转换为课程目录和时间安排，程序可以高效地找到满足条件的解，甚至复杂的需求也能在100毫秒内解决。

阅读更多
(blog.danielh.cc)
12
未分类 回溯算法 课程安排