Unit 3


录音


Text A
BestFirst Search
1. Preamble
This article is about bestfirst search in its general form. There are a number of specific algorithms that follow the basic form of bestfirst search but use more sophisticated evaluation functions. A*search is a popular variant of the bestfirst search. This passage does not discuss A*search or other variants specifically, though the information contained herein is relevant to those search algorithms.

2. Definition
Bestfirst search in its most general form is a simple heuristic search algorithm. ‘Heuristic’ here refers to a general problemsolving rule or set of rules that do not guarantee the best solution or even any solution, but serves as a useful guide for problemsolving. Bestfirst search is a graphbased search algorithm, meaning that the search space can be represented as a series of nodes connected by paths.

3. How It Works
The name ‘bestfirst’ refers to the method of exploring the node with the best ‘score’ first. An evaluation function is used to assign a score to each candidate node. The algorithm maintains two lists, one containing a list of candidates yet to explore (OPEN), and one containing a list of visited nodes (CLOSED). Since all unvisited successor nodes of every visited node are included in the OPEN list, the algorithm is not restricted to only exploring successor nodes of the most recently visited node. In other words, the algorithm always chooses the best of all unvisited nodes that have been graphed, rather than being restricted to only a small subset, such as immediate neighbours. Other search strategies, such as depthfirst and breadthfirst, have this restriction. The advantage of this strategy is that if the algorithm reaches a deadend node, it will continue to try other nodes.




4. Algorithm
Bestfirst search in its most basic form consists of the following algorithm.
The first step is to define the OPEN list with a single node, the starting node. The second step is to check whether or not OPEN is empty. If it is empty, then the algorithm returns failure and exits. The third step is to remove the node with the best score, n, from OPEN and place it in CLOSED. The fourth step ‘expands’ the node n, where expansion is the identification of successor nodes of n. The fifth step then checks each of the successor nodes to see whether or not one of them is the goal node. If any successor is the goal node, the algorithm returns success and the solution, which consists of a path traced backwards from the goal to the start node. Otherwise, the algorithm proceeds to the sixth step. For every successor node, the algorithm applies the evaluation function, f, to it, then checks to see if the node has been in either OPEN or CLOSED. If the node has not been in either, it gets added to OPEN. Finally, the seventh step establishes a looping structure by sending the algorithm back to the second step. This loop will only be broken if the algorithm returns success in step five or failure in step two.
The algorithm is represented here in pseudocode:
（1)  Define a list, OPEN, consisting solely of a single node, the start node, s.
（2)  IF the list is empty, return failure.
（3)  Remove from the list the node n with the best score (the node where f is the minimum), and move it to a list, CLOSED.
（4)  Expand node n.
（5)  IF any successor to n is the goal node, return success and the solution (by tracing the path from the goal node to the start node).
（6)  FOR each successor node:
 Apply the evaluation function, f, to the node.
 IF the node has not been in either list, add it to OPEN.
 Loop structure by sending the algorithm back to the second step.
Pearl adds a third step to the FOR loop that is designed to prevent reexpansion of nodes that have already been visited. This step has been omitted above because it is not common to all bestfirst search algorithms.

5. Evaluation Function
The particular evaluation function used to determine the score of a node is not precisely defined in the above algorithm, because the actual function used is up to the determination of the programmer, and may vary depending on the particularities of the search space. While the evaluation function can determine to a large extent the effectiveness and efficiency of the search, for the purposes of understanding the search algorithm we need not be concerned with the particularities of the function.

6. Applications
Bestfirst search and its more advanced variants have been used in such applications as games and web crawlers. In a web crawler, each web page is treated as a node, and all the hyperlinks on the page are treated as unvisited successor nodes. A crawler that uses bestfirst search generally uses an evaluation function that assigns priority to links based on how closely the contents of their parent page resemble the search query. In games, bestfirst search may be used as a pathfinding algorithm for game characters. For example, it could be used by an enemy agent to find the location of the player in the game world. Some games divide up the terrain into ‘tiles’ which can either be blocked or unblocked. In such cases, the search algorithm treats each tile as a node, with the neighboring unblocked tiles being successor nodes, and the goal node being the destination tile.
  New Words

