test_eight.zip_eight

#include <iostream> #define LIST_EMPTY 1 #define OK 0 #define NO 0 #define YES 1 using namespace std; const int sg[9] = { 1, 2, 3, 8, 0, 4, 7, 6, 5 }; const int KT[9] = { 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 }; typedef struct tagNode {//结点 int status[9]; int KTValue; struct tagNode *parent; }Node,*pNode; typedef struct tagList {//表 pNode node; int hValue; struct tagList *next; }List,*pList; int JKT(int *a);//计算康托值函数 int h(const int *s0, const int *sg);//启发函数 void InitList(pList &s); void PushList(pList &s, int h, pNode n);//入表操作 void PopList(pList &s, int &h, pNode &n);//出表操作 int isEmpty(const pList &s);//判断是否为空 int isSuccess(const pList &s);//判断是否找到结果 void Extend(const pNode &s,pList &open);//子结点扩展函数 List* SortLinkList(List* head);//链表排序函数 void swap(int &a, int&b); void Delete(pList &s,int a);//删除某结点 int main() { cout << "请输入初始状态：" << endl; int s0[9]; for (int i = 0; i < 9; i++) { cin >> s0[i]; } pList open, close; InitList(open); InitList(close); pNode s00 = new Node; s00->parent = nullptr; s00->KTValue = JKT(s0); for (int i = 0; i < 9; i++) { s00->status[i] = s0[i]; } PushList(open, h(s0, sg), s00); int cnt = 0; while (!isEmpty(open)) { pNode z; int hh; PopList(open, hh, z); cout << "第" << cnt<< "步移动: " << endl; for (int i = 0; i < 9; i++) { if (i % 3 == 0) cout << endl; cout << z->status[i] << " "; } cout << endl; PushList(close, hh, z); if (isSuccess(close) == YES) { cout << "成功！" << endl; break; } cnt++; Extend(close->next->node, open); open=SortLinkList(open); //删除open表中已遍历的结点 pList q = open->next; int cnt = 2; while (q!= nullptr) { pList k = close->next; while (k != nullptr) { if (q->node->KTValue == k->node->KTValue) { q = q->next; Delete(open, cnt); } k = k->next; } q = q->next; cnt++; } } if (isEmpty(open) == LIST_EMPTY) cout << "失败！" << endl; system("pause"); return 0; } void swap(int &a, int &b) { int c = a; a = b; b = c; } int h(const int *s0, const int *sg) { int cnt = 0; for (int i = 0; i < 9; i++) { if (s0[i] == sg[i]) cnt++; } return 9-cnt; } void InitList(pList &s) { s = new List; s->hValue = -1; s->next = nullptr; s->node = new Node; } void PushList(pList &s, int h, pNode n) { pList p = new List; p->hValue = h; p->node = n; p->next=s->next; s->next = p; } void PopList(pList &s, int &h, pNode &n) { h = s->next->hValue; n = s->next->node; pList p = s->next; s->next = p->next; delete p; } int isEmpty(const pList &s) { if (s->next == nullptr) return LIST_EMPTY; return OK; } int isSuccess(const pList &s) { if (s->next->hValue == 0) return YES; return NO; } void Extend(const pNode &s,pList &open) { int locate = 5; for (int i = 0; i < 9; i++) { if (s->status[i] == 0) locate = i; } if (locate == 10) throw "错误！"; if (locate != 0 && locate != 3 && locate != 6) {//可以左移，则左移生成新结点 int a[9]; for (int k = 0; k < 9; k++) { a[k] = s->status[k]; } swap(a[locate], a[locate - 1]); pNode n = new Node; for (int i = 0; i < 9; i++) { n->status[i] = a[i]; } n->parent = s; n->KTValue = JKT(a); int hh = h(n->status, sg); PushList(open, hh, n); } if (locate != 2 && locate != 5 && locate != 8) {//右 int a[9]; for (int k = 0; k < 9; k++) { a[k] = s->status[k]; } swap(a[locate], a[locate + 1]); pNode n = new Node; for (int i = 0; i < 9; i++) { n->status[i] = a[i]; } n->parent = s; n->KTValue = JKT(a); int hh = h(n->status, sg); PushList(open, hh, n); } if (locate != 0 && locate != 1 && locate != 2) {//上 int a[9]; for (int k = 0; k < 9; k++) { a[k] = s->status[k]; } swap(a[locate], a[locate - 3]); pNode n = new Node; for (int i = 0; i < 9; i++) { n->status[i] = a[i]; } n->parent = s; n->KTValue = JKT(a); int hh = h(n->status, sg); PushList(open, hh, n); } if (locate != 2 && locate != 5 && locate != 8) {//下 int a[9]; for (int k = 0; k < 9; k++) { a[k] = s->status[k]; } swap(a[locate], a[locate + 3]); pNode n = new Node; for (int i = 0; i < 9; i++) { n->status[i] = a[i]; } n->parent = s; n->KTValue = JKT(a); int hh = h(n->status, sg); PushList(open, hh, n); } } List* SortLinkList(List* head) { List* p = NULL; List* pminpre = NULL; List L = { 0, NULL }; List* Ltail = &L; while (NULL != head && NULL != head->next) { pminpre = head; p = head->next; while (NULL != p && NULL != p->next) { if (p->next->hValue < pminpre->next->hValue) pminpre = p; p = p->next; } if (head->hValue <= pminpre->next->hValue) { Ltail = Ltail->next = head; head = head->next; } else { Ltail = Ltail->next = pminpre->next; pminpre->next = pminpre->next->next; } } Ltail = Ltail->next = head; Ltail->next = NULL; return L.next; } int JKT(int *a) { int sum = 0; int Ji = 0; for (int i = 0; i < 9; i++) { Ji = a[i] * KT[i]; sum = sum + Ji; } return sum; } void Delete(pList &s, int a) { int cnt = 1; pList p = s; while (cnt != a-1) { p = p->next; cnt++; } pList q = p->next; p->next = q->next; delete q; }