用通俗易懂的方式讲解：2024 检索增强生成技术（RAG）研究进展

2024-01-09 00:52
文章标签 讲解 技术 生成 方式 检索 2024 增强 通俗易懂 rag 研究进展

本文主要是介绍用通俗易懂的方式讲解：2024 检索增强生成技术（RAG）研究进展，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本篇内容1w字左右，稍微有点长，相对不容易理解，喜欢可以收藏、关注、点赞。

一、前言

在过去的一两年里，人工智能领域目睹了检索增强生成技术（RAG）的迅猛发展，这种技术结合了强大的语言模型与信息检索系统，以期在复杂的问题解决和信息处理任务中提供更加精确和深入的答案。正是这种对前沿科技的不懈追求，推动了RAG技术在2023年成为研究的热点。

随着大模型的不断进化，它们在各种任务中的表现已经达到了令人瞩目的水平。然而，无论模型的规模如何增长，它们仍受限于训练数据的质量和范围。RAG技术的出现，正是为了解决这一瓶颈。通过将动态检索过程与生成过程结合，RAG允许模型在生成响应之前，先从一个更广泛、更新的知识源中获取信息。这不仅提升了模型的表现，也极大扩展了其应用范围。

诸如 LangChain 和 LlamaIndex 等工具和框架投入了大量资源来研究和实现RAG技术。它们通过提供高效的检索策略和优化的生成方法，使得RAG不仅在学术界受到青睐，在工业界也逐渐展示出其巨大潜力。尤其是 LlamaIndex 从其官方发布的信息可以了解到2023年其在RAG领域做了不少的研究和探索，且取得了一定的成果。

然而，随着大模型本身的持续进步，一些人开始质疑RAG技术未来的地位。他们认为，如果大模型能够内化足够多的信息并提高内部处理复杂性，那么外部检索可能就不再必要。表面上看这种观点有其合理之处，但它忽视了一个关键因素：知识的动态性。世界在不断变化，信息也在持续更新。RAG技术通过实时检索最新信息保持了模型的时效性和准确性，这是单纯依靠预训练大模型难以实现的。

与传统检索相比，当前 RAG 系统最显著的不同之处在于其组件的灵活性和模块化设计。人们正不断以新颖和创造性的方式将大语言模型与检索结合起来，从而从数据中挖掘出更深层次的洞见。

未来，我们可以预见大模型和RAG技术将会共同进步，并可能融合发展。大模型可能会内置更加高效的检索机制，而RAG技术也会不断优化，使得检索过程更加精准、生成过程更加自然。在某些特定领域，大模型可能会逐渐减少对外部检索的依赖；但在需要处理最新信息或特定领域知识的任务中，RAG仍将是不可或缺的。预计2024年大模型将逐渐会在多模态领域进行深入的研究和突破。

由 Gao 等人撰写的论文《大语言模型的检索增强生成：一项调查》（Retrieval-Augmented Generation for Large Language Models: A Survey）对所有 RAG 研究进行了分类，分为三大类：1) 预训练模型（例如 RETRO），2) 微调加上 RAG（例如 RA-DIT），以及 3) 推理模式中的 RAG（例如 DSP）。

这项调查应该算是目前看到的最全面的研究概览 - 它覆盖了超过 100 篇论文、博客文章和项目，贯穿 RAG 流程的每一个环节：
✅ 检索（数据块分割，查询重写，结果重排，嵌入向量微调）
✅ 生成（文本压缩，内容总结，大语言模型微调）
✅ 能够交织检索与生成的能力（路由选择，HyDE 技术，AI 智能体）