preamble［prmbl］n.序； 绪言

variant［vernt］n.变体，变种，变异体； 变量

adj.不同的，相异的，不一致的； 多样的； 变异的

discuss［dsks］vt.讨论，谈论； 论述，详述

definition［defnn］n.定义； 解释

rule［rul］n.规则，规定； 统治，支配

vi.控制，支配

guarantee［grnti］n.保证，担保； 保证人，保证书

vt.保证，担保

score［sk］n. & v.得分； 记分

candidate［knddt］n.候选者，候选人

unvisited［nvztd］adj.未访问的

include［nklud］vt.包括，包含

restrict［rstrkt］vt.限制，限定； 约束

immediate［midt］adj.最接近的； 立即的； 直接的

restriction［rstrkn］n.限制，限定

empty［empt］adj.空的

vt.(使)成为空的

failure［felj］n.失败

exit［ekst］n.出口，退出

vi.离开； 退出

remove［rmuv］vt.删除，去除

pseudocode［sjudkd］n.伪代码

solely［sll］adv.唯一地； 仅仅

minimum［mnmm］n.最小量； 极小值

trace［tres］vt.跟踪，追踪； 追溯

prevent［prvent］vt.防止，预防； 阻碍； 阻止

vi.阻止

reexpansion［rikspnn］n.再扩展

omit［umt］vt.省略； 删掉

determine［dtmn］vt.决定，确定

precisely［prsasl］adv.精确地； 恰好地

determination［dtmnen］n.决定，确定

particularity［ptkjulrt］n.特性

extent［kstent］n.程度； 长度

efficiency［fektvns］n.有效性； 有效，有力

crawler［krl］n.爬虫，爬行动物

hyperlink［haplk］n.超链接

resemble［rzembl］vt.与……相似，类似于

query［kwr］v.查询

character［krkt］n.角色，人物； 性格； 特点； 字母

enemy［enm］n.敌军

adj.敌人的； 敌方的

terrain［tren］n.地面，地带

tile［tal］n.片状材料，瓦片，瓷砖

vt.用瓦片、瓷砖等覆盖

destination［destnen］n.目的，目标
 Phrases

refer to涉及； 指的是； 适用于； 参考

general problemsolving rule 普通问题解决规则

graphbased search algorithm基于图的搜索算法

evaluation function评价函数

deadend node死角节点

consist of由……组成； 包括

traced backward追溯

web crawler网络爬虫

web page网页

be treated as被当作

parent page父页面

divide up分割

 Exercises

【Ex.1】根据课文内容回答问题。

1. What is bestfirst search?

2. How many lists does the algorithm maintain? What are they?

3. What is the advantage of this strategy?

4. What is the first step?

5. What does the algorithm return if any successor is the goal node?

6. What does the seventh step do?

7. Why is the particular evaluation function used to determine the score of a node not precisely defined in the above algorithm?

8. What is each web page treated as in a web crawler? And what about the hyperlinks on the page?

9. What may bestfirst search be used as in games?

10. What do some games divide up the terrain into? In such cases, what does the search algorithm do?


【Ex.2】把下列单词或词组中英互译。

1. web crawler1. 

2. web page2. 

3. graphbased search algorithm3. 

4. crawler4. 

5. definition5. 

6. n.超链接6. 

7. n.伪代码7. 

8. v.查询8. 

9. n.限制，限定9. 

10. adv.精确地； 恰好地10. 


【Ex.3】短文翻译。
Hill Climbing
In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is relatively simple to implement, making it a popular first choice. Although more advanced algorithms may give better results, in some situations hill climbing works just as well.
Hill climbing can be used to solve problems that have many solutions, some of which are better than others. It starts with a random (potentially poor) solution, and iteratively makes small changes to the solution, each time improving it a little. When the algorithm cannot see any improvement anymore, it terminates. Ideally, at that point the current solution is close to optimal, but it is not guaranteed that hill climbing will ever come close to the optimal solution.
For example, hill climbing can be applied to the traveling salesman problem. It is easy to find a solution that visits all the cities but will be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much better route is obtained.
Hill climbing is used widely in artificial intelligence. It reaches a goal state from a starting node. 


