這幾天在做搜索，看到一篇比較好玩的論文，估價(jià)函數(shù)在信息學(xué)競(jìng)賽中的應(yīng)用。發(fā)現(xiàn)有點(diǎn)難懂。好了，第一道就是uva10605。
題意就不廢話了。這題我剛剛看到作者列舉了下暴力時(shí)候深度為1-17的時(shí)候搜索的次數(shù)，我也很傻很天真的寫(xiě)了個(gè)暴力。我是枚舉不定次數(shù)個(gè)邊界，然后找最小值。程序就一直在那兒搜，還沒(méi)用迭代加深搜索。。。傻傻寫(xiě)了半小時(shí)。結(jié)果這種暴力中的最暴力需要的節(jié)點(diǎn)數(shù)太驚人了。然后就。。卡住了。
果斷搜。沒(méi)人寫(xiě)這個(gè)題的結(jié)題報(bào)告。暈。偶然發(fā)現(xiàn)一個(gè)臺(tái)灣的網(wǎng)站，全死繁體字。找到了UVA10605，發(fā)現(xiàn)就一句話，最小生成樹(shù)變種云云，NPC問(wèn)題。額，沒(méi)任何信息。額，也不是沒(méi)信息！最小生成樹(shù)算法是從每個(gè)節(jié)點(diǎn)開(kāi)始枚舉，對(duì)，每個(gè)節(jié)點(diǎn)。。。額。。。。SB了，這個(gè)題直接暴力的寫(xiě)法應(yīng)該是枚舉N個(gè)金礦，然后搜。
又很傻很天真的寫(xiě)了一次。發(fā)現(xiàn)我寫(xiě)的和作者列舉的生成結(jié)點(diǎn)個(gè)數(shù)差不多，列舉了幾個(gè)答案，也是對(duì)的。枚舉總算沒(méi)問(wèn)題了。精彩的地方還在后面：如何用
啟發(fā)函數(shù)和迭代加深搜索來(lái)解決這個(gè)有最優(yōu)解問(wèn)題。晚上做了另一件事，所以下次再細(xì)看這道題。
晚上突然想到去年十二月份月賽有一道題，鏈接在此，
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1223。這題的意思。。額。。不難懂。以前看這個(gè)題沒(méi)思路，現(xiàn)在看了看，發(fā)現(xiàn)可以暴力一下。這個(gè)題應(yīng)該不是傳統(tǒng)意義上的搜索題，因?yàn)橄拗茥l件比較奇怪：兩條線不能交叉。而且數(shù)據(jù)很大，有100個(gè)點(diǎn)。而且還有無(wú)解情況。無(wú)解現(xiàn)在看來(lái)是沒(méi)辦法預(yù)判的，那么就要搜索所有的可能了。4^100是個(gè)天文數(shù)字。好吧，我沒(méi)有注意到任意兩條線不能相交這個(gè)題目條件，所以寫(xiě)了個(gè)暴力，這個(gè)暴力也不是毫無(wú)價(jià)值，其實(shí)主要是想自己寫(xiě)一個(gè)啟發(fā)函數(shù)試一試，看看能不能對(duì)這個(gè)問(wèn)題進(jìn)行優(yōu)化的。這個(gè)題的啟發(fā)函數(shù)很挫，就是所有的點(diǎn)到它最近的邊的長(zhǎng)度（
最樂(lè)觀的估計(jì)）。然后就沒(méi)有然后了。這個(gè)題描述不清，哎。。TLE，OLE，ＷＡ。。慘不忍睹。
只貼一下uva那個(gè)題的暴力吧，我覺(jué)得寫(xiě)的不算太丑，改天把他A掉。
另外，今天好像到了另外一個(gè)題：這個(gè)題可能比較有意思，也是這個(gè)文章能給別人點(diǎn)啟發(fā)的地方：
去年TX來(lái)中南校招筆試的最后一個(gè)題。我先吐槽下那張卷子：選擇題60分，全是各種操作系統(tǒng)網(wǎng)絡(luò)細(xì)節(jié)，沒(méi)啥意思。TX咋出這樣的題目呢？填空題倒是比較簡(jiǎn)單，但是據(jù)說(shuō)各種坑坑，無(wú)限坑。好吧。就最后一個(gè)比較有意思。題目大意如下：
給定一個(gè)NＸＭ的矩陣，矩陣中三種點(diǎn)：第一種是墻壁，不可以走進(jìn)去；第二種是路，可以走進(jìn)去；第三種是豆豆。題目的問(wèn)題是給定一個(gè)起始點(diǎn)，求吃掉所有豆豆最短的路。
首先的想法就是，暴力。題目中N，M的規(guī)模是1000X1000，還是非常大的。如果直接暴力，肯定掛掉。這個(gè)題LJJ跟我說(shuō)過(guò)，他想把每?jī)蓚€(gè)豆豆的最短路求出來(lái)，這個(gè)不難，而且豆豆小于100，沒(méi)什么問(wèn)題。然后再搜。搜索的時(shí)候，也是A(100,100)，非常大。轉(zhuǎn)化成了一個(gè)求最短哈密頓路徑問(wèn)題。這里可以擴(kuò)展出很多想法，額，還沒(méi)想好。
這個(gè)題是不是能用啟發(fā)函數(shù)做一下呢？首先，題目需要的是最短路徑。接著上面的說(shuō)，求出來(lái)任意兩個(gè)豆豆的最短路之后，實(shí)在想不出啥玩意了。
明天要去實(shí)驗(yàn)室matlab畢設(shè)了。。。這糾結(jié)的搜索。求同行指教。
#include <cstdio>
#include <cstring>
char map[20][20];
int vis[20][20];
class node
{
public:
int x,y;
};
node point[23];
int pcount;
int res;
int N,M;
int val[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int testdata;
int bound(
int x,
int y)
{
if(x<0 || y<0 || x>=N || y>=M)
return 0;
return 1;
}
int min(
int x,
int y)
{
if(x>y)
return y;
return x;
}
int getH()
{
int i,ret = 0;
for(i=0;i<pcount;i++)
{
int x = point[i].x;
int y = point[i].y;
if(!vis[x][y])
{
ret += min(min(x,N-x),min(y,M-y));
}
}
return ret;
}
void dfs(
int step,
int x,
int y,
int next,
int F,
int count,
int maxstep)
{
testdata++;
if(step > maxstep)
return;
if(next == pcount)
{
if(count == pcount && res > step)
{
res = step;
}
return;
}
int i;
if(F == 1)
{
if(!vis[point[next].x][point[next].y])
{
vis[point[next].x][point[next].y] = 1;
dfs(step+1,point[next].x,point[next].y,next+1,0,count+1,maxstep);
vis[point[next].x][point[next].y] = 0;
}
dfs(step,0,0,next+1,1,count,maxstep);
return;
}
else {
for(i=0;i<4;i++)
{
int nx = x + val[i][0];
int ny = y + val[i][1];
if(bound(nx,ny) && !vis[nx][ny])
{
if(map[nx][ny] != '#')
{
vis[nx][ny] = 1;
if(map[nx][ny] == '*')
dfs(step+1,nx,ny,next,0,count+1,maxstep);
else dfs(step+1,nx,ny,next,0,count,maxstep);
vis[nx][ny] = 0;
}
else dfs(step,0,0,next,1,count,maxstep);
}
}
}
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int i,j;
while(scanf("%d%d",&N,&M)!=EOF)
{
pcount = 0;
for(i=0;i<N;i++)
scanf("%s",map[i]);
for(i=0;i<N;i++)
for(j=0;j<M;j++)
if(map[i][j] == '*')
{
node tmp ={i,j};
point[pcount++] = tmp;
}
memset(vis,0,
sizeof(vis));
res = N*M;
testdata = 0;
for(i=1;i<=16;i++)
{
dfs(0,0,0,0,1,0,i);
if(res == i)
{
printf("%d %d\n",res,testdata);
break;
}
}
}
return 0;
}