通俗易懂讲解大模型系列

  • 用通俗易懂的方式讲解：如何提升大模型 Agent 的能力?

  • 用通俗易懂的方式讲解：使用 Mistral-7B 和 Langchain 搭建基于PDF文件的聊天机器人

  • 用通俗易懂的方式讲解：ChatGPT 开放的多模态的DALL-E 3功能，好玩到停不下来！

  • 用通俗易懂的方式讲解：结合检索和重排序模型，改善大模型 RAG 效果明显

  • 用通俗易懂的方式讲解：基于扩散模型（Diffusion）,文生图 AnyText 的效果太棒了

  • 用通俗易懂的方式讲解：在 CPU 服务器上部署 ChatGLM3-6B 模型

  • 用通俗易懂的方式讲解：ChatGLM3-6B 功能原理解析

  • 用通俗易懂的方式讲解：使用 LangChain 和大模型生成海报文案

  • 用通俗易懂的方式讲解：一个强大的 LLM 微调工具 LLaMA Factory

  • 用通俗易懂的方式讲解：ChatGLM3-6B 部署指南

  • 用通俗易懂的方式讲解：LangChain Agent 原理解析

  • 用通俗易懂的方式讲解：HugggingFace 推理 API、推理端点和推理空间使用详解

  • 用通俗易懂的方式讲解：使用 LangChain 封装自定义的 LLM，太棒了

  • 用通俗易懂的方式讲解：使用 FastChat 部署 LLM 的体验太爽了

  • 用通俗易懂的方式讲解：基于 Langchain 和 ChatChat 部署本地知识库问答系统

  • 用通俗易懂的方式讲解：使用 Docker 部署大模型的训练环境

  • 用通俗易懂的方式讲解：在 Ubuntu 22 上安装 CUDA、Nvidia 显卡驱动、PyTorch等大模型基础环境

  • 用通俗易懂的方式讲解：Llama2 部署讲解及试用方式

  • 用通俗易懂的方式讲解：LangChain 知识库检索常见问题及解决方案

  • 用通俗易懂的方式讲解：基于 LangChain 和 ChatGLM2 打造自有知识库问答系统

  • 用通俗易懂的方式讲解：代码大模型盘点及优劣分析

  • 用通俗易懂的方式讲解：Prompt 提示词在开发中的使用

  • 用通俗易懂的方式讲解：万字长文带你入门大模型

二、什么是 RAG？

大语言模型（Large Language Models，LLMs）已经成为我们生活和工作中不可或缺的一部分，它们以惊人的多功能性和智能，转变了我们与信息的互动方式。

然而，尽管拥有令人瞩目的能力，这些模型仍存在缺陷。它们可能产生误导性的“幻觉”（hallucinations），依赖潜在的过时信息，处理特定知识时效率不高，专业领域的深度不够，推理能力也有所欠缺。

在真实世界的应用中，数据需要持续更新以反映最新进展，并且生成的内容必须是透明并可追溯的，这对于管理成本和保护数据隐私至关重要。因此，仅依赖这些“黑盒子”模型是不够的；我们需要更精细的解决方案来满足这些复杂的需求。

在这种背景下，检索增强生成（Retrieval-Augmented Generation，RAG） 作为人工智能时代的一项创新趋势，正在受到广泛关注。

在这里插入图片描述

RAG 在问答应用中的一个典型例子是（比如向 ChatGPT 询问关于 OpenAI CEO SAM Altman 被解雇和重新聘用的情况。😆 )

RAG 通过在语言模型生成答案之前，首先从外部数据库检索相关信息，大幅提高了内容的精准度和相关性。

三、RAG 的发展范式

Lewis 在 2020 年提出的 RAG 概念快速演变，经历了研究旅程中的几个不同阶段。起初，研究旨在通过在预训练阶段注入额外知识，来强化语言模型。ChatGPT 的推出极大地促进了对大模型进行深入上下文理解能力的兴趣，并加速了 RAG 在推理阶段的发展。随着研究人员对大语言模型（LLMs）能力的深入挖掘，焦点转向了提升它们的可控性和推理技巧，以满足日益增长的需求。GPT-4 的问世是一个重要里程碑，它采用了一种将 RAG 与微调技术结合的新方法，同时继续优化预训练策略。

在这里插入图片描述

RAG 研究发展历程图谱

我们从技术演变的视角，将 RAG 的发展分为以下几个阶段：

3.1、初级 RAG

