A*是一种带权广度优先的启发算法,很经典的一道题目!
启发函数比较难找,而且,思路比较绕,题目链接!
2472 – Editing a Book
Asia – Kanpur – 2001/2002
 
最后的启发函数:是用后继错误的字符数目[书上的表述有问题,不过牛人写书都是观其大略,能理解]做的,dH<=3,这样,每次的H下降最多为3,为保持f的递增,只有把g函数[每次增加1]强行*3,好了,这样f就是一个递增函数了!
书上说用二叉树作字典,个人认为没有hash的效果好,实验了下,确实如此!当然如果二叉树的节点进行块分配的话,或许要快点,但路径长度的优化,涉及到平衡问题.如果用Treap的实现,递归栈必然会影响其性能.观察下,每个特征字符串长度不大[Color Hash那个长度太大,即使用unsigned __int64也是拼命的冲突],因此hash应该要快点,如果追求性能的话,可以将hash的next节点作块分配,当然这里就不说了[因为CRT和系统的内存分配不一定是连续的,只是C有一次性分配的策略,因此Jon才提出块分配的优化,个人认为看情况了!我这里一个slot的冲突本来就不大,在做块分配逻辑的话,反而在初始时会影响内存分配,所以就没写]
 
T1是待扩展表,T2是判重表[前者用优先队实现,自己用***_heap实现了个,很快15行不到;判重麻烦点,多写了个replace的逻辑],还做了一个对象分配表[这个很重要,程序反复派拨内存对性能影响很大;而且用char代替了int数组,这里要注意cin读入的时候与类型相关,要自己转型!]
 
还有就是这道题目的非常麻烦的地方,如果进行字符串的裁剪,和H函数值计算:
这里用了一个简单的方法:用位图标记连续区域,最优的策略是不会破坏连续区域的,再在做位图的时候,把后继标志记录下来f[value]=i,代表值为value的后继在索引i的位置,其实借用了计数的思路![预处理只需要0(len)].
我花了很长时间研究怎么剪贴,用代码实现:开始是用直观的思路,真的“粘贴复制”,发现很烦,代码写的近似不可读!
其实不用那么复杂,可以用reverse_segment的逻辑,只需要标记边界即可;只是边界也有两种情况,开始写了一种,调试的时候发现老是栈溢出,但看了下分配数远远不到最大值,郁闷了![曾经有冲动想请教高手]仔细一看,原来是忽略了一种情况,sigh!
 
感觉数据量小的时候,c++和c的文件操作时间上差别不大,虽然实际上隐藏的咚咚远远不是时间能衡量的!
 
