算法分析實(shí)驗(yàn)報(bào)告-回溯法

《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告回溯法姓名：XXX專業(yè)班級(jí)：XXX學(xué)號(hào)：XXX指導(dǎo)教師：XXX完成日期：XXX一、試驗(yàn)名稱：回溯法寫出源程序，并編譯運(yùn)行詳細(xì)記錄程序調(diào)試及運(yùn)行結(jié)果二、實(shí)驗(yàn)?zāi)康恼莆栈厮菟惴ㄋ枷胝莆栈厮葸f歸原理了解回溯法典型問題三、實(shí)驗(yàn)內(nèi)容編寫一個(gè)簡(jiǎn)單的程序，解決8皇后問題批處理作業(yè)調(diào)度數(shù)字全排列問題四、算法思想分析編寫一個(gè)簡(jiǎn)單的程序，解決8皇后問題批處理作業(yè)調(diào)度[問題描述]給定n個(gè)作業(yè)的集合J=(J1,J2,…,Jn)。每一個(gè)作業(yè)Ji都有兩項(xiàng)任務(wù)需要分別在2臺(tái)機(jī)器上完成。每一個(gè)作業(yè)必須先由機(jī)器1處理，然后再由機(jī)器2處理。作業(yè)Ji需要機(jī)器i的處理時(shí)間為tji，i=1,2,…,n;j=1,2。對(duì)于一個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器i上完成處理的時(shí)間。則所有作業(yè)在機(jī)器2上完成處理的時(shí)間和成為該作業(yè)調(diào)度的完成時(shí)間和。批處理作業(yè)調(diào)度問題要求對(duì)于給定的n個(gè)作業(yè)，制定一個(gè)最佳的作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。要求輸入：1、作業(yè)數(shù)2、每個(gè)作業(yè)完成時(shí)間表：作業(yè)完成時(shí)間機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323要求輸出：1、最佳完成時(shí)間2、最佳調(diào)度方案提示提示：算法復(fù)雜度為O(n!),建議在測(cè)試的時(shí)候n值不要太大，可以考慮不要超過12。（3）數(shù)字全排列問題：任意給出從1到N的N個(gè)連續(xù)的自然數(shù)，求出這N個(gè)自然數(shù)的各種全排列。如N=3時(shí)，共有以下6種排列方式：123，132，213，231，312，321。注意：數(shù)字不能重復(fù)，N由鍵盤輸入（N<=9）。五、算法源代碼及用戶程序編寫一個(gè)簡(jiǎn)單的程序，解決8皇后問題N皇后問題代碼1：#include<stdio.h>#defineNUM8//定義數(shù)組大小inta[NUM+1];intmain(){ inta[100];intnumber;inti;intk;intflag;intnotfinish=1;intcount=0;i=1;//正在處理的元素下標(biāo)，表示前i－1個(gè)元素已符合要求，正在處理第i個(gè)元素a[1]=1;//為數(shù)組的第一個(gè)元素賦初值printf("Result:\n");while(notfinish)//處理尚未結(jié)束{while(notfinish&&i<=NUM)//處理尚未結(jié)束且還沒處理到第NUM個(gè)元素{for(flag=1,k=1;flag&&k<i;k++)//判斷是否有多個(gè)皇后在同一行{if(a[k]==a[i])flag=0;}for(k=1;flag&&k<i;k++)//判斷是否有多個(gè)皇后在同一對(duì)角線{if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))flag=0;}if(!flag)//若存在矛盾不滿足要求，需要重新設(shè)置第i個(gè)元素{if(a[i]==a[i-1])//若a［i］的值已經(jīng)經(jīng)過一圈追上a［i－1］的值{i--;//退回一步，重新試探處理前的一個(gè)元素if(i>1&&a[i]==NUM){a[i]=1;//當(dāng)a［i］的值為NUM時(shí)將a［i］的值置1}elseif(i==1&&a[i]==NUM){notfinish=0;//當(dāng)?shù)谝晃坏闹颠_(dá)到NUM時(shí)結(jié)束}else{a[i]++;//將a［i］的值取下一個(gè)值}}elseif(a[i]==NUM){a[i]=1;}else{a[i]++;//將a［i］的值取下一個(gè)值}}elseif(++i<=NUM)//第i位已經(jīng)滿足要求則處理第i＋1位{if(a[i-1]==NUM)//若前一個(gè)元素的值為NUM則a[i]＝1{a[i]=1;}else{a[i]=a[i-1]+1;//否則元素的值為前一個(gè)元素的下一個(gè)值}}}if(notfinish){++count;printf((count-1)%3?"[%2d]:":"\n[%2d]:",count);for(k=1;k<=NUM;k++)//輸出結(jié)果{printf("%d",a[k]);}if(a[NUM-1]<NUM)//修改倒數(shù)第二位的值{a[NUM-1]++;}else{a[NUM-1]=1;}i=NUM-1;//開始尋找下一個(gè)滿足條件的解}}//whileprintf("\n");return0;}批處理作業(yè)調(diào)度importjava.util.*;publicclassFlowShop{staticintn;//作業(yè)數(shù)staticintf1;//機(jī)器1完成處理時(shí)間staticintf;//完成時(shí)間和staticintbestf;//當(dāng)前最優(yōu)值staticint[][]m;//各作業(yè)所需要的處理時(shí)間staticint[]x;//當(dāng)前作業(yè)調(diào)度staticint[]bestx;//當(dāng)前最優(yōu)作業(yè)調(diào)度staticint[]f2;//機(jī)器2完成處理時(shí)間publicstaticvoidtrackback(inti){if(i==n){for(intj=0;j<n;j++){bestx[j]=x[j];}bestf=f;}else{for(intj=i;j<n;j++){f1+=m[x[j]][0];if(i>0){f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][1];}else{f2[i]=f1+m[x[j]][1];}f+=f2[i];if(f<bestf){swap(x,i,j);trackback(i+1);swap(x,i,j);}f1-=m[x[j]][0];f-=f2[i];}}}privatestaticvoidswap(int[]x,inti,intj){inttemp=x[i];x[i]=x[j];x[j]=temp;}privatestaticvoidtest(){n=3;int[][]testm={{2,1},{3,1},{2,3}};m=testm;int[]testx={0,1,2};x=testx;bestx=newint[n];f2=newint[n];f1=0;f=0;bestf=Integer.MAX_VALUE;trackback(0);System.out.println(Arrays.toString(bestx));System.out.println(bestf);}publicstaticvoidmain(String[]args){test();System.out.println("HelloWorld!");}}數(shù)字全排列問題#include"stdio.h"#include"conio.h"intnum,cont=0;main(){inti,n,a[30];printf("enterN:");scanf("%d",&num);for(i=1;i<=num;i++)a[i]=i;perm(a,1);printf("\n%d",cont);getch();}intperm(intb[],inti){intk,j,temp;

if(i==num){for(k=1;k<=num;k++)printf("%d",b[k]);printf("\t");cont++;}

elsefor(j=i