Tag: 算法

几天前中午和同事一起吃饭，聊到了AI（人工智能），特别是过去两三年间非常火热的ChatGPT大语言模型。他提到，有一次他在火车站打算去机场，结果火车停运了，于是他用手机查询了一下Uber去机场的费用，大概是80英镑。碰巧旁边有一位女士也要去机场，他便询问能否拼车以平摊车费。神奇的是，那位女士也查了一下Uber的价格，结果她的报价是50英镑。 同事不明白为什么仅相隔几分钟，价格会有这么大的差异。我解释道，这可能是因为Uber知道你在微软工作，觉得你有支付能力。 其实一些公司早就有算法（甚至不用AI）来实施差别定价。如果判断你是老客户，可能认为你更有可能会下单，于是就提高价格。甚至公司还会根据用户所在地区显示不同的价格，因此有时使用VPN更换地区，可能会获得更便宜的报价。 随着AI技术的引入，AI对你的了解也在增加（如性别、年龄、兴趣爱好等），模型会预测你能接受的最高价格，从而为公司带来最大化利润。当然，最简单的避免入坑的方法就是多比价（货比三家）。 Uber打车在不同手机上显示不同的价格 一位同事最近在两部不同的手机上同时预订了 Uber 车，从同一个上车点到同一个下车点。他想提高在高峰时段搭车的几率。 在 Android 上，车费为 < 290.79 – 在 iPhone 上，车费为 342.47。这是怎么回事？ 这不是故障，而是设计思维在起作用，由数据和用户洞察驱动： 用户行为：iPhone 用户通常被视为”高级客户” 数据显示他们更愿意支付更高的价格。 平台费用：Apple 对应用内购买收取高达 30% 的佣金，微妙地影响定价决策。 动态个性化：应用程序越来越多地使用基于用户行为和个人资料的动态定价。您选择的设备可能会影响您的收费。 真正的问题是： 个性化何时改善用户体验，何时开始让人觉得它是一种剥削？ …

数学中的迭代幂运算/重幂是什么？ 迭代幂运算（重幂）是数学中的一种运算，涉及到反复进行幂次运算。它是超运算序列的一部分，该序列延伸了加法、乘法和幂运算。在迭代幂运算中，一个数自乘多次，直到达到指定的次数。 一个数a迭代幂的高度n通常表示为：，也就是把n写在a的左上角，（也可以记作：a↑↑n）这表示a被迭代n次。 例如： （简单恒等式） （a自乘一次） （a的幂次为a自乘） ，依此类推。 在迭代幂运算的上下文中， 通常未定义或没有普遍共识。然而，一些数学惯例建议对于任何 ，，类似于在幂运算中对任何非零的 有 的情况。 迭代幂运算示例 让我们评估 （读作“2迭代到高度3”）： 因此 迭代幂/重幂运算的通用性质 非交换性：迭代幂运算不是交换的，这意味着 增长速度非常快：迭代幂运算增长非常快。即使是小数也会因为幂运算的快速增长而导致非常大的结果。 迭代幂运算/重幂在基础数学中较少见，但在某些高级数学领域中发挥作用，特别是在涉及极大数的领域，如大数理论和计算机科学中。 用 Python 计算迭代幂运算 以下是两个计算迭代幂运算的Python函数。第一个使用递归，第二个使用迭代。 在两个函数中，我们在开始时添加了对 n = 0 …

P、NP、NP-hard 和 NP-complete 是计算复杂性理论中的关键概念，用于描述不同类型的计算问题以及它们的求解难度。 P 类问题 P 类问题是指多项式时间内可以通过确定性算法解决的问题。这意味着，给定一个输入，问题可以在有限的步骤内得到解决，且步骤的数量是输入大小的多项式函数。换句话说，P 类问题的求解效率较高。例如，最短路径问题和排序问题都是 P 类问题。 NP 类问题 NP（Non-deterministic Polynomial time）类问题是指能够在多项式时间内验证解是否正确的问题。换句话说，虽然找到问题的解可能比较难，但一旦给出了解，我们可以在多项式时间内验证它是否正确。一个典型的 NP 问题是旅行商问题：找出某个城市之间的最短旅行路径可能很复杂，但给定一条路径，我们可以快速验证它是否满足要求。 NP-complete 问题 NP-complete 问题是 NP 类问题中的一种特殊类型。这类问题满足以下两个条件： 它是 NP 类问题，意味着给定解后可以在多项式时间内验证其正确性。 它是 NP …

