人工智能報(bào)告

1、人工智能課程報(bào)告人工智能課程報(bào)告——推箱子小游戲的人工智能尋路推箱子小游戲的人工智能尋路學(xué)院：學(xué)院：姓名：姓名：學(xué)號：學(xué)號：班級：班級：指導(dǎo)教師：指導(dǎo)教師：推箱子中人的行為推箱子中人的行為人只可以推箱子不可以拉而且一次只能推動一個(gè)。即使是處于目的位置的箱子也可以推走。二基本概念二基本概念啟發(fā)式搜索啟發(fā)式搜索考慮一個(gè)普通的圖搜索問題：給出初始狀態(tài)(節(jié)點(diǎn)s)和目標(biāo)狀態(tài)(節(jié)點(diǎn)t，可以不止一個(gè))以及狀態(tài)的產(chǎn)生規(guī)則，求從s到t的一條路經(jīng)。搜索過程

2、可描述如下：1待展開的節(jié)點(diǎn)集合(OPEN表)為s，已展開的節(jié)點(diǎn)集合(CLOSED表)為，節(jié)點(diǎn)s的層深為g(s)=0。2每次從OPEN表中取出一個(gè)節(jié)點(diǎn)n，根據(jù)規(guī)則擴(kuò)展產(chǎn)生一組節(jié)點(diǎn)mi，然后把n放入CLOSED表中。節(jié)點(diǎn)mi可能屬于下列三種情況之一：（1）新的節(jié)點(diǎn)，則把mi的源標(biāo)記為n，層深g(mi)=g(n)1，并放入OPEN表中。（2）已在OPEN表中存在的節(jié)點(diǎn)，并且層深g(mi)g(n)1，說明從s到mi并且經(jīng)由n的路徑要比先前搜索得

3、到的路徑要短。因此，把mi的源改記為n，層深g(mi)=g(n)1，仍放入OPEN表中。（3）已在CLOSED表中存在的節(jié)點(diǎn)，并且層深g(mi)g(n)1。同理，把mi的源改記為n，層深g(mi)=g(n)1，并從CLOSED表中取出重新放入OPEN表中，留待以后重新搜索計(jì)算mi的子節(jié)點(diǎn)的層深。3不斷重復(fù)上一步操作，直到滿足下列條件之一：（1）n==t，搜索成功。（2）OPEN表為空，搜索失敗。在以上過程中，如何從OPEN表中選取待擴(kuò)展