根据所学经典问题：资源分配的特点和描述请自行设计一个实际问题且所设计的实际问题至少能使用分治法、蛮力法、回溯法、分支限界法、贪心法、动态规划法中的三种方法并进行c语言代码实现

实际问题：旅行商问题(TSP)

问题描述：旅行商问题是一个经典的组合优化问题，其目标是找到一条经过所有城市并回到起点的最短路径。假设有n个城市，旅行商需要从其中一个城市出发，经过所有城市恰好一次，最后回到出发的城市。每个城市之间的距离不同，需要找到一条最短的路径。

算法实现：

蛮力法

蛮力法通过枚举所有可能的路径，找到最短的路径。但是，由于旅行商问题的复杂度很高，当城市数量增加时，蛮力法的时间复杂度会呈指数级增长，不适用于大规模问题。

C语言代码实现：

#include<stdio.h>
#include<limits.h>
int main(){
    int n;  //城市数目
    scanf("%d",&n);
    int graph[n][n];  //存储城市之间的距离
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&graph[i][j]);
        }
    }
    int path[n];  //存储路径
    for(int i=0;i<n;i++){
        path[i]=i;
    }
    int min_dist=INT_MAX;  //最小距离
    while(1){
        int dist=0;
        for(int i=0;i<n-1;i++){
            dist+=graph[path[i]][path[i+1]];
        }
        dist+=graph[path[n-1]][path[0]];
        if(dist<min_dist){
            min_dist=dist;
        }
        if(!next_permutation(path,path+n)){
            break;
        }
    }
    printf("%d\n",min_dist);
    return 0;
}

动态规划法

动态规划法通过将问题分解成子问题，并通过子问题的最优解来求解整个问题的最优解。对于旅行商问题，定义状态为f(S,i)，表示经过集合S中的所有城市，最后到达城市i的最短距离。则状态转移方程为：

f(S,i)=min{f(S-{i},j)+dist[j][i]}，其中j∈S且j≠i

C语言代码实现：

#include<stdio.h>
#include<limits.h>
int main(){
    int n;  //城市数目
    scanf("%d",&n);
    int graph[n][n];  //存储城市之间的距离
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&graph[i][j]);
        }
    }
    int dp[1<<n][n];  //状态数组
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            dp[i][j]=INT_MAX;
        }
    }
    for(int i=0;i<n;i++){
        dp[1<<i][i]=0;  //初始状态
    }
    for(int i=1;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                for(int k=0;k<n;k++){
                    if(j!=k&&(i&(1<<k))){
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+graph[k][j]);
                    }
                }
            }
        }
    }
    int min_dist=INT_MAX;  //最小距离
    for(int i=0;i<n;i++){
        min_dist=min(min_dist,dp[(1<<n)-1][i]);
    }
    printf("%d\n",min_dist);
    return 0;
}

分支限界法

分支限界法通过搜索所有可能的路径，并在搜索过程中剪枝，以减少搜索空间。对于旅行商问题，可以使用优先队列来维护当前最优解，每次扩展节点时，计算当前节点的下界，如果下界大于当前最优解，则剪枝。

C语言代码实现：

#include<stdio.h>
#include<limits.h>
#include<stdbool.h>
#define MAXN 20
typedef struct{
    int dist;  //距离
    int path[MAXN];  //路径
    int len;  //路径长度
}Node;
typedef struct{
    Node heap[MAXN*MAXN*MAXN];  //优先队列
    int size;  //队列大小
}PriorityQueue;
bool cmp(Node x,Node y){
    return x.dist<y.dist;
}
void swap(Node *a,Node *b){
    Node temp=*a;
    *a=*b;
    *b=temp;
}
void push(PriorityQueue *q,Node x){
    q->heap[++q->size]=x;  //插入新节点
    int i=q->size;
    while(i>1){
        int j=i/2;
        if(cmp(q->heap[j],q->heap[i])){  //如果父节点比子节点小，则交换
            break;
        }
        swap(&q->heap[i],&q->heap[j]);
        i=j;
    }
}
Node pop(PriorityQueue *q){
    Node res=q->heap[1];  //取出根节点
    q->heap[1]=q->heap[q->size--];  //将最后一个节点放到根节点
    int i=1;
    while(i*2<=q->size){
        int j=i*2;
        if(j+1<=q->size&&cmp(q->heap[j+1],q->heap[j])){
            j++;
        }
        if(cmp(q->heap[i],q->heap[j])){  //如果父节点比子节点小，则交换
            break;
        }
        swap(&q->heap[i],&q->heap[j]);
        i=j;
    }
    return res;
}
int main(){
    int n;  //城市数目
    scanf("%d",&n);
    int graph[n][n];  //存储城市之间的距离
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&graph[i][j]);
        }
    }
    PriorityQueue q={0};  //优先队列
    Node start={0,{},0};  //初始节点
    push(&q,start);
    int min_dist=INT_MAX;  //最小距离
    while(q.size){
        Node cur=pop(&q);  //取出当前节点
        if(cur.len==n){  //找到一条路径
            cur.dist+=graph[cur.path[n-1]][cur.path[0]];
            if(cur.dist<min_dist){
                min_dist=cur.dist;
            }
            continue;
        }
        for(int i=0;i<n;i++){
            if(cur.len==0||!((1<<i)&((1<<n)-1-(1<<cur.path[cur.len-1])))){  //如果该城市未被访问过
                Node next=cur;
                next.dist+=graph[cur.path[cur.len-1]][i];
                next.path[next.len++]=i;
                int lb=next.dist;
                for(int j=0;j<n;j++){
                    if(!((1<<j)&((1<<n)-1-(1<<next.path[next.len-1])))){  //如果该城市未被访问过
                        int min_dist=INT_MAX;
                        for(int k=0;k<n;k++){
                            if(j!=k&&((1<<k)&((1<<n)-1-(1<<next.path[next.len-1])))){  //如果该城市被访问过
                                min_dist=min(min_dist,graph[k][j]);
                            }
                        }
                        lb+=min_dist;
                    }
                }
                if(lb<min_dist){  //如果下界小于当前最优解，则扩展节点
                    push(&q,next);
                }
            }
        }
    }
    printf("%d\n",min_dist);
    return 0;
}
``