问题描述
我正在尝试在C中使用BackTracking解决以下问题,但我不知道如何从这里继续...
问题是:克里斯正计划去一个有N个城市的国家旅行。他将从矩阵NxN获得帮助,该单元格(I,J)代表从城市I到城市J的道路长度。
从城市A到城市B的道路长度相比而言并不相同到从城市B到城市A的道路。
从同一来源城市返回到它的路(直接)为0。
克里斯注意到从A到B的最短道路并不总是直接两个城市之间的一个。
您将需要帮助Chris查找最短路径。
编写一个函数,该函数在给定矩阵NxN的情况下检查最短地图,该矩阵存储道路长度的值。
注意:N定义为4。
示例:
从0到3的最短路径1给城市0,然后3,然后给1,如果给定以下矩阵:
0 5 2 2
1 0 1 1
1 2 0 1
1 1 2 0
她的代码:
int ShortestPath(int SourceCity,int DestinationCity,int Distance [] [N ],bool Chosen [] [N])
{
int Path = 0;
if(SourceCity == DestinationCity)
{
Distance [SourceCity] [DestinationCity] = true;
返回0;
}
for(int i = 0; i {
for(int j = 0; j {
路径+ =距离[i] [j];
if(!Chosen [i] [j])
{
Chosen [i] [j] = true;
ShortestPath(i,DestinationCity,Distance,Chosen);
}
}
}
if(Path> = Distance [SourceCity] [DestinationCity])
{
Chosen [SourceCity,DestinationCity] = false;
return Distance [SourceCity] [DestinationCity];
}
}
注意:选择的矩阵表示我是否选择了特定的道路与否(其初始值全为假)
以下是建议的解决方案。这是Dijkstra算法的实现,它找到了最短的路径。
#include< stdio.h>
#include< stdlib.h>
#include< limits.h>
#include< stdbool.h>
//节点数
#define N 4
// d [i] [j]从i到j的距离矩阵
int d [N] [N] = {
{0,5,2,2},
{1,0,1,1},
{1,2,0,1},
{1,1,2,0},
};
// shortestPath使用距离矩阵d在路径中存储从起始节点到
//最终节点的最短路径。它返回路径中
//节点的数量。
int shortestPath(int d [N] [N],int start,int final,int path [N]){
//节点i之前的节点
int prev [N];
//初始化到节点i的距离,开始为无限的
int dist [N];
for(int i = 0; i< N; i ++)
dist [i] = INT_MAX;
dist [start] = 0;
//初始化已完成节点的列表
bool done [N];
for(int i = 0; i< N; i ++)
done [i] = false;
int nDone = 0;
//虽然我们还没有完成所有节点
,但是(nDone< N){
//找到尚未完成的节点,以最小的距离开始节点
int minDist = INT_MAX;
int n; //对于(int i = 0; i< N; i ++)具有最小距离
的节点if(!done [i]&& dist [i]< minDist)
minDist = dist [n = i];
done [n] = true;
nDone ++;
//如果(n == final)
中断,我们可以在完成最后一个节点
后停止。
//对于每个节点j ...
for(int j = 0; j< N; j ++){
//如果节点j尚未完成,
//,如果((done [j]&& dist [j]> dist [n] + d [n] [j ]){
//设置新的最短距离
dist [j] = dist [n] + d [n] [j];
//将节点n设置为节点j之前的节点
prev [j] = n;
}
}
}
//获取路径[start,...,final]
int j = N;
for(int i = final; i!= start; i = prev [i])
path [-j] = i;
path [-j] =开始;
如果(j == 0)
返回N;
int n = N-j;
for(int i = 0; i< n; i ++,j ++)
path [i] = path [j];
返回n;
}
int main(){
int path [N];
int n = shortestPath(d,0,1,path);
printf( path:%d,path [0]);
for(int i = 1; i< n; i ++)
printf(->%d,path [i]);
printf( \n);
返回0;
}
输出
路径:0-> 3-> 1
I am trying to solve the following question using BackTracking in C but I don't know how to continue from here...
The question is:
Chris is planning to travel in a country with N cities. He will get help from a matrix NxN that the cell (I,J) represents the length of the road from city I to City J.The length of the road from City A to city B is not the same when compared to the road from City B to City A.The Road From the same source city back to it (directly) is 0.Chris noticed that the shortest road From A to B isn't alway the direct one between both Cities.You will need to help Chris Finding the shortest path.Write a function that checks for the shortest map given a matrix NxN which stores the values of the roads lengths.Note: N is defined as 4.
Example:
The Shortest path from 0 to 1 is going to City 0 then 3 then 1 if given the following matrix:
0 5 2 2
1 0 1 1
1 2 0 1
1 1 2 0
Her's my code:
int ShortestPath (int SourceCity, int DestinationCity, int Distance [][N], bool Chosen[][N])
{
int Path=0;
if (SourceCity==DestinationCity)
{
Distance[SourceCity][DestinationCity]=true;
return 0;
}
for (int i=0;i<N;i++)
{
for (int j=0;j<N;j++)
{
Path += Distance[i][j];
if (!Chosen[i][j])
{
Chosen[i][j] = true;
ShortestPath(i, DestinationCity, Distance, Chosen);
}
}
}
if (Path>=Distance[SourceCity][DestinationCity])
{
Chosen[SourceCity,DestinationCity]=false;
return Distance[SourceCity][DestinationCity];
}
}
Note: the matrix chosen indicated wether I chose a specific road or not (Its initial values are all false)
Here is a suggested solution. It is an implementation of the Dijkstra algorithm finding the shortest path.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
// number of nodes
#define N 4
// distance matrix from i to j for d[i][j]
int d[N][N] = {
{0, 5, 2, 2},
{1, 0, 1, 1},
{1, 2, 0, 1},
{1, 1, 2, 0},
};
// shortestPath stores in path the shortest path from start node to
// final node using the distance matrix d. It returns the number of
// nodes in the path.
int shortestPath(int d[N][N], int start, int final, int path[N]){
// node previous to node i
int prev[N];
// initialize distance from node i to start as infinite
int dist[N];
for (int i = 0; i < N; i++)
dist[i] = INT_MAX;
dist[start] = 0;
// initialize list of nodes done
bool done[N];
for (int i = 0; i < N; i++)
done[i] = false;
int nDone = 0;
// while we haven’t done all nodes
while (nDone < N) {
// find not yet done node with minimal distance to start node
int minDist = INT_MAX;
int n; // node with minimum distance
for (int i = 0; i < N; i++)
if (!done[i] && dist[i] < minDist)
minDist = dist[n = i];
done[n] = true;
nDone++;
// we can stop when final node is done
if (n == final)
break;
// for every node j...
for (int j = 0; j < N; j++) {
// if node j is not yet done,
// and distance from start to j through n is smaller to known
if (!done[j] && dist[j] > dist[n] + d[n][j]) {
// set new shortest distance
dist[j] = dist[n] + d[n][j];
// set node n as previous to node j
prev[j] = n;
}
}
}
// get path [start, ..., final]
int j = N;
for (int i = final; i != start; i = prev[i])
path[--j] = i;
path[--j] = start;
if (j == 0)
return N;
int n = N-j;
for (int i = 0; i < n; i++, j++)
path[i] = path[j];
return n;
}
int main() {
int path[N];
int n = shortestPath(d, 0, 1, path);
printf("path: %d", path[0]);
for (int i = 1; i < n; i++)
printf("->%d", path[i]);
printf("\n");
return 0;
}
It outputs
path: 0->3->1
这篇关于BackTracking功能无法正常工作的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!