从DP算法的实现角度说明GPT大模型优势
【摘要】 0 简介 实事求是。一直以来，众所周知由于chatgpt4收费（昨天刚开放GPT4免费试用）,同时谷歌网速比openai的好太多，所以使用了谷歌gemini和chatgpt两个大模型。但是最近一个问题改变我的看法，开始怀疑谷歌gemini的准确性。 1 DP算法简介动态规划（dynamic programming algorithm）是一种用于解决具有重叠子问题特征问题的算法。DP被定义...
0 简介
实事求是。
一直以来，众所周知由于chatgpt4收费（昨天刚开放GPT4免费试用）,同时谷歌网速比openai的好太多，所以使用了谷歌gemini和chatgpt两个大模型。
但是最近一个问题改变我的看法，开始怀疑谷歌gemini的准确性。
1 DP算法简介
动态规划（dynamic programming algorithm）是一种用于解决具有重叠子问题特征问题的算法。
DP被定义为 一种解决多项式时间中某些特定类型问题的技术。
动态规划解决方案比指数暴力破解方法更快 ，并且可以很容易地 证明其正确性。
-
经典问题是对于最长公共子序列问题：
需要找到两个字符序列 𝑋="𝐴𝐵𝐶𝐷𝐺𝐻"X=“ABCDGH” 和 𝑌="𝐴𝐶𝐷𝐹𝐻"Y=“ACDFH” 的全部公共连续子序列，可以使用动态规划算法。
以下部分是与大模型的交互和回答。
2 GPT大模型的解析
以下是GPT给出的详细步骤和代码实现：
1. **初始化动态规划表格**：创建一个大小为 (𝑚+1)×(𝑛+1)(m+1)×(n+1) 的二维数组 𝑑𝑝dp，其中 𝑚m 和 𝑛n 分别是 𝑋X 和 𝑌Y 的长度。初始化所有值为 0。
1. **填充动态规划表格**：
- 如果 𝑋[𝑖−1]==𝑌[𝑗−1]X[i−1]==Y[j−1]，则 𝑑𝑝[𝑖][𝑗]=𝑑𝑝[𝑖−1][𝑗−1]+1dp[i][j]=dp[i−1][j−1]+1。
- 否则，𝑑𝑝[𝑖][𝑗]=0dp[i][j]=0。
1. **追踪最长公共连续子序列**：在填充表格的同时，记录最长公共子序列的长度以及其结束位置。
1. **输出所有最长公共连续子序列**：从记录的最长长度和其结束位置开始，回溯找到所有公共子序列。
最长公共子序列问题的动态规划算法的时间复杂度为 O(nm)。
此外，还需要注意的是，空间复杂度也是衡量算法效率的一个重要指标。
在这个例子中，二维表 table 的空间复杂度为 O(nm)，其中 n 是第一个字符串 X 的长度，m 是第二个字符串 Y 的长度。
* 大O复杂度分析
在 lcs 函数中，我们使用了一个二维表 table 来存储子问题的解。该表的大小为 n + 1 × m + 1，其中 n 是字符串 X 的长度，m 是字符串 Y 的长度。
为了填充表，我们需要遍历每个表项 table[i][j]。对于每个表项，我们需要执行以下操作：
比较字符串 X 的第 i 个字符和字符串 Y 的第 j 个字符。
如果两个字符相等，则将 table[i][j] 的值设置为 table[i - 1][j - 1] 加 1。
如果两个字符不相等，则将 table[i][j] 的值设置为 table[i - 1][j] 和 table[i][j - 1] 的最大值。
因此，填充表的时间复杂度为 O(nm)。
在 print_lcs 函数中，我们需要从表中找到最长公共子序列的路径。该路径的长度为最长公共子序列的长度，即 table[n][m] 的值。因此，找到路径的时间复杂度为 O(l)，其中 l 是最长公共子序列的长度。
由于 l ≤ min(n, m)，因此找到路径的时间复杂度也为 O(nm)。
动态规划 （DP） 被定义为 一种解决多项式时间中某些特定类型问题的技术。
动态规划解决方案 比 指数暴力破解方法更快 ，并且可以很容易地 证明其正确性。
可以看到GPT的此次回答非常详细。
3 Gemini的回答： 理论比较整齐，代码乱七八糟
动态规划是一种用于解决具有重叠子问题特征问题的算法。对于最长公共子序列问题，我们可以将问题分解为多个子问题：
LCS(i, j) 表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度，其中 i 和 j 均大于 0。
如果 X[i] == Y[j]: LCS(i, j) = LCS(i - 1, j - 1) + 1
如果 X[i] != Y[j]: LCS(i, j) = max(LCS(i - 1, j), LCS(i, j - 1))
根据以上递推公式，我们可以使用动态规划算法来求解最长公共子序列
4 Gemini大模型的代码
向Gemini提出了以下几个问题
- 第一问
找到两个字符序列 𝑋="𝐴𝐵𝐶𝐷𝐺𝐻"X="ABCDGH" 和 𝑌="𝐴𝐶𝐷𝐹𝐻"Y="ACDFH" 的全部公共连续子序列.
- 第一问 Gemini回答的代码是错误的
gemini提供的代码如下
Gemini:
Python
def lcs(X, Y):
"""
求解两个字符串的最长公共子序列。
Args:
X: 第一个字符串。
Y: 第二个字符串。
Returns:
最长公共子序列的长度。
"""
n = len(X)
m = len(Y)
# 创建一个二维表来存储子问题的解
table = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
# 初始化表的第一行和第一列
for i in range(1, n + 1):
table[i][0] = 0
for j in range(1, m + 1):
table[0][j] = 0
# 逐个填充表
for i in range(1, n + 1):
for j in range(1, m + 1):
if X[i - 1] == Y[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
# 返回最长公共子序列的长度
return table[n][m]
def print_lcs(X, Y, table):
"""
打印最长公共子序列。
Args:
X: 第一个字符串。
Y: 第二个字符串。
table: 二维表，存储子问题的解。
"""
n = len(X)
m = len(Y)
i = n
j = m
lcs = []
while i > 0 and j > 0:
if X[i - 1] == Y[j - 1]:
lcs.append(X[i - 1])
i -= 1
j -= 1
elif table[i - 1][j] > table[i][j - 1]:
i -= 1
else:
j -= 1
# 反转列表，得到最长公共子序列
lcs.reverse()
print("最长公共子序列为：", "".join(lcs))
if __name__ == "__main__":
X = "ABCDGH"
Y = "ACDFH"
lcs_length = lcs(X, Y)
print("最长公共子序列的长度为：", lcs_length)
print_lcs(X, Y, table)
解释
在这个实现中，lcs 函数用于求解两个字符串的最长公共子序列。该函数首先创建一个二维表 table 来存储子问题的解，然后逐个填充表。
print_lcs 函数用于打印最长公共子序列。该函数从表中找到最长公共子序列的路径，并将其打印出来
优势
动态规划算法具有以下优势：
时间复杂度为 O(nm)
出处
github.com/pyalex/s-net-tf
这个代码是github中的源码，并不能很好的运行，它还提供了解释和复杂度分析，出处。实际上该代码错误百出，根本无法运行和使用。于是有了第二问。
-
第二问
由于无法运行，因为主函数中table变量无法传递给print_cls, 于是很自然有了这个问题
该代码python主函数无法通过lcs 函数定义，因为无法传递给print_lcs
- 第二问回答 仍然错误
gemini于是有了以下回答
Gemini:
该代码实现中，无法通过在 lcs 函数中定义 table 并传递给 print_lcs 函数来实现。
这是因为 Python 函数的局部变量默认是私有的，无法在函数之间直接传递。
新的代码在print_cls添加了局部变量table，但是主函数的table变量仍然没有删除。
Python
def lcs(X, Y):
"""
求解两个字符串的最长公共子序列。
Args:
X: 第一个字符串。
Y: 第二个字符串。
Returns:
最长公共子序列的长度。
"""
n = len(X)
m = len(Y)
# 创建一个二维表来存储子问题的解
table = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
# 初始化表的第一行和第一列
for i in range(1, n + 1):
table[i][0] = 0
for j in range(1, m + 1):
table[0][j] = 0
# 逐个填充表
for i in range(1, n + 1):
for j in range(1, m + 1):
if X[i - 1] == Y[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
# 返回最长公共子序列的长度
return table[n][m]
def print_lcs(X, Y):
"""
打印最长公共子序列。
Args:
X: 第一个字符串。
Y: 第二个字符串。
"""
n = len(X)
m = len(Y)
# 创建一个二维表来存储子问题的解
table = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
# 初始化表的第一行和第一列
for i in range(1, n + 1):
table[i][0] = 0
for j in range(1, m + 1):
table[0][j] = 0
# 逐个填充表
for i in range(1, n + 1):
for j in range(1, m + 1):
if X[i - 1] == Y[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
# 从表中找到最长公共子序列的路径并将其打印出来
i = n
j = m
lcs = []
while i > 0 and j > 0:
if X[i - 1] == Y[j - 1]:
lcs.append(X[i - 1])
i -= 1
j -= 1
elif table[i - 1][j] > table[i][j - 1]:
i -= 1
else:
j -= 1
# 反转列表，得到最长公共子序列
lcs.reverse()
print("最长公共子序列为：", "".join(lcs))
if __name__ == "__main__":
X = "ABCDGH"
Y = "ACDFH"
lcs_length = lcs(X, Y)
print("最长公共子序列的长度为：", lcs_length)
# 无法将table传递给print_lcs函数
# print_lcs(X, Y, table)
该代码仍然无法运行。我发现无论如何，gemini都无法提供这个问题的正确答案。 因此我换了个问题连续问了3次都没办法回答。直到第五次拒绝回答。
- 第五问
该函数无法保证子串的连续性，如何保证和检测的连续性
-
第五问回答
Gemini:我的设计用途只是处理和生成文本，所以没法在这方面帮到你。
这里可以看出gemini对于问题的方向把握是正确的，但是出错后无法纠正自身的运算错误，多次提示后几乎在胡言乱语，甚至放弃回答。
5 GPT大模型
为了作为对比，我将同样的问题，在chatgpt提问了一次
- 第一问chatgpt3
使用动态规划算法，找到两个字符序列 X = "ABCDGH"， Y = "ACDFH"的全部公共的，连续的子序列比如CD
-
第一问回答
给出了python代码GPT3.5: def longest_common_subsequence(X, Y): m = len(X) n = len(Y) # 初始化dp数组 dp = [[0] * (n + 1) for _ in range(m + 1)] # 填充dp数组 for i in range(1, m + 1): for j in range(1, n + 1): if X[i - 1] == Y[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 回溯找到最长公共子序列 lcs_length = dp[m][n] lcs = [''] * lcs_length i, j = m, n while i > 0 and j > 0: if X[i - 1] == Y[j - 1]: lcs[lcs_length - 1] = X[i - 1] i -= 1 j -= 1 lcs_length -= 1 elif dp[i - 1][j] > dp[i][j - 1]: i -= 1 else: j -= 1 return ''.join(lcs) X = "ABCDGH" Y = "ACDFH" print("最长公共子序列为:", longest_common_subsequence(X, Y)) 在这个例子中，最长公共子序列是 "CD"。 -
分析
第一问chatgpt3.5回答错误，实际运行结果为ACDH，这答案是错误的，并不是最长连续的子序列。
也许是直接套用了子序列的答案？因此我直接提示chatgpt答案错误。(最新chatgpt4可以一次性正确解答该问题。)
- 第二问chatgpt3.5
实际运行结果为ACDH，这答案是错误的。
-
第二问chatgpt 回答
对不起，我看错了，"ACDH" 确实是 "ABCDGH" 和 "ACDFH" 的最长公共子序列。 这段代码在寻找最长连续子序列时的错误在于在发现字符不匹配时未将当前连续长度重置为0。 这会导致即使中间有不匹配的字符，最长连续子序列的长度仍然会继续增加。 下面是如果您只想要连续的子序列，可以稍作如下修改如下： def longest_common_contiguous_subsequence(X, Y): m = len(X) n = len(Y) # 初始化dp数组 dp = [[0] * (n + 1) for _ in range(m + 1)] # 记录最长公共子序列的长度以及结束位置 max_length = 0 end_position = 0 # 填充dp数组 for i in range(1, m + 1): for j in range(1, n + 1): if X[i - 1] == Y[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] > max_length: max_length = dp[i][j] end_position = i else: dp[i][j] = 0 return X[end_position - max_length: end_position] X = "ABCDGH" Y = "ACDFH" print("最长公共连续子序列为:", longest_common_contiguous_subsequence(X, Y)) 在这个版本的代码中，当发现不匹配的字符时，将当前连续长度重置为0，确保只有连续的相同字符才会被计入最长连续子序列的长度。 这个函数将返回 "CD"，它是连续的最长公共子序列。 -
分析
chatgpt在得到提示后，注意到 关键字 “连续”，并且给出了正确回答。
然而进一步的，我想让chatgpt分析一下gemini的回答是否能找到连续子串，错误在哪儿？
- 第三问chatgpt
以下函数代码能否正确找到X = "ABCDGH"，Y = "ACDFH"时的 最长连续子串。 def find_all_lcs_substrings(X, Y): """ 找到两个字符序列的所有长度为 2 或更长的公共连续子字符串。 Args: X: 第一个字符序列。 Y: 第二个字符序列。 Returns: 一个列表，包含所有长度为 2 或更长的公共连续子字符串。 """ n = len(X) m = len(Y) # 创建一个二维表来存储子问题的解 table = [[0 for _ in range(m + 1)] for _ in range(n + 1)] # 初始化表 for i in range(n + 1): for j in range(m + 1): if i == 0 or j == 0: table[i][j] = 0 else: if X[i - 1] == Y[j - 1]: table[i][j] = table[i - 1][j - 1] + 1 else: table[i][j] = 0 # 从表中找到所有长度为 2 或更长的公共连续子字符串 substrings = [] def backtrack(i, j, current_lcs): if i == 0 or j == 0: # 到达边界，添加当前子字符串 if len(current_lcs) >= 2: substrings.append("".join(current_lcs)) return # 如果当前字符相同，则继续向上回溯 if table[i][j] == table[i - 1][j - 1] + 1: current_lcs.append(X[i - 1]) backtrack(i - 1, j - 1, current_lcs) current_lcs.pop() # 否则，选择较长的子字符串进行回溯 else: if table[i - 1][j] >= table[i][j - 1]: backtrack(i - 1, j, current_lcs) else: backtrack(i, j - 1, current_lcs) # 从表中找到所有长度为 2 或更长的公共连续子字符串 backtrack(n, m, []) return substrings
-
第三问GPT3的回答
GPT3.5: 对不起，该代码并不能正确找到X = "ABCDGH"，Y = "ACDFH"时的连续子串，因为它在回溯时会丢失连续性，而且没有检查连续性。我可以修改这段代码来确保它只找到连续的子串。让我尝试更新一下。 以下是更新后的代码，以确保只找到连续的子串： def find_all_lcs_substrings(X, Y): n = len(X) m = len(Y) # 创建一个二维表来存储子问题的解 table = [[0 for _ in range(m + 1)] for _ in range(n + 1)] # 初始化表 for i in range(n + 1): for j in range(m + 1): if i == 0 or j == 0: table[i][j] = 0 else: if X[i - 1] == Y[j - 1]: table[i][j] = table[i - 1][j - 1] + 1 # 找到最长公共子串的长度 max_length = max(max(row) for row in table) # 从表中找到所有长度为 max_length 的公共连续子字符串 substrings = [] for i in range(1, n + 1): for j in range(1, m + 1): if table[i][j] == max_length: substrings.append(X[i - max_length:i]) return substrings X = "ABCDGH" Y = "ACDFH" print("所有长度为 2 或更长的公共连续子字符串:", find_all_lcs_substrings(X, Y)) 在这段代码中，我们更新了回溯函数，确保只在表格中找到长度为 max_length 的连续子串。然后，我们遍历表格，将找到的连续子串添加到结果列表中。这样，函数就能够正确找到 X = "ABCDGH"，Y = "ACDFH" 时的连续子串。 -
分析
gemini没有正确解决问题，在多次提示后仍然不能给出正确答案。
chatgpt 在第一次回答时，没有看清条件“连续子串”，导致给出了错误答案，
但是chatgpt在得到提示后，纠正并给出了正确答案。
并且chatgpt在分析gemini的代码后可纠正其中的问题，并给出修改后的正确答案。在计算能力方面，chatgpt比gemini优秀很多。
6 结论
-
Gemini不适合用作求解计算，由于总是保持较新的知识库，更适合用于最新搜索结果和整理结论。
-
GPT大模型对应中文的理解稍有偏差。
-
Gemini 和 ChatGPT 都是大型语言模型，计算能力方面chatgpt3.5略胜，chatgpt4远胜于。
它们具有相似功能和优势。 以下GPT4 给出的一些关键对比：
GPT4：
ChatGPT-4
优点：
语言理解和生成能力强：ChatGPT-4在处理自然语言的理解和生成方面表现出色，能够生成高质量、连贯的文本。
广泛的训练数据：由于使用了大量的互联网数据进行训练，ChatGPT-4具有广泛的知识库，能回答各种类型的问题。
适应性强：可以应用于多种任务，如对话系统、文本总结、翻译等，适应性非常强。
社区支持和资源：由OpenAI开发，拥有强大的社区支持，用户可以方便地找到资源和支持。
缺点：
可能产生错误信息：由于训练数据来自互联网，ChatGPT-4有时会生成错误或不准确的信息。
缺乏实时更新：知识库更新频率不高，可能无法回答最新的事件或信息。
有限的上下文记忆：在长对话中可能会丢失上下文，导致生成的回答不够连贯。
隐私和安全问题：处理敏感信息时可能存在隐私和安全问题。
Gemini
优点：
高精度和专业化：Gemini专注于某些特定领域或任务，能够提供更高精度和专业化的回答。
实时更新：可能具有更频繁的知识库更新，能够更好地回答最新事件和动态信息。
改进的上下文处理：在长对话中能够更好地保持上下文，提供更加连贯的回答。
安全和隐私：可能在处理敏感信息时具有更好的隐私保护和安全措施。
缺点：
有限的通用性：由于可能专注于特定领域，Gemini在处理广泛的、非专业化的问题时可能不如ChatGPT-4。
资源和社区支持相对较少：与OpenAI的ChatGPT相比，Gemini的社区资源和支持可能较少。
训练数据量和覆盖面：训练数据的广度可能不如ChatGPT-4，导致在某些冷门话题上的知识储备较少。
综合对比
ChatGPT-4适用于需要广泛知识、通用性强的应用场景，如通用对话、文本生成等。它的优势在于广泛的知识覆盖和强大的社区支持，但在专业领域的精度和实时更新方面略显不足。
Gemini则更适合需要高精度、专业化的场景，尤其是在特定领域的应用中表现突出。其实时更新和改进的上下文处理能力是重要优势，但在处理通用性问题时可能不如ChatGPT-4。
Gemini 和 ChatGPT 3.5 都是功能强大的语言模型，各有优缺点。 选择哪个模型取决于您的具体需求和偏好。
以下是Gemini给出的一些更具体的对比：
特性 Gemini ChatGPT 3.5
训练数据 Google 搜索、维基百科和其他公共数据集 互联网和书籍
擅长领域 回答事实问题、生成不同创意文本格式的文本内容 进行对话、生成创意文本格式的文本内容
访问方式 Google 内部员工 OpenAI API
安全性 经过 Google 内部安全团队审查 尚未经过独立评估
个人认为：谷歌提供独立的服务，感知网速较好。ChatGPT依赖CDN厂商CF进行加速，感知速度较差。
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）