本文目錄一覽：
- 1、求大神改一下這個代碼 回溯法的任務分配問題 用C語言
- 2、用動態規劃做旅行商問題 用C語言 各位大蝦幫幫忙啊
- 3、已知12個地點間的距離，每個地點都要去一次，最後回到起點。求最短距離。TSP旅行商問題。
- 4、什麼是商旅問題啊？用c語言設計，是關於圖的程序。最好能給出代碼
- 5、可運行的c語言程序：旅行商求最短路徑問題
- 6、求大神給這個程序做個詳細的注釋 C語言 回溯法 任務分配問題
求大神改一下這個代碼 回溯法的任務分配問題 用C語言
#include stdio.h
#include string.h
int n, a[21][21], sum, best, b[21], c[21], d[21];
void f(int m) {
int i,j;
if(mn) {
if(best==-1||sumbest)
best=sum;
memcpy(d,c,sizeof(d));
return;
}
for(j=1;j=n;j++) {
if(!b[j]) {
sum+=a[m][j]; b[j]=1;
c[m] = j;
if(sumbest||best==-1)
f(m+1);
sum-=a[m][j]; b[j]=0;
}
}
}
int main() {
int i,j;
printf(“請輸入作業數：”);
scanf(“%d”,n);
printf(“作業分配給不同工人所需費用: “);
for(i=1;i=n;i++)
for(j=1;j=n;j++)
scanf(“%d”,a[i][j]);
sum=0;
best=-1;
f(1);
printf(“最小總費用為：%d\n”, best);
printf(“作業”);
for(i=1;i=n;i++) {
printf(“%3d”, i);
}
printf(“分別分給第”);
for(i=1;i=n;i++) {
printf(“%3d”, d[i]);
}
puts(“個工人！作業分配完畢！”);
return 0;
}
用動態規劃做旅行商問題 用C語言 各位大蝦幫幫忙啊
#include list
#include iostream
using namespace std ;
typedef listint LISTINT;
LISTINT listAnother;
LISTINT list_result;
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}};
int matrix_length=4;
int getPath(int n,LISTINT list_org)
{
// cout”——————-“n”-start——-“endl;
LISTINT::iterator i;
int minValue;
if(n==1){
i=list_org.begin();
minValue= d[*i-1][0];
if(list_org.size()==matrix_length-1){
list_result=list_org;
}
//cout”—“*i”-“”1″”=”minValueendl;
}
else{
int temp;
i=list_org.begin();
temp=*i;
list_org.erase(i);
i=list_org.begin();
minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(list_org.size()==matrix_length-1){
list_result=list_org;
}
/*
cout”—-“temp”–“*(i)”=”minValue”–鏈表裡還剩有如下元素”;
for (i = list_org.begin(); i != list_org.end(); ++i)
cout *i ” “;
cout endl;
*/
for(int j=2;jn;j++)
{
i=list_org.begin();
for(int k=1;kj;k++){
i++;
}
int tempvalue=*i;
list_org.erase(i);
list_org.push_front(tempvalue);
i=list_org.begin();
tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
/*
cout”—-“”—“temp”–“*(i)”=”tempvalue”–所有的”;
for (i = list_org.begin(); i != list_org.end(); ++i)
cout *i ” “;
cout endl;
*/
if(tempvalueminValue){
if(list_org.size()==matrix_length-1){
list_result=list_org;
}
minValue=tempvalue;
}
}
}
//cout”——————-“n”—end—–“endl;
return minValue;
}
int main(int argc, char* argv[])
{
LISTINT list_org;
LISTINT::iterator h;
list_org.push_front(4);
list_org.push_front(3);
list_org.push_front(2);
list_org.push_front(1);
cout”旅行商問題的動態規劃演算法”endl;
cout”路線長度的矩陣表示如下,-1表示無限大”endl;
for(int j=0;jmatrix_length;j++){
coutendl;
for(int k=0;kmatrix_length;k++){
cout” “d[j][k];
}
}
coutendl;
cout”計算結果:”getPath(4,list_org)endl;
list_result.push_front(1);
list_result.push_back(1);
cout”走的路徑:—-:”;
for (h = list_result.begin(); h != list_result.end(); ++h)
cout *h ” “;
cout endl;
int i;
cini;
return 0;
}
已知12個地點間的距離，每個地點都要去一次，最後回到起點。求最短距離。TSP旅行商問題。
這個是NP完全問題，只能求近似解,目前沒有簡單又高效的方法，最簡單的就是窮舉演算法和最鄰近演算法了,其它的可以考慮插入演算法，回溯法，遺傳演算法，蟻群演算法，模擬退火演算法等。。。
什麼是商旅問題啊？用c語言設計，是關於圖的程序。最好能給出代碼
旅行商問題（Traveling Saleman Problem，TSP）又譯為旅行推銷員問題、貨郎擔問題，簡稱為TSP問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點出發，通過所有給定的需求點之後，最後再回到原點的最小路徑成本。字面上的理解是：有一個推銷員，要到n個城市推銷商品，他要找出一個包含所有n個城市的具有最短路程的環路。
解決TSP問題的思想有回溯法、貪心法、動態規劃法等。
如果動態規劃法解決TSP問題，可以參考程序代碼：
#include list
#include iostream
using namespace std ;
typedef listint LISTINT;
LISTINT listAnother;
LISTINT list_result;
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}};
int matrix_length=4;
int getPath(int n,LISTINT list_org)
{
LISTINT::iterator i;
int minValue;
if(n==1)
{
i=list_org.begin();
minValue= d[*i-1][0];
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
}
else
{
int temp;
i=list_org.begin();
temp=*i;
list_org.erase(i);
i=list_org.begin();
minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
for(int j=2;jn;j++)
{
i=list_org.begin();
for(int k=1;kj;k++)
{
i++;
}
int tempvalue=*i;
list_org.erase(i);
list_org.push_front(tempvalue);
i=list_org.begin();
tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(tempvalueminValue)
{
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
minValue=tempvalue;
}
}
}
return minValue;
}
int main(int argc, char* argv[])
{
LISTINT list_org;
LISTINT::iterator h;
list_org.push_front(4);
list_org.push_front(3);
list_org.push_front(2);
list_org.push_front(1);
cout”旅行商問題動態規劃演算法”endl;
cout”路線長度的矩陣表示如下 （-1表示無限大）”endl;
for(int j=0;jmatrix_length;j++){
coutendl;
for(int k=0;kmatrix_length;k++){
cout” “d[j][k];
}
}
coutendl;
cout”計算結果:”getPath(4,list_org)endl;
list_result.push_front(1);
list_result.push_back(1);
cout”要走的路徑:—-:”;
for (h = list_result.begin(); h != list_result.end(); ++h)
cout *h ” “;
cout endl;
int i;
cini;
return 0;
}
可運行的c語言程序：旅行商求最短路徑問題
在無向完全圖中，對於任意兩個頂點vi和vj，我們可以在多項式時間內找到vi和vj這兩個頂點之間的所有路徑，選擇其中路程最短的一條，令S[i,j]表示vi和vj這兩個頂點之間最短距離的那條路徑。搜索路徑S[i,j]，找到vi到達的在S[i,j]上的第一個頂點，記該頂點為vk，將其記錄在數組中R[][]，遞歸查找vi到vk和vk到vj的最短路徑及其相應權值，最後將數組D[]中的頂點和權值之和列印出來即為所求，並用畫圖函數將行經過程畫出。
求大神給這個程序做個詳細的注釋 C語言 回溯法 任務分配問題
這個題目分解一下，就是將n個數據排列組合，數學演算法可以得到種數為A(n,n)=n!
然後在這n!種可能種找到花費最少的那一種就行了。
以下是我寫的程序，驗證了一下，好像沒有什麼問題，你看看。
#include stdio.h
int best,last;
int b[20],c[20],d[20],a[20][20];
void get_best(int n)
{
int j,k;
last = 0;
for(j=0;jn;j++)
last += a[j][c[j]];
if(best == 0)
{
best = last;
for(k=0; kn; k++)
d[k] = c[k];
}
else
{
if(last best)
{
best = last;
for(k=0; kn; k++)
d[k] = c[k];
}
}
}
void f(int n,int count)
{
int i,t,j;
if(n == 1)
{
c[count] = b[0];
get_best(count+1);
}
else
{
for(i=0; in; i++)
{
t = b[i];
b[i] = b[n-1];
b[n-1] = t;
c[count] = t;
f(n-1,count+1);
t = b[i];
b[i] = b[n-1];
b[n-1] = t;
}
}
}
int main()
{
int i,j;
int n;
printf(“請輸入作業數：”);
scanf(“%d”,n);
printf(“作業分配給不同工人所需費用:\n”);
for(i=0;in;i++)
{
b[i] = i;
c[i] = -1;
d[i] = -1;
for(j=0;jn;j++)
scanf(“%d”,a[i][j]);
}
best = last = 0;
f(n,0);
printf(“最小總費用為：%d\n”, best);
for(i=0;in;i++)
{
printf(“第%d人分：”,i+1);
printf(“第%d工作. “, d[i]+1);
printf(“金錢為：%d\n”,a[i][d[i]]);
}
puts(“\n”);
return 0;
}
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/244638.html
微信掃一掃 
支付寶掃一掃 