等代价搜索 罗马尼亚度假问题 c语言

以下是一个简单的C语言实现，用等代价搜索解决罗马尼亚度假问题，假设所有的路程都是等代价的：

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

#define MAX_CITY_NUM 20
#define INF 1000000

typedef struct
{
    int weight[MAX_CITY_NUM][MAX_CITY_NUM]; // 权重矩阵
    int city_num; // 城市数量
}Map;

int visited[MAX_CITY_NUM]; // 标记城市是否被访问过
int path[MAX_CITY_NUM]; // 存储路径
int min_cost = INF; // 存储最小花费
int end_city = 5; // 结束城市

void dfs(Map map, int cur_city, int cur_cost, int step)
{
    int i, j;
    path[step] = cur_city;
    visited[cur_city] = 1;
    if (cur_city == end_city)
    {
        if (cur_cost < min_cost)
        {
            min_cost = cur_cost;
        }
        return;
    }
    for (i = 1; i <= map.city_num; i++)
    {
        if (visited[i] == 0 && map.weight[cur_city][i] != INF)
        {
            dfs(map, i, cur_cost + map.weight[cur_city][i], step + 1);
        }
    }
    visited[cur_city] = 0;
}

int main()
{
    Map map;
    int i, j;
    memset(visited, 0, sizeof(visited));
    memset(path, 0, sizeof(path));
    // 初始化地图
    map.city_num = 6;
    for (i = 1; i <= map.city_num; i++)
    {
        for (j = 1; j <= map.city_num; j++)
        {
            map.weight[i][j] = INF;
        }
    }
    map.weight[1][2] = map.weight[2][1] = 71;
    map.weight[1][3] = map.weight[3][1] = 151;
    map.weight[2][4] = map.weight[4][2] = 211;
    map.weight[2][5] = map.weight[5][2] = 101;
    map.weight[3][6] = map.weight[6][3] = 90;
    map.weight[4][5] = map.weight[5][4] = 90;
    map.weight[5][6] = map.weight[6][5] = 85;

    dfs(map, 1, 0, 0);

    printf("The shortest path is: ");
    for (i = 0; i <= map.city_num; i++)
    {
        printf("%d ", path[i]);
    }
    printf("\nThe minimum cost is: %d\n", min_cost);

    return 0;
}

上述代码中，我们使用深度优先搜索算法实现了等代价搜索。该算法通过递归的方式遍历所有的节点，找到最短路径。我们使用一个min_cost变量来存储最小的花费，path数组来存储路径。在搜索过程中，我们使用visited数组来标记哪些城市已经被访问过，防止重复访问。最后输出最短路径和最小花费。