你这基本就是C语言，C++几乎没有。
这个Node类定义得太让人难受，还不如直接用个结构体完事。
【 在 finlab (挨踢卢瑟) 的大作中提到: 】
: 标 题: 数字华容道程序速度快速下降，比C#慢几十倍
: 发信站: 水木社区 (Wed Dec 1 21:22:56 2021), 站内
:
: C++ 当搜索节点数达到几十万后，搜素速度快速下降，处理1000节点的时间是C#的几十倍
: 而C#的速度到接近1000万节点，依然很快。
:
: C++的容器这么差？
:
:
: #ifndef HUARONGDAO_H
: #define HUARONGDAO_H
:
: #include <math.h>
: #include <queue>
: #include <unordered_set>
: #include <iostream>
:
: #include <QtCore>
:
: using namespace std;
:
: #define N 4
: #define L N*N
:
: int buf[L] = {1,5,8,3,2,6,4,15,10,9,12,7,13,14,11,16};
:
: class Node
: {
: public:
: Node* Parent;
:
: int A[L];
: int p;
: int hash,score,gen;
:
: public:
:
: Node() { }
:
: // Parse from string
: Node(const int* a)
: {
: Parent = nullptr;
: gen = 0;
: memcpy(A,a,L*sizeof(int));
:
: for (int i = 0; i < L; i++)
: if (A[i] == L)
: {
: p = i;
: break;
: }
: Hash();
: Score();
: }
: ~Node(){
: // delete A;
: }
:
: // Move
: Node* Move(int d)
: {
: int p2 = p + d;
:
: if (d ==-1 && p%N==0 ) return nullptr; //左右移动后没有出界
: if (d == 1 && p % N == N-1) return nullptr; //左右移动后没有出界
: if (p2 < 0 || p2 >=L) return nullptr; //上下移动后没有出界
:
:
: Node* child = new Node();
: child->Parent = this;
: child->gen = gen+1;
: child->p = p2;
: memcpy(child->A,A,L*sizeof(int));
:
: child->A[p2] = A[p];
: child->A[p] = A[p2];
:
: child->Hash();
: child->Score();
: return child;
: }
:
: bool OK()
: {
: for (int i = 0; i < L; i++)
: if (A[i] != i + 1)
: return false;
: return true;
: }
:
: void Score()
: {
: int r = 0;
: for (int i = 0; i < L ; i++)
: r += abs((A[i]-1)%N - i%N) + 3*abs((A[i]-1)/N-i/N);
:
: //r += SquareSum((A[i] - 1) % N - i % N, (A[i] - 1) / N - i / N);
: //r += (A[i] == i + 1)?0:1;
: score = r;
: }
:
: void Hash()
: {
: hash=0;
: for(int i=0;i<L;++i)
: {
: hash = ((hash<<31) | (hash>>1) )^A[i];
: }
: }
:
: bool Equal(const Node * nd)const
: {
: for(int i=0;i<L;++i)
: if (A[i]!=nd->A[i])
: return false;
: return true;
:
: }
:
:
: void Print()
: {
: for (int i = 0; i < L; ++i)
: {
: if (A[i] == L)
: cout << "\t*";
: else
: cout <<"\t"<<(int)A[i];
: if (i % N == N-1) cout<< endl;
: }
:
: }
: };
:
: typedef Node* PNode;
:
: class Comparer
: {
: public :
: bool operator()(Node * nd1, Node * nd2){ return nd1->score > nd2->score;}
: };
:
:
: class Hasher{
: public:
: size_t operator()( PNode const & node)const {return node->hash;}
: };
:
: class Equal{
: public:
: bool operator()(Node * const& nd1, Node * nd2)const{return nd1->Equal(nd2);}
: };
:
: //------------------------------------------------------------
:
: void Print(Node* node)
: {
: QList<Node*> nodes;
: while (node != nullptr)
: {
: nodes<<node;
: node = node->Parent;
: }
:
: int n= nodes.count();
: for (int i =0;i<n; ++i)
: {
: cout<<i <<"------" <<endl;
: nodes[n-i-1]->Print();
: }
:
: }
:
:
:
: void Go(Node* root)
: {
:
: priority_queue<Node*, vector<Node*>, Comparer> q ;
:
: unordered_set<PNode,Hasher,Equal> hist;
:
: q.push(root);
:
: while (!q.empty())
: {
: Node* node = q.top();
: q.pop();
: hist.insert(node);
: if (hist.size() % 1000 == 0)
: {
: cout<< hist.size() <<"," << node->gen <<" , " << node->score << endl;
: node->Print();
: }
:
: if (node->OK())
: {
: Print(node);
: return;
: }
:
: // if (node->gen>100)
: // continue;
:
: char d[] = {-1, 1, - N, N };
: for (int i = 0; i < 4; ++i)
: {
: Node* child = node->Move(d[i]);
: if (child !=nullptr){
: if (hist.count(child)==0)
: q.push(child);
: else
: delete child;
: }
:
: }
: }
: }
:
:
:
:
: void Run()
: {
: Go(new Node(buf));
:
: }
:
: #endif // HUARONGDAO_H
:
: --
: ※ 修改:·finlab 于 Dec 1 21:46:20 2021 修改本文·[FROM: 123.112.70.*]
: ※ 来源:·水木社区
http://www.mysmth.net·[FROM: 123.112.70.*]
--
修改:finlab FROM 123.112.70.*
FROM 73.15.185.*