【Ex.4】将下列词填入适当的位置(每个词只用一次)。






determined
heuristic
memory
advantage
recognition
heuristic
available
optimal
solved
nodes


Beam Search
1. Definition
Beam search is a restricted, or modified, version of either a breadthfirst search or a bestfirst search. It is restricted in the sense that the amount of memory available for storing the set of alternative search1is limited, and in the sense that nonpromising nodes can be pruned at any step in the search. The pruning of nonpromising nodes is2by problemspecific heuristics. The set of most promising, or best alternative, search nodes is called the ‘beam’. Essentially, beam search is a forwardpruning,3search.

2. Search Components and Algorithm
A beam search takes three components as its input: a problem to be4, a set of heuristic rules for pruning, and a memory with a limited5capacity. The problem is the problem to be solved, usually represented as a graph, and contains a set of nodes in which one or more of the nodes represents a goal. The set of6rules are rules specific to the problem domain and prune unfavorable nodes from the memory in respect to the problem domain. The memory is where the ‘beam’ is stored, where when memory is full and a node is to be added to the beam, the most costly node will be deleted, such that the7limit is not exceeded.
3. Advantages, Disadvantages, and Practical Applications
Beam search has the advantage of potentially reducing the computation, and hence the time, of a search. The memory consumption of the search is far less than its underlying search methods. This potential8rests upon the accuracy and effectiveness of the heuristic rules used for pruning, and having such rules can be somewhat difficult due to the expert knowledge required of the problem domain. The main disadvantages of a beam search are that the search may not result in an9goal and may not even reach a goal at all. In fact, the beam search algorithm terminates for two cases: a required goal node is reached, or a goal node is not reached and there are no nodes left to be explored. Beam search has the potential to be incomplete. Despite these disadvantages, beam search has found success in the practical areas of speech10, vision, planning, and machine learning.
Text B
Why AI Needs Security?
Artificial intelligence (AI) is creating new waves of innovation and business models, powered by new technology for deep learning and a massive growth in investment. As AI becomes pervasive in computing applications, highgrade security in all levels of the system is needed. Protecting AI systems, their data, and their communication is critical for users’ safety and privacy, and for protecting businesses’ investments.

1. Where and Why AI Security Is Needed
AI applications built around artificial neural networks operate in two basic stages—training and inference. During the training stage, a neural network ‘learns’ to do a job, such as recognizing faces or street signs. The resulting data set of weights, representing the strength of interaction between the artificial neurons, is used to configure the neural net as a model. In the inference stage, this model is used by the end application to infer information about the data with which it is presented.
The algorithms used in neural net training often process data, such as facial images or fingerprints, which comes from public surveillance, face recognition and fingerprint biometrics, financial or medical applications. This kind of data is usually private and often contains personally identifiable information. Attackers, whether organized crime groups or business competitors, can take advantage of this information to gain economic or other benefits.
AI systems also face the risk of being sent rogue data to disrupt a neural networks functionality. Companies that protect training algorithms and user data will be differentiated in their fields from companies that face the reputational and financial risks of not doing so. Hence, designers must ensure that data is received only from trusted sources and that it is protected during use.
The models themselves, represented by the neuralnet weights that emerge during the training process, are expensive to create and form valuable intellectual property that must be protected against disclosure and misuse. 
Another strong driver for enforcing personal data privacy is the General Data Protection Regulation (GDPR) that came into effect within the European Union on 25 May 2018. This legal framework sets guidelines for the collection and processing of personal information. The GDPR sets out the principles for datamanagement protection and the rights of the individual and large fines may be imposed on businesses that do not comply with the rules.
As data and models move between the network edge and the cloud, communications also need to be secured and authenticated. It is important to ensure that data and/or models are protected and can only be downloaded and communicated from authorized sources to authorized devices.

