八数码启发式搜索c++代码

### 回答1：
以下是八数码问题的A*算法代码示例，使用了曼哈顿距离作为启发式函数。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5;
int vis[maxn],pre[maxn];
int a[3][3],st,ed;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

struct node
{
    int x[3][3];
    int f,g,h;
    bool operator <(const node& b)const
    {
        return f>b.f;
    }
}now,nex;

int get_dis()
{
    int res=0;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        {
            if(!now.x[i][j])continue;
            res+=abs((now.x[i][j]-1)/3+1-i)+abs((now.x[i][j]-1)%3+1-j);
        }
    return res;
}

void print(int k)
{
    if(!k)return;
    print(pre[k]);
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
            printf("%d ",now.x[i][j]);
        printf("\n");
    }
    printf("\n");
}

int get_hash(node x)
{
    int res=0;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            res=res*10+x.x[i][j];
    return res;
}

void bfs()
{
    priority_queue<node> q;
    q.push(now);
    vis[get_hash(now)]=1;
    pre[get_hash(now)]=-1;
    while(!q.empty())
    {
        now=q.top();
        q.pop();
        if(!get_dis())
        {
            print(get_hash(now));
            return;
        }
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
            {
                if(now.x[i][j])continue;
                for(int k=0;k<4;k++)
                {
                    int nx=i+dx[k],ny=j+dy[k];
                    if(nx<1||nx>3||ny<1||ny>3)continue;
                    nex=now;
                    swap(nex.x[i][j],nex.x[nx][ny]);
                    nex.g++;
                    nex.h=get_dis();
                    nex.f=nex.g+nex.h;
                    int h=get_hash(nex);
                    if(!vis[h])
                    {
                        vis[h]=1;
                        pre[h]=get_hash(now);
                        q.push(nex);
                    }
                }
            }
    }
}

int main()
{
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]==0)
            {
                now.x[i][j]=0;
                st=i,ed=j;
            }
            else now.x[i][j]=a[i][j];
        }
    now.g=0;
    now.h=get_dis();
    now.f=now.g+now.h;
    bfs();
    return 0;
}

### 回答2：
八数码问题是一个经典的搜索问题，主要目标是通过移动数字来达到特定的目标状态。启发式搜索是一种通过有选择性地探索状态空间来寻找最佳解决方案的方法。

基于八数码问题的启发式搜索算法中，可以使用A*算法。A*算法是一种使用启发式函数来评估每个状态的优先级，并根据优先级选择下一个要探索的状态的算法。以下为八数码问题的启发式搜索算法C代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 八数码问题的状态
typedef struct {
    int board[3][3];  // 3x3的棋盘
    int g;  // 路径的实际代价
    int h;  // 启发式估计的代价
} State;

// 初始化状态
void init_state(State* state, int board[3][3]) {
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            state->board[i][j] = board[i][j];
        }
    }
    state->g = 0;
    state->h = 0;
}

// 计算状态的启发式估计代价
void calculate_heuristic(State* state, int target[3][3]) {
    int count = 0;
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            if(state->board[i][j] != target[i][j]) {
                count++;
            }
        }
    }
    state->h = count;
}

// 判断状态是否达到目标状态
bool is_goal_state(State* state, int target[3][3]) {
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            if(state->board[i][j] != target[i][j]) {
                return false;
            }
        }
    }
    return true;
}

// 启发式搜索算法
void heuristic_search(int start[3][3], int target[3][3]) {
    State open_set[100];  // 开放列表，存储待探索的状态
    int open_set_size = 0;
    bool visited[100] = {false};  // 记录已访问过的状态
    State current_state;

    init_state(&current_state, start);
    calculate_heuristic(&current_state, target);

    open_set[open_set_size++] = current_state;
    visited[0] = true;

    while(open_set_size > 0) {
        // 从open_set中选择具有最小f值的状态
        int min_index = 0;
        int min_f = open_set[0].g + open_set[0].h;
        for(int i=1; i<open_set_size; i++) {
            int f = open_set[i].g + open_set[i].h;
            if(f < min_f) {
                min_f = f;
                min_index = i;
            }
        }

        current_state = open_set[min_index];
        visited[min_index] = false;

        if(is_goal_state(&current_state, target)) {
            printf("找到最佳解决方案！");
            return;
        }

        // 扩展当前状态的子状态
        // ...

        // 修改状态的g和h值，并加入open_set中
        // ...

        // 探索子状态，更新open_set和visited
        // ...
    }
    
    printf("未找到最佳解决方案！");
}

int main() {
    int start[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};  // 初始状态
    int target[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};  // 目标状态

    heuristic_search(start, target);

    return 0;
}

以上是一个简单的八数码问题的启发式搜索算法的C代码示例。在实际的算法实现中，还需要扩展当前状态的子状态、修改状态的g和h值，并根据实际情况更新open_set和visited列表。希望这个示例对你理解八数码问题的启发式搜索有所帮助！

### 回答3：
八数码问题是经典的启发式搜索问题，其中八个数字块以3x3的网格形式排列，目标是将这些数字通过移动重新排列成特定的目标状态。启发式搜索算法是一种使用启发函数（heuristic function）来评估当前状态距离目标状态的距离，并选择最有希望的状态来继续搜索的算法。

八数码问题的启发式搜索算法通常使用曼哈顿距离（Manhattan distance）作为启发函数。曼哈顿距离是指每个数字块离其目标位置的横向和纵向的距离之和。算法描述如下：

1. 定义一个优先队列（priority queue），把初始状态放入队列中，并将其曼哈顿距离作为优先级。
2. 重复以下步骤直到找到目标状态或队列为空：
a. 从队列中弹出优先级最高的状态作为当前状态。
b. 如果当前状态是目标状态，则返回解。
c. 根据当前状态生成所有可能的下一状态。
d. 对于每个下一状态，计算其曼哈顿距离，并将其放入队列中。
3. 如果队列为空且没有找到目标状态，则认为问题无解。

此外，为了避免无限循环，还需添加一些额外的控制流程，例如记录已经遍历过的状态，避免重复。

通过以上的算法描述，可以编写相应的C代码实现八数码启发式搜索。该代码将包括状态和封装状态的数据结构、曼哈顿距离的计算函数、生成下一步状态的函数以及主函数，依照以上算法描述实现相应的逻辑即可。

【补充说明】300字的范围有限，以上是对八数码启发式搜索算法的简要描述，实际的代码实现需要更多的细节和逻辑处理，以及数据结构的定义和更全面的测试与优化。