时间:290MS[gcc]
#include <iostream>
#include <bitset>
#include <fstream>
#include <algorithm>
using namespace std;
//state length
int len=0, index=0;
const int MAX=20;
char input[MAX];//save 3/4
//state type
typedef struct state{
    char* s;
    state* pre;//g,h,f Heuristic;pre
    int g,h,f;
}state;
typedef state* stateptr;
const int MAXHEAP=10000, MAXHASH=10007, MUL=11;
//default strategy for comparsion
int inline cmp(const void* p1, const void* p2){//cast
    return ((stateptr)p1)->f>((stateptr)p2)->f;
}
//simple priority_queue, 18->37lines for priority_queue
class heap{
private:
    int size;
    stateptr _h[MAXHEAP];
public:
    void inti(){//clr heap
        //memset((void*)_h, 0, sizeof(stateptr)*MAXHEAP)
        size=0;
    }
    void push_back(const stateptr p){
        assert(size<MAXHEAP);//heap is less than MAXHEAP threshold
        _h[size++]=p;
        push_heap(_h, _h+size, cmp);
    }
    stateptr pop_front(){
        if(size<=0) return NULL;
        pop_heap(_h, _h+size, cmp),size–;
        return _h[size];//last item
    }
    void replace(const stateptr p){
        for(int i=0;i<size;i++){
            if(memcmp((void*)p->s,(void*)(_h[i]->s),len)==0){
                if(p->f<_h[i]->f) _h[i]->f=p->f;
                return;
            }
        }
    }
    int sz(){return size;}
};
//global heap, for new state
heap h_gT1;
//simple implementation for hash table
typedef struct node{
    unsigned __int64 key;//8bytes
    stateptr s;//4bytes
    node* next;//4bytes
}node;
typedef node* nodeptr;
//simple implemenation for shash, a little too many check for logic for editing book
//70 lines 41->119
class shash{
private:
    nodeptr _bin[MAXHASH];
public:
    void clr(){
        nodeptr nt, pre;
        for(int i=0; i<MAXHASH; i++){
            nt=_bin[i];
            while(nt){pre=nt,nt=nt->next,delete pre;}
        }
    }
    stateptr insert(stateptr ns, int& ret){//must return state pointer!
        if(!ns){ ret=-1; return NULL; }
        unsigned __int64 hKey=0;
        int hEntry=0;
        for(int i=0; i<len; i++) hKey=hKey*MUL+ns->s[i];
        hEntry=hKey%MAXHASH;
        assert(hKey>=0&&hEntry>=0);
        nodeptr nd=_bin[hEntry], newnode, pre=NULL;
        int keycmp=-1;
        for(;nd;pre=nd,nd=nd->next){
            if(hKey<nd->key) continue;
            else if(hKey==nd->key){//hKey==nd->key
                keycmp=memcmp((void*)(nd->s->s), (void*)(ns->s), len);
                if(!keycmp)break;
            }
            else break;
        }
        if(nd&&!keycmp){//replace or not
            if(nd->s->f>ns->f){
                nd->s->f=ns->f; ret=1;return ns;//replace
            }
            ret=-1; return NULL;
        }
        newnode=new node;
        newnode->key=hKey, newnode->s=ns, newnode->next=NULL;
        if(!pre){//pre is NULL
            if(!nd) _bin[hEntry]=newnode;//here severe bugs!
            else _bin[hEntry]=newnode, newnode->next=nd;//here severe bugs!
        }
        else{//pre is null
            if(!nd) pre->next=newnode;
            else pre->next=newnode, newnode->next=nd;
        }
        ret=2;return ns;
    }
    int searchrep(stateptr ns){
        if(!ns) return -1;
        unsigned __int64 hKey=0;
        for(int i=0; i<len; i++) hKey=hKey*MUL+ns->s[i];
        assert(hKey>=0);
        int keycmp=-1;
        nodeptr nd=NULL;//scope checking
        for(nd=_bin[hKey%MAXHASH]; nd; nd=nd->next){
            if(nd->key!=hKey) continue;
            else{
                keycmp=memcmp((void*)(nd->s->s), (void*)(nd->s), len);
                if(!keycmp) break;
            }
        }
        if(nd&&keycmp==0){//equal,replace items in T1 is meanless!so..
            if(nd->s->f>ns->f){
                nd->s->f=ns->f; return 1;//replace
            }
            return 0;//exists
        }
        return -1;//no key
    }
};
//global shash, for existing state
shash h_gT2;
const int MAXSTATE=10000;
class stateBuf{
private:
    state _buf[MAXSTATE];
    char _s[MAXSTATE];
    int top, front;
    int maxtop, maxfront;
public:
    void init(){top=0, front=0,maxtop=0,maxfront=0;}
    stateptr getState(){
        assert(top<MAXSTATE);
        if(top+1>maxtop) maxtop=top+1;
        return _buf + (top++);
    }
    void removeState(){
        top–;
    }
    void removeS(){
        front-=len;
    }
    char* getS(){
        assert(front+len<MAXSTATE);//last index
        if(front+len>maxfront) maxfront=front+len;
        char *tmp=&_s[front]; front+=len;
        return tmp;
    }
    int getMaxTop(){return maxtop;}
    int getMaxFront(){return maxfront;}
};
//global buf for state
stateBuf h_gST;
//backtrack for answer!
void inline print(stateptr cur);
//AStar algorithm
void Astar();
//expand algorithm
void expand(stateptr cur);
//reverse logic
void reverse_l(char* arr, int l, int end);
void inline print(stateptr cur){
    if(!cur) return;
    if(cur->pre) print(cur->pre);
    for(int i=0; i<len; i++) cout<<(int)cur->s[i]<<" ";
    cout<<endl;
}
//A* algorithm : BFS + f fuctions
void Astar(){
    h_gST.init(),h_gT1.inti(), h_gT2.clr();//reset for each case
    int i, ret;
    //intialization
    stateptr ini=h_gST.getState();
    ini->g=0,ini->pre=NULL,ini->s=input;
    for(i=0, ini->h=0; i<len-1; i++)
        if(input[i]!=input[i+1]-1) ini->h++;
    //ini->f function
    ini->f=ini->h;//g is zero starting point!
    h_gT1.push_back(ini),h_gT2.insert(ini, ret);
    assert(ret!=-1);
    bool OK=false; stateptr cur;
    while(!OK&&h_gT1.sz()>0){
        cur=h_gT1.pop_front();
        //check answer
        OK=true;
        for(i=0; i<len-1; i++) OK=OK&&(cur->s[i]==cur->s[i+1]-1);//all true
        if(OK){//print-out all number,backtrack to top
            cout<<index<<" "<<cur->g<<endl;
            print(cur);
            break;
        }
        else expand(cur);
    }
}
//reverse logic
void reverse_l(char* arr, int l, int end){//l,end is boundary index
    for(char *p=arr,*q=arr+end; p<=q; p++,q–)
        if(*p!=*q) *p^=*q,*q^=*p,*p^=*q;
    for(char *p=arr,*q=arr+end-l-1; p<=q; p++,q–)
        if(*p!=*q) *p^=*q,*q^=*p,*p^=*q;
    for(char *p=arr+end-l,*q=arr+end; p<=q; p++,q–)
        if(*p!=*q) *p^=*q,*q^=*p,*p^=*q;
}
//expand algorithm
void expand(stateptr cur){
    char *sp=cur->s;//problem here!how to find next status
    //we shouldn’t cut-off right segment to small pieces
    bitset<64> bt(0x0);//[0…len-1]
    int f[len+1];//f function,continual digital
    int i,start,l;
    for(i=0;i<len;i++){
        f[sp[i]-1]=i;//sp[i]-1 ‘s following item
        assert(sp[i]-1<=len);//keep true
        if(i!=len-1){
            if(sp[i]==sp[i+1]-1) bt.set(i, 1);//right
            else bt.set(i, 0);
        }
    }
    f[len]=len;//last one is invalid
    //status change,copy of status
    for(i=0;i<len;){//find first 0, then next 0
        start=i,l=1;//intial value
        while(bt.test(i)&&i<len) l++,i++;
        if(i==len) break;
        /*logic:generate status*/
        stateptr next=h_gST.getState();
        char* str=h_gST.getS();
        strncpy(str, cur->s, len);//copy to the shadow buffer
        next->g=cur->g+1,next->h=cur->h,next->s=str,next->pre=cur;
        //reverse logic,[i…last-1], the whole length is l-1
        int last=f[(int)str[start+l-1]];//last segment
        /*Heuristic Algorithm for H*/
        if(start>0&&last<len&&str[start-1]==str[last]-1) next->h–;
        if(last>0&&last<len&&str[last-1]==str[start]-1) next->h–;
        if(last<len) next->h–;
        //assert(next->h>=0);//right,keep true
        next->f=next->g*3+next->h;
        /*reverse logic, [start, start+l-1, last-1]*/
        assert(last!=start);//impossible
        if(last>start)//first
            reverse_l(str+start, l-1, last-start-1);//right!
        else
            reverse_l(str+last, start-1-last, start+l-1-last);//based on str+last pointer address
        /*OK checking for last*/
        int sr=h_gT2.searchrep(next);
        if(sr==-1)//new state
            h_gT1.push_back(next);
        else if(sr==1)//existing state, bug may be in T1, replace in T1
            h_gT1.replace(next);
        else //invalid state
            h_gST.removeS(),h_gST.removeState();
        i=start+l;//get next
    }
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in){
        cerr<<"error to open input.txt"<<endl;
        return EXIT_FAILURE;
    }
    cin.rdbuf(in.rdbuf());
    #endif
    int k;
    #ifdef fbase
    while(cin>>index&&index){
        cin>>len;
        for(int i=0;i<len;i++)
            cin>>k,input[i]=k;//int
        Astar();
    }
    #else
    FILE* fp=fopen("input.txt","r");
    if(!fp) return EXIT_FAILURE;
    while(fscanf(fp, "%d", &index)&&index){
        fscanf(fp, "%d", &len);
        for(int i=0;i<len;i++)
            fscanf(fp, "%d\n", &k),input[i]=k;//fscanf is address operation
        Astar();
    }
    #endif
    #ifdef fbase
    in.close();
    #else
    fclose(fp);
    #endif
    return 0;
}
#undef fbase
 
Advertisements