資源簡(jiǎn)介

教學(xué)設(shè)計(jì)
課程基本信息
學(xué)科 信息技術(shù) 年級(jí) 高三 學(xué)期 秋季
課題 搜索算法
教學(xué)目標(biāo)
1. 理解廣度優(yōu)先搜索算法的基本思想和基本框架。 2. 熟練應(yīng)用搜索算法求解一些實(shí)際問(wèn)題。
教學(xué)內(nèi)容
教學(xué)重點(diǎn)： 1. 理解廣度優(yōu)先搜索算法的基本思想。
2. 掌握廣度優(yōu)先搜索算法的算法框架。
教學(xué)難點(diǎn)： 1. 理解與體會(huì)搜索算法中的相關(guān)概念。
2. 熟練應(yīng)用搜索算法求解一些實(shí)際問(wèn)題。
教學(xué)過(guò)程
一、開門見(jiàn)山，直接引入 搜索的概念：搜索是計(jì)算機(jī)程序設(shè)計(jì)中一種最基本、最常用的算法。當(dāng)面對(duì)一個(gè)程序設(shè)計(jì)問(wèn)題時(shí)，如果能夠我到數(shù)學(xué)類的方法，如遞推法、構(gòu)造法，或者類似貪心、動(dòng)態(tài)規(guī)劃求最優(yōu)值的方法,那么對(duì)于該題而言,已經(jīng)基本解決。如果沒(méi)有找到行之有效的方法，搜索便成了一個(gè)經(jīng)常性的選擇。 搜索算法是直接基于計(jì)算機(jī)高速運(yùn)算的特點(diǎn)而使用的計(jì)算機(jī)求解方法。它是從問(wèn)題的初始狀態(tài)出發(fā),根據(jù)其中的約束條件，按照一定的策略，有序推進(jìn)，不斷深人，對(duì)于達(dá)到的所有目標(biāo)狀態(tài)(解空間)，一—驗(yàn)證，找到符合條件的解(可行解)，或者找出所有可行解中的最優(yōu)解。按照推進(jìn)的控制策略，搜索一般分為寬度優(yōu)先搜索和深度優(yōu)先搜索。 二、新知講解 廣度優(yōu)先搜索的基本思想：它是從初始結(jié)點(diǎn)開始，應(yīng)用產(chǎn)生式規(guī)則和控制策略生成第一層結(jié)點(diǎn)，同時(shí)檢查目標(biāo)結(jié)點(diǎn)是否在這些生成的結(jié)點(diǎn)中。若沒(méi)有，再用產(chǎn)生式規(guī)則將所有第一層結(jié)點(diǎn)逐一拓展，得到第二層結(jié)點(diǎn)，并逐一檢杳第二層結(jié)點(diǎn)是否包含目標(biāo)結(jié)點(diǎn)。若沒(méi)有，再用產(chǎn)生式規(guī)則拓展第二層結(jié)點(diǎn)。如此依次拓展,檢查下去，直至發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn)為止。如果拓展完所有結(jié)點(diǎn),都沒(méi)有發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn),則問(wèn)題無(wú)解 在搜索的過(guò)程中，廣度優(yōu)先搜索對(duì)于結(jié)點(diǎn)是沿著深度的斷層拓展的。如果要拓展第n+1層結(jié)點(diǎn)，必須先全部拓展完第n層結(jié)點(diǎn)。對(duì)于同一層結(jié)點(diǎn)來(lái)說(shuō),它們對(duì)于問(wèn)題的解的價(jià)值是相同的。所以，這種搜索方法定能保證找到最短的解序列。也就是說(shuō)，第一個(gè)我到的目標(biāo)結(jié)點(diǎn),一定是應(yīng)用產(chǎn)生式規(guī)則最少的。因此，寬度優(yōu)先搜素算法適合求最少步驟或者最短解序列這類最優(yōu)解問(wèn)題。 例題：小華從某起點(diǎn)到某目的地需要經(jīng)過(guò)若干次公交轉(zhuǎn)車（乘車不存在繞圈現(xiàn)象，但不保證可以到達(dá)目的地），顯然換乘公交的方案可能不唯一。如圖所示，小華從起點(diǎn)A到目的地H最少需要轉(zhuǎn)車兩次，公交線路為“A->D->G->H”。 基本框架： def bfs(): while head備注：教學(xué)設(shè)計(jì)應(yīng)至少含教學(xué)目標(biāo)、教學(xué)內(nèi)容、教學(xué)過(guò)程等三個(gè)部分，如有其它內(nèi)容，可自行補(bǔ)充增加。

展開更多......

收起↑