2. AI Security Solutions
Product security must be incorporated throughout the product lifecycle, from conceptualization to disposal. As new AI applications and use cases emerge, devices that run these applications must be able to adapt to an evolving threat landscape. To meet highgrade protection requirements, security needs to be multifaceted and deeply embedded in everything from edge devices that use neuralnetwork processing systemonchips (SoCs), through the applications that run on them, to communications to the cloud and storage within it.
System designers adding security to their AI products must consider a few foundational functions for enabling security in AI products to protect all phases of operation: offline, during power up, and at runtime, including during communication with other devices or the cloud. Establishing the integrity of the system is essential to creating trust that it is behaving as intended.

2.1Secure Bootstrap
Secure bootstrap, an example of a foundational security function, establishes that the software or firmware of the product is intact. This integrity ensures that when a product is coming out of reset, it does what its manufacturer intended—and not something that a hacker has altered it to do. Secure bootstrap systems use cryptographic signatures on the firmware to determine their authenticity. 

2.2Key Management
The best encryption algorithms can be compromised if the keys are not protected with key management, which is another foundational security function. For highgrade protection, the secret key material should reside inside a hardware root of trust. 

2.3Secure Updates
A third foundational function relates to secure updates. AI applications will continue to get more sophisticated and so data and models will need to be updated continuously. The process of distributing new models securely needs to be protected with endtoend security. Hence it is essential that products can be updated in a trusted way to fix bugs, close vulnerabilities, and evolve product functionality. A flexible, secure update function can even be used to allow postconsumer enablement of optional features of hardware or firmware.

2.4Protecting Data and Coefficients
After addressing foundational security issues, designers must consider how to protect the data and coefficients in their AI systems. Many neural network applications operate on audio, images, video streams, and other realtime data. There are often serious privacy concerns with these large data sets, so it is essential to protect that data when it is in working memory, or stored locally on disk or flash memory systems. 

3. Conclusion
Providers of AI solutions are investing significantly in R&D, and so the neural network algorithms and the models derived from training them need to be properly protected. Concerns about the privacy of personal data, which are already being reflected in the introduction of regulations such as GDPR, also mean that it is increasingly important for companies providing AI solutions to secure them as well as possible.
 New Words

innovation［nven］n.改革，创新； 新观念，新发明

pervasive［pvesv］adj.普遍的； 扩大的

adv.无处不在地； 遍布地

n.无处不在； 遍布

critical［krtkl］adj.关键的； 极重要的

privacy［prvs］n.隐私，秘密

operate［pret］v.运转； 操作； 经营； 管理

stage［sted］n.阶段

configure［knfg］v.配置； 设定

infer［nf］vt.推断； 猜想，推理

vi.作出推论

facial［fel］adj.面部的； 表面的

fingerprint［fgprnt］n.指纹，指印

vt.采指纹

surveillance［svelns］n.监督

biometrics［bametrks］n.生物测定学

identifiable［adentfabl］adj.可辨认的，可识别的

attacker［tk］n.攻击者

competitor［kmpett］n.竞争者； 对手

risk［rsk］n.危险，冒险

vt.冒……的危险

functionality［fknlt］n.功能性

reputational［repjutenl］n.声誉

trusted［trstd］adj.可信的，无错的

weight［wet］n.权重

valuable［vljbl］adj.贵重的，宝贵的； 有价值的

disclosure［dskl］n.泄露，揭露

misuse［msjuz］vt.使用……不当； 滥用

enforce［nfs］vt.实施，执行； 加强

framework［fremwk］n.构架； 框架

guideline［gadlan］n.指导方针； 指导原则

collection［klekn］n.收集，采集

authenticate［entket］vt.认证； 鉴定

ensure［n］vt.确保

download［danld］v.下载

authorize［raz］vt.授权，批准

lifecycle［lafsakl］n.生命周期

disposal［dspzl］n.(事情的)处置； 清理

adj.处理废品的

threat［ret］n.威胁

foundational［fandenl］adj.基本的，基础的

offline［flan］adj.未连线的； 未联机的； 脱机的； 离线的

adv.未连线地； 未联机地； 脱机地； 离线地

establish［stbl］vt.建立，创建

integrity［ntegrt］n.完整，完整性

essential［senl］adj.基本的； 必要的； 本质的

n.必需品； 基本要素

behave［bhev］vi.表现

bootstrap［butstrp］n.引导