“回溯 = DFS + 剪枝” 是一个对回溯算法简明且直观的描述。要理解这一点，我们可以先拆解这个等式中的几个关键概念。 深度优先搜索 (DFS) DFS（Depth-First Search）是一种图或树的遍历算法，它从根节点开始，沿着一个分支深入到尽可能远的节点，直到达到叶子节点或无可拓展的节点，然后回溯到上一个节点继续搜索其他分支。这种搜索策略自然地适合解决需要遍历所有可能状态的问题，如组合、排列问题等。 剪枝/Pruning 剪枝（Pruning）是指在搜索过程中，提前排除不符合条件的分支，以减少计算量。剪枝的主要作用是在搜索的过程中，避免无谓的计算。通过某些条件判断，可以在尚未完全展开某些分支时就停止搜索，从而减少时间复杂度。例如，当我们知道一个分支肯定不会产生有效解时，可以提前终止该分支的搜索过程。 回溯算法/Backtracking 回溯算法可以看作是深度优先搜索DFS的一种特例或具体应用。它采用DFS的思想，在搜索的过程中尝试每一种可能的选择（通常是通过递归实现），并在发现某个选择不符合条件或已经无法产生有效解时，及时回退（即“回溯”），然后继续尝试其他选择。这种“试探—回溯”的过程就构成了回溯算法。 结合三者的理解 DFS 为回溯算法提供了基本的搜索框架，即从起点开始沿着一个分支深入探索； 剪枝 则是在DFS基础上增加的优化步骤，目的是减少无效状态的探索。 因此，“回溯 = DFS + 剪枝” 是对回溯算法的一种总结。它表明回溯算法不仅仅是简单的深度优先搜索，还通过剪枝来提升效率。剪枝使得回溯算法在解决很多问题时比单纯的DFS更加高效，尤其是在解空间很大的情况下，剪枝能够大幅减少计算量，从而使得问题求解变得可行。 例子：Alpha-beta 算法剪枝 Alpha-beta 剪枝可以看作是一种回溯算法，它通过剪枝技术增强了深度优先搜索算法。 …

给定一个数独(Sudoku), 我们可以使用深度优先搜索算法(DFS), 迭代加深搜索算法(IDS)或广度优先搜索算法(BFS)来寻找可能的解. 反过来, 如果我们要设计一个算法来生成有效的数独, 我们需要澄清以下问题: 生成的数独(Sudoku)必须有可解状态吗? 是的 生成的数独(Sudoku)有多个解吗? 我们可以假设返回的Suduoku只有1个唯一解 生成的数独(Sudoku)的找解难度? 我们可以为此设置一个参数: 简单, 中等或困难 一共有6.671×10^21个有效的数独状态, 如果我们忽略旋转, 镜像状态等重复的状态, 这个数字就降到了5.4×10^9个状态. 我们可以随机生成一个由数字1-9填充的矩阵, 并检查它是否是有效的数独, 但这非常低效, 因为生成的矩阵极有可能不是有效的数独. 设计一个随机数独的算法 为了设计一个有效的算法, 生成一个随机的有效数独, 我们可以采用以下算法: 使用回溯(深度优先搜索)算法来生成一个具有随机性的有效完整数独. 例如, 我们可以随机选择数字, …

据说这个是谷歌 Google 的第一轮面试题. 一般这种题目就是: 设计一个迷宫算法 (Design a Maze). 面试中应该先问清楚需求 (Ask Clarifying Questions): 迷宫需要有几条出路? (假定至少1条), 多大的迷宫? 多复杂的迷宫等等. 最容易想到的就是随机生成1和0的地图, 其中1是墙, 0是空路, 不过这种方法生成随机的效率实在是太低, 你可以跑了半天也无法生成一个有效的迷宫, 我们假定有效的迷宫是至少含一条路径. def maze(width, height): m = None while …

在计算机里, 斐波那契数(Fibonacci) 被常常用来当作递归和循环迭代的很好的例子. 斐波那契数定义如下: F(1) = 0 F(2) = 1 F(N) = F(N – 1) + F(N – 2) for N >= 3 前几项是: 0, 1, 1, 2, 3, …