经典的 RAG 流程，即初级 RAG，主要包括三个步骤：

  1. 索引 - 将文档分割成短小的片段，并利用编码器建立一个向量索引。

  2. 检索 - 根据问题与这些片段之间的相似度来寻找相关的文档片段。

  3. 生成 - 结合检索到的信息，生成回答问题的内容。

3.2、高级 RAG

初级 RAG 在信息检索、内容生成和信息增强方面存在挑战。为此，高级 RAG 应运而生，它在检索前后加入了额外的处理步骤。在检索前，可以采用查询重写、路径选择和扩展等方法来缩小问题与文档片段之间的语义差异。检索后，对文档进行重新排序，以避免在信息处理中出现信息丢失或上下文信息过于冗长的问题。

3.3、模块化 RAG

随着技术的不断进步，RAG 超越了传统的检索-生成框架，发展出了模块化 RAG。这一结构不仅更加灵活自由，还引入了更多定制化的功能模块，例如查询搜索引擎和多答案整合。技术上，它将信息检索与微调、强化学习等技术相结合。从流程上看，RAG 的各个模块被精心设计和调配，形成了多种RAG模式。

但模块化 RAG 并非一蹴而就；它是在前两个范式基础上逐步演化而来的。高级 RAG 可以看作是模块化 RAG 的一个特殊实例，而初级 RAG 则是高级 RAG 的一个简化版本。

在这里插入图片描述

三种 RAG 范式的对比分析。

四、怎样进行智能增强处理？

想要打造一个出色的 RAG（检索增强生成）系统，关键在于如何巧妙地进行信息增强。在这个过程中，我们需要深思熟虑以下三个问题：

  1. 我们要从海量信息中检索哪些内容？

  2. 我们应该在什么时候进行这样的检索？

  3. 我们如何有效利用检索到的这些内容？

针对这些问题，我们可以将信息增强分为以下几个阶段：

  • 增强的阶段。我们可以在模型的预训练、微调或是实际应用推理时进行信息检索增强，不同阶段对计算资源的需求各不相同，也影响着外部知识如何与模型参数结合。

  • 增强的来源。信息增强可以来源于多种数据形式。非结构化数据可能是文本段落、短语或单词；而结构化数据则可能是已经建立好索引的文档、数据三元组或是数据子图。除了这些外部来源，我们还可以仅依靠大语言模型（LLMs）本身的能力，从模型自己生成的内容中提取信息。

  • 增强的过程。最初，我们可能只做一次简单的检索，但随着技术的进步，我们开始尝试更为复杂的迭代检索、递归检索和自适应检索方法，让模型根据情况自行决定何时进行检索。

在这里插入图片描述

涵盖不同信息增强方面的技术树。

在这里插入图片描述

RAG 系统核心组件详细分类

五、RAG 还是微调？

在大语言模型 (LLM) 的优化策略中，除了 RAG，我们还经常听到提示工程 (Prompt Engineering) 和微调 (Fine-tuning, FT)。这些策略各有千秋，根据对外部知识的依赖程度和模型调整的需要，它们在不同的应用场景下各显神通。

在这里插入图片描述

使用 RAG 就好比给模型配备了一本定制的教科书，它能够针对特定的问题进行精准的信息查找。而微调则像是让模型变成一个学习者，随着时间逐步吸收和内化知识，这使得模型更擅长于复制特定的结构、风格或格式。通过提升模型已有的知识水平、调整其输出结果以及训练它执行复杂的指令，微调能够提高模型的表现力和工作效率。然而，微调不太擅长融入新知识或快速应对新的使用场景。RAG 和微调并不是对立的，它们可以互相补充，在一起使用时可能会带来最好的效果。

在这里插入图片描述

RAG 和微调的比较图表

六、如何评价 RAG 的效果呢？

评估 RAG 的方法多种多样，主要包括三个质量评分：上下文相关性、答案的准确度以及答案的相关性。此外，评估还涉及到四个关键能力：抵抗干扰的能力、拒绝回答不当问题的能力、整合信息的能力、以及在面对假设性情况时保持稳定性的能力。这些评估维度结合了传统的量化指标和专门针对 RAG 特点的评估标准，虽然这些标准还没有统一规定。