firmware［fmwe］n.(计算机的)固件

intact［ntkt］adj.完整无缺的，未受损伤的； 原封不动的； 

reset［riset］vt.重置； 重排； 重新安装

manufacturer［mnjfktr］n.制造商，制造厂

hacker［hk］n.(电脑)黑客

cryptographic［krptgrfk］adj.加密的，用密码写的

authenticity［entst］n.可靠性，确实性，真实性

compromise［kmprmaz］n.损害； 妥协，折中方案

vi.折中解决； 妥协

sophisticated［sfstketd］adj.复杂的； 精致的； 富有经验的

continuously［kntnjsl］adv.连续不断地，接连地

endtoend［endtuend］adj.端到端的，端对端的

vulnerability［vlnrblt］n.弱点

enablement［neblment］n.允许，启动，实现

hardware［hɑdwe］n.计算机硬件

coefficient［kfnt］n.系数

disk［dsk］n.磁盘

reflect［rflekt］v.反映，反射； 考虑

introduction［ntrdkn］n.介绍； 引言，导言

 Phrases

business model企业模型，商业模式

recognizing face识别人脸

street sign街道标志

public surveillance群众监督

face recognition面貌识别

crime group犯罪集团

financial risk财务风险

personal data privacy个人数据隐私

use case用例

adapt to使适应于

power up加电，使启动

fix bug修复错误

video stream视频流

realtime data实时数据

flash memory闪存

derived from...来源于……

 Abbreviations

SoCs (SystemonChips)片载系统

R&D(research and development)科学研究与开发

 Exercises

【Ex.5】根据课文内容填空。

1. AI applications built aroundoperate in two basic stages—training and inference. During the training stage, a neural network ‘learns’ to do a job, such asor.

2. The algorithms used in neural net training often process data, such asor, which comes from, face recognition and fingerprint biometrics,or medical applications. 

3. AI systems also face the risk of being sentto disrupt a neural networks . 

4. As data and models move betweenand, communications also need to be secured and. 

5. To meet highgrade protection requirements, security needs to beandin everything from edge devices that use neuralnetwork processing systemonchips (SoCs), throughthat run on them, to communications toand storage within it.

6. System designers adding security to their AI products must consider a few foundational functions for enabling security in AI products to protect all phases of operation:,, and, including during communication with other devices or the cloud. 

7. Secure bootstrap, an example of a foundational security function, establishes thatorof the product is intact. 

8. For highgrade protection, the secret key material should reside.

9. A flexible, secure update function can even be used to allowof optional features of hardware or firmware.

10. Concerns aboutalso mean that it is increasingly important for companies providing AI solutions to.
Reading
Heuristic Evaluation and Iterated Prisoners Dilemma
1. Heuristic Evaluation
A heuristic evaluation is a process by which an expert evaluates a user interface
user interface： 用户接口，用户界面 or similar system using a list of guidelines. This is not the same as a user evaluation or usability test
usability test： 可用性测试 in which users actually try out the interface. Instead, a predetermined
predetermine ［pridtmn］ v.预定 list of features or aspects of a user interface that are commonly accepted as being beneficial
beneficial ［benfl］ adj.有利的，有益的 is used to evaluate the interface. A heuristic evaluation is typically faster and less expensive than a usability test, though it does have weaknesses and should be used early in development.
There are different ways in which a heuristic evaluation can be conducted, but it typically begins with a list of criteria or features expected of a strong user interface. This list can come from a number of sources, though the first such basic list was created by Jakob Nielsen, and establishes
establish ［stbl］ vt.建立，创建 10 principle design elements that should be included in an interface. Different experts in usability and design can create their own lists, or use these 10 as a starting point for more detailed checklists
checklist ［teklst］ n.清单. When that expert is called upon to perform a heuristic evaluation, he or she uses the checklist to consider the strengths and weaknesses of a system.
A heuristic evaluation is usually conducted by an expert in usability features and interface design, rather than actual test users. The expert looks at the different elements of an interface and evaluates each part of it according to the checklist he or she has created. This can include the use of ‘yes’ or ‘no’ answers to evaluate if certain elements are present in the interface, as well as a numerical scale to indicate the severity of problems or issues found in the heuristic evaluation. The scale allows program developers to easily recognize the nature of a problem and quickly determine if the resources are available to correct it prior to software release
release ［rlis］ vt.发布，发行.
One of the major weaknesses of a heuristic evaluation is that it applies common standards to different types of systems. A feature that may be required in one type of software may be unnecessary
unnecessary ［nnessr］ adj.不必要的，多余的; 无用的 in another; while some features that might be considered poor design for some programs can actually be beneficial in others. Many companies still utilize experts to perform a heuristic evaluation, however, since the process is faster and cheaper than longterm usability testing using large groups of users. Heuristic evaluations are still beneficial, but they should be used early on in the design and development process so that changes suggested by the evaluation can be considered prior to usability testing that often demonstrates
demonstrate ［demnstret］ vt.证明，证实; 论证; 显示 the reality of interface usability.

