人工智能報告

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

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

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