在评估框架方面，我们有一些基准测试如 RGB 和 RECALL，还有自动化评估工具如 RAGAS、ARES 和 TruLens，这些工具帮助我们全面地衡量 RAG 模型的性能。

在这里插入图片描述

七、发展前景

随着检索增强生成 (Retrieval-Augmented Generation, RAG) 技术的快速发展，我们面临着一系列值得深入探讨的新问题。我们可以从三个方面来展望这些问题：

7.1、现有挑战

为了进一步解决 RAG 目前面临的挑战，我们考虑如下几个方面：

  • 上下文长度：当检索到的内容过多，超出了模型处理的窗口限制，我们该如何应对？如果大语言模型 (Large Language Model, LLMs) 的上下文窗口不再有限制，我们应该如何优化 RAG？

  • 鲁棒性：面对检索到的不正确内容，我们该如何处理？我们如何过滤和验证检索到的内容？我们能如何提升模型对抗错误信息和噪声的能力？

  • 微调协同：如何同时发挥 RAG 和微调 (Fine-tuning, FT) 的效果？它们之间应该如何协调，是串行、交替还是端到端组织？

  • 规模定律：RAG 模型是否遵循规模定律？在什么情况下，RAG 可能会出现逆规模定律的现象？

  • 大语言模型的角色：LLMs 可以用于检索（用生成替代搜索或搜索 LLMs 的记忆）、生成和评估。我们如何进一步挖掘 LLMs 在 RAG 中的潜力？

  • 生产部署：我们如何减少超大规模语料库的检索延时？我们如何确保 LLMs 检索到的内容不被泄露？

7.2、多模态扩展

RAG 的技术和概念正在不断进化，它们将如何扩展到图像、音频、视频或代码等其他数据形式？一方面，这可以增强单一模态内的任务性能；另一方面，它可以通过 RAG 的思想来实现多模态数据的融合。

7.3、RAG 生态系统

RAG 的应用范围已经不再局限于问答系统，其影响力正在向更广泛的领域扩散。目前，包括推荐系统、信息提取和报告生成在内的多种任务已经开始受益于 RAG 技术的应用。

同时，RAG 技术栈也在迅速壮大。市场上不仅有像 Langchain 和 LlamaIndex 这样的知名工具，还涌现出许多更具针对性的 RAG 工具。这些工具有的为特定用例量身定制，满足更具体的场景需求；有的简化了使用流程，进一步降低了使用门槛；还有的在功能上进行了专业化设计，逐步适应生产环境的需求。

在这里插入图片描述

八、RAG 论文清单

8.1、增强阶段

8.1.1、预训练

  1. 通过检索数万亿 Token (Token) 来改善语言模型

    https://arxiv.org/abs/2112.04426

  2. 少样本学习借助检索增强型语言模型

    https://arxiv.org/pdf/2208.03299.pdf

  3. Toolformer: 语言模型自学使用工具

    https://arxiv.org/abs/2302.04761

  4. 一切只需复制

    https://openreview.net/pdf?id=CROlOA9Nd8C

  5. 结合检索增强的编解码器进行上下文学习

    https://arxiv.org/abs/2308.07922

  6. 我们是否应该通过检索来预训练自回归语言模型？

    https://arxiv.org/abs/2304.06762

  7. 展示-搜索-预测: 融合检索与语言模型，用于知识密集型自然语言处理

    https://arxiv.org/abs/2212.14024

8.1.2、微调

  1. 密集通道检索在开放域问答中的应用

    https://arxiv.org/abs/2004.04906

  2. UPRISE: 通用提示检索助力零样本评估提升

    https://arxiv.org/abs/2303.08518

    https://github.com/microsoft/LMOps

  3. 问答系统中从阅读器到检索器的知识转移

    https://arxiv.org/abs/2012.04584

  4. RA-DIT: 检索增强双指令微调

    https://arxiv.org/abs/2310.01352

  5. Self-RAG: 自我反思学习检索、生成及评价

    https://arxiv.org/abs/2310.11511

  6. 知识图谱增强的语言模型，用于生成知识驱动对话

    https://arxiv.org/abs/2305.18846

  7. 结构感知预训练语言模型，提高结构化数据的密集检索性

    https://aclanthology.org/2023.findings-acl.734.pdf

    https://github.com/OpenMatch/SANTA

  8. Replug: 检索增强的黑盒语言模型

    https://arxiv.org/pdf/2301.12652.pdf

  9. 适应性增强检索器，提升语言模型作为泛用插件的泛化能力

    https://arxiv.org/abs/2305.17331

    https://github.com/OpenMatch/Augmentation-Adapted-Retriever

8.1.3、推理

  1. 通过记忆实现泛化：最近邻居语言模型

    https://arxiv.org/abs/1911.00172

  2. 展示-搜索-预测: 融合检索与语言模型，用于知识密集型自然语言处理

    https://arxiv.org/abs/2212.14024

    https://github.com/stanfordnlp/dspy

  3. 关键词增强检索: 结合语音接口的信息检索新框架

    https://arxiv.org/abs/2310.04205

  4. 在多步骤问题解答中交错使用检索与链式思考推理

    https://arxiv.org/pdf/2212.10509.pdf

    https://github.com/stonybrooknlp/ircot

  5. 直接生成：大语言模型 (Large Language Model) 作为出色的上下文生成器

    https://arxiv.org/abs/2209.10063

    https://github.com/wyu97/GenRead

  6. 上下文中使用检索增强的语言模型

    https://arxiv.org/abs/2302.00083

8.2、增强来源

8.2.1、非结构化数据

  1. UPRISE: 通用提示检索助力零样本评估提升

    https://arxiv.org/abs/2303.08518

    https://github.com/microsoft/LMOps

  2. 从分类到生成：洞察跨语言检索增强互动式上下文学习 (ICL)

    https://arxiv.org/abs/2311.06595

  3. 简单复制即可

    https://openreview.net/pdf?id=CROlOA9Nd8C

8.2.2、结构化数据

  1. FABULA: 利用检索增强的叙事技术生成情报报告

    https://arxiv.org/abs/2310.13848

  2. 知识图谱辅助的语言模型：用于生成知识驱动的对话

    https://arxiv.org/abs/2305.18846

  3. KnowledGPT: 结合知识库的检索和存储访问来提升大语言模

    https://arxiv.org/abs/2308.11761

  4. Graph-ToolFormer: 利用 ChatGPT 增强提示来提升大语言模型的图形推理能力

    https://arxiv.org/abs/2304.11116

8.2.3、LLM 生成内容

  1. 自我提升：带有记忆功能的检索增强文本生成技术

    https://arxiv.org/abs/2305.02437

  2. 展示—搜索—预测：结合检索与语言模型技术，面向知识密集型自然语言处理任务

    https://arxiv.org/abs/2212.14024

  3. Recitation-augmented 语言模型

    https://arxiv.org/pdf/2210.01296.pdf

  4. 生成胜于检索：大语言模型作为强大的上下文生成器

    https://arxiv.org/abs/2209.10063

  5. 自我知识引导的检索增强技术，用于提升大语言模型

    https://arxiv.org/abs/2310.05002

8.3、增强过程

8.3.1、一次性检索

  1. 面向知识密集型自然语言处理任务的检索增强生成方法

    https://proceedings.neurips.cc/paper/2020/hash/6b493230205f780e1bc26945df7481e5-Abstract.html

  2. UPRISE: 通用提示式检索改善零样本评估技术

    https://arxiv.org/abs/2303.08518

  3. 带参数化知识引导的大语言模型增强技术

    https://arxiv.org/abs/2305.04757

  4. 学习为大语言模型检索上下文示例的方法

    https://arxiv.org/pdf/2307.07164.pdf

  5. 使用检索增强的少样本学习语言模型

    https://arxiv.org/pdf/2208.03299.pdf

  6. Replug: 检索增强的黑箱式语言模型

    https://arxiv.org/pdf/2301.12652.pdf

  7. 背诵增强式语言模型

    https://arxiv.org/pdf/2210.01296.pdf

8.3.2、迭代检索

  1. 展示—搜索—预测：结合检索与语言模型技术，面向知识密集型自然语言处理任务

    https://arxiv.org/abs/2212.14024

    https://github.com/stanfordnlp/dspy

  2. 检索与抽样：结合混合检索增强技术进行文档级事件参数提取

    https://aclanthology.org/2023.acl-long.17/

  3. 通过迭代检索与生成的协同作用来增强大语言模型的检索能力

    https://arxiv.org/abs/2305.15294

  4. 检索-生成协同作用下的大语言模型增强方法

    https://arxiv.org/abs/2310.05149

8.3.3、递归式检索

  1. 结合思维链条推理与信息检索，解答知识密集型多步骤问题

    https://arxiv.org/abs/2212.10509

    https://github.com/stonybrooknlp/ircot

  2. 采用检索增强型大语言模型 (LLM) 解开含糊问题的迷雾

    https://arxiv.org/abs/2310.14696

8.3.4、自适应检索

  1. 主动式检索增强生成技术

    https://arxiv.org/abs/2305.06983

    https://github.com/jzbjyb/FLARE

  2. 自我RAG：自省中学习检索、生成及评判的艺术

    https://arxiv.org/abs/2310.11511

  3. 结合检索功能的编解码器语言模型上下文学习方法

    https://arxiv.org/abs/2308.07922

九、References

[1]. Retrieval-Augmented Generation for Large Language Models: A Survey”Gao, Yunfan, et al. 2023

https://arxiv.org/pdf/2312.10997.pdf

这篇关于用通俗易懂的方式讲解：2024 检索增强生成技术（RAG）研究进展的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/585426。

相关文章

AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源：安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供，流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材，流动式起重机司机大纲整理而成（含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析），掌握本资料和学校方法，考试容易。流动式起重机司机考试技
阅读更多...
【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
高效录音转文字：2024年四大工具精选！

高效录音转文字：2024年四大工具精选！

在快节奏的工作生活中，能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候，一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具！ 365在线转文字 直达链接：https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具，它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件，只
阅读更多...
内核启动时减少log的方式

内核启动时减少log的方式

内核引导选项 内核引导选项大体上可以分为两类：一类与设备无关、另一类与设备有关。与设备有关的引导选项多如牛毛，需要你自己阅读内核中的相应驱动程序源码以获取其能够接受的引导选项。比如，如果你想知道可以向 AHA1542 SCSI 驱动程序传递哪些引导选项，那么就查看 drivers/scsi/aha1542.c 文件，一般在前面 100 行注释里就可以找到所接受的引导选项说明。大多数选项是通过"_
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
poj 1287 Networking（prim or kruscal最小生成树）

poj 1287 Networking（prim or kruscal最小生成树）

题意给你点与点间距离，求最小生成树。 注意点是，两点之间可能有不同的路，输入的时候选择最小的，和之前有道最短路WA的题目类似。 prim代码： #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];
阅读更多...
poj 2349 Arctic Network uva 10369（prim or kruscal最小生成树）

poj 2349 Arctic Network uva 10369（prim or kruscal最小生成树）

题目很麻烦，因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚，不适合新手。自己写一个。 题意：给你点的坐标，然后两点间可以有两种方式来通信：第一种是卫星通信，第二种是无线电通信。 卫星通信：任何两个有卫星频道的点间都可以直接建立连接，与点间的距离无关； 无线电通信：两个点之间的距离不能超过D，无线电收发器的功率越大，D越大，越昂贵。 计算无线电收发器D
阅读更多...
hdu 1102 uva 10397（最小生成树prim）

hdu 1102 uva 10397（最小生成树prim）

hdu 1102: 题意： 给一个邻接矩阵，给一些村庄间已经修的路，问最小生成树。 解析： 把已经修的路的权值改为0，套个prim（）。 注意prim 最外层循坏为n-1。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2