2. Iterated Prisoners Dilemma

2.1Definition of Iterated Prisoners Dilemma
iterated prisoners dilemma： 迭代囚徒困境
The iterated prisoners dilemma is an extension of the general form except the game is repeatedly played by the same participants. An iterated prisoners dilemma differs from the original concept of a prisoners dilemma because participants can learn about the behavioral tendencies of their counterparty
counterparty ［kantpɑt］ n.对手方.
The iterated prisoners dilemma at times has been called the ‘PeaceWar game’.

2.2Breaking down Iterated Prisoners Dilemma
Since the game is repeated, one individual can formulate a strategy that does not follow the regular logical convention of an isolated round.
‘Tit for tat
tit for tat： 针锋相对; 以牙还牙，一报还一报’ is a common iterated prisoners dilemma strategy.
The iterated prisoners dilemma game is fundamental to many theories of human cooperation
cooperation ［kpren］ n.合作，协作 and trust. Based on the assumption
assumption ［smpn］ n.假定，假设 that the game can model transactions between two people requiring trust, cooperative behavior in populations
population ［ppjulen］ n.人口 may be modeled by a multiplayer, iterated, version of the game.
The theory behind the game has captivated
captivate ［kptvet］ vt.迷住，迷惑 many scholars
scholar ［skl］ n.学者 over the years. More recently, organizational design researchers have used the game to model corporate strategies. The prisoners dilemma is also now commonplace
commonplace ［kmnples］ adj.平凡的，普通的 for game theories are becoming popular with investment strategist. Globalization
globalization ［glblazen］ n.全球化，全球性 and integrated trade have further driven demand for financial and operational models that can describe geopolitical
geopolitical ［dipltkl］ adj.地理政治学的 issues.

2.3Example of the Iterated Prisoners Dilemma Game
For example, you and a colleague are in jail and suspected of committing a crime. You are isolated
isolate ［aslet］ vt.使隔离，使孤立 from each other and do not know how the other will respond to questioning. The police invite both of you to implicate the other in the crime (defect). What happens depends on what both of you do, but neither of you know how the other will respond. If your colleague betrays you (yields to the temptation to defect) while you remain silent
remain silent： 保持沉默，沉默无语, then you receive the longest jail term
jail term： 刑期 while your colleague gets off free (and visa versa). If you both choose to cooperate with each other (not the police) by remaining silent, there is insufficient
insufficient ［nsfnt］ adj.不足的，不够的 evidence
evidence ［evdns］ n.证词，证据 to convict
convict ［knvkt］ vt.宣判有罪n.罪犯 both of you, so you are both given a light sentence for a lesser crime. If both of you decide to defect, you have condemned each other to slightly reduced but still heavy sentences.
The game is played iteratively for a number of rounds until it is ended (as if you are repeatedly
repeatedly ［rpitdl］ adv.反复地，重复地; 屡次地 interrogated
interrogate ［nterget］ vt.审问 for separate crimes). The scores from each round are accumulated, so the object is to optimize the point score before reaching game over. Game over is determined randomly anywhere between 1 and 100 rounds. At the end of the game, the scores are translated into percentages of the best possible scores.

参考译文
最佳优先搜索
1. 序言
本文介绍了最佳优先搜索的一般形式。有许多特定的算法遵循最佳优先搜索的基本形式，却使用更复杂的评估函数。A*搜索是最佳优先搜索的一个流行变体。虽然此处包含的信息与这些搜索算法相关，但本文没有专门讨论A*搜索或其他变体。

2. 定义
最佳优先搜索的最常见形式是简单的启发式搜索算法。这里的“启发式”是指一般的问题解决规则或一组规则，它们不能保证得到最佳解决方案甚至不能保证得到任何解决方案，但可以作为解决问题的有用指南。 最佳优先搜索是基于图的搜索算法，这意味着搜索空间可以表示为由路径连接的一系列节点。

3. 它如何工作
名称“最佳优先”指首先探索具有最佳“得分”的节点的方法。用评估函数为每个候选节点分配分数。该算法含有两个列表，一个列表包含尚待探索的候选节点(OPEN)，另一个列表包含已访问节点(CLOSED)。由于每个访问节点的所有未访问的后继节点都包括在OPEN列表中，因此该算法不限于仅探索最近访问的节点的后继节点。换句话说，该算法总是选择图中所有未访问节点中的最佳节点，而不是仅限于小的子集(例如直接邻居)。其他搜索策略(例如深度优先和广度优先)具有这样的限制。该策略的优点是，如果算法到达死角节点，它将继续尝试其他节点。

4. 算法
最佳优先搜索最基本形式包括以下算法。
第一步是使用单个节点(起始节点)定义OPEN列表。第二步是检查OPEN是否为空。如果它为空，则算法返回失败并退出。第三步是从OPEN中删除具有最高分数n的节点，并将其置于CLOSED中。第四步“扩展”节点n，其中扩展是n的后继节点的标识。然后，第五步检查每个后继节点，以查看它们中的一个是否是目标节点。如果任何后继者是目标节点，则算法返回成功和解决方案，该解决方案包括从目标向后追溯到起始节点的路径。否则，算法前进到第六步。对于每个后继节点，算法将评估函数f应用于它，然后检查节点是否已处于OPEN或CLOSED状态。如果该节点尚未进入任一列表，则会将其添加到OPEN。最后，第七步通过将算法回送到第二步来建立循环结构。如果算法在第五步中返回成功或在第二步中失败，则该循环中断。
这里的算法用伪代码表示为： 
（1) 定义一个列表，OPEN，仅由单个节点(即起始节点)组成。
（2) 如果列表为空，则返回失败。
（3) 从列表中删除具有最佳分数的节点n(f为最小的节点)，并将其移至列表CLOSED。
（4) 展开节点n。
（5) 如果n的任何后继者是目标节点，则返回成功和解决方案(通过跟踪从目标节点到开始节点的路径)。
（6) 对于每个后继节点： 
 将评估函数f应用于节点。
 如果节点未在任何列表中，则将其添加到OPEN。
  通过将算法回送到第二步来建立循环结构。
Pearl为FOR循环添加了第三步，旨在防止重新扩展已经访问过的节点。上面省略了该步骤，因为对于所有最佳优先搜索算法这一步并不常见。
5. 评估函数
用于确定节点得分的特定评估函数在上述算法中没有精确定义，因为所使用的实际函数由程序员确定，并且可以根据搜索空间的特性而变化。虽然评估函数可以在很大程度上确定搜索的有效性和效率，但是为了理解搜索算法，我们不需要关心函数的特性。

6. 应用
最佳搜索及其更高级的变体已用于游戏和网络爬虫等应用程序。在网络爬虫程序中，每个网页都被视为一个节点，页面上的所有超链接都被视为未访问的后继节点。使用最佳优先搜索的网络爬虫程序通常使用评估函数，该函数根据其父页面的内容与搜索查询的相似程度为链接分配优先级。在游戏中，最佳优先搜索可以为游戏角色提供路径搜索算法。例如，对手可以使用它来查找游戏世界中玩家的位置。有些游戏把地形分成可进入或不可进入的区块。在这种情况下，搜索算法将每个区块视为节点，其中相邻的可进入区块是后继节点，并且目标节点是目标区块。