matlab貪婪演算法tsp實例

1. 遺傳演算法求解tsp問題的matlab程序

把下面的（1）-（7）依次存成相應的.m文件，在（7）的m文件下運行就可以了
（1） 適應度函數fit.m
function fitness=fit(len,m,maxlen,minlen)
fitness=len;
for i=1:length(len)
fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001)).^m;
end
(2)個體距離計算函數 mylength.m
function len=myLength(D,p)
[N,NN]=size(D);
len=D(p(1,N),p(1,1));
for i=1:(N-1)
len=len+D(p(1,i),p(1,i+1));
end

end
(3)交叉操作函數 cross.m
function [A,B]=cross(A,B)
L=length(A);
if L<10
W=L;
elseif ((L/10)-floor(L/10))>=rand&&L>10
W=ceil(L/10)+8;
else
W=floor(L/10)+8;
end
p=unidrnd(L-W+1);
fprintf('p=%d ',p);
for i=1:W
x=find(A==B(1,p+i-1));
y=find(B==A(1,p+i-1));
[A(1,p+i-1),B(1,p+i-1)]=exchange(A(1,p+i-1),B(1,p+i-1));
[A(1,x),B(1,y)]=exchange(A(1,x),B(1,y));
end

end
(4)對調函數 exchange.m
function [x,y]=exchange(x,y)
temp=x;
x=y;
y=temp;

end
(5)變異函數 Mutation.m
function a=Mutation(A)
index1=0;index2=0;
nnper=randperm(size(A,2));
index1=nnper(1);
index2=nnper(2);
%fprintf('index1=%d ',index1);
%fprintf('index2=%d ',index2);

temp=0;
temp=A(index1);
A(index1)=A(index2);
A(index2)=temp;
a=A;
end
(6)連點畫圖函數 plot_route.m
function plot_route(a,R)
scatter(a(:,1),a(:,2),'rx');
hold on;
plot([a(R(1),1),a(R(length(R)),1)],[a(R(1),2),a(R(length(R)),2)]);
hold on;
for i=2:length(R)
x0=a(R(i-1),1);
y0=a(R(i-1),2);
x1=a(R(i),1);
y1=a(R(i),2);
xx=[x0,x1];
yy=[y0,y1];
plot(xx,yy);
hold on;
end

end
(7)主函數
clear;
clc;
%%%%%%%%%%%%%%%輸入參數%%%%%%%%
N=50; %%城市的個數
M=100; %%種群的個數
C=100; %%迭代次數
C_old=C;
m=2; %%適應值歸一化淘汰加速指數
Pc=0.4; %%交叉概率
Pmutation=0.2; %%變異概率
%%生成城市的坐標
pos=randn(N,2);
%%生成城市之間距離矩陣
D=zeros(N,N);
for i=1:N
for j=i+1:N
dis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2;
D(i,j)=dis^(0.5);
D(j,i)=D(i,j);
end
end
%%如果城市之間的距離矩陣已知，可以在下面賦值給D，否則就隨機生成

%%生成初始群體
popm=zeros(M,N);
for i=1:M
popm(i,:)=randperm(N);
end
%%隨機選擇一個種群
R=popm(1,:);

figure(1);
scatter(pos(:,1),pos(:,2),'rx');
axis([-3 3 -3 3]);
figure(2);
plot_route(pos,R); %%畫出種群各城市之間的連線
axis([-3 3 -3 3]);
%%初始化種群及其適應函數
fitness=zeros(M,1);
len=zeros(M,1);
for i=1:M
len(i,1)=myLength(D,popm(i,:));
end
maxlen=max(len);
minlen=min(len);
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);
R=popm(rr(1,1),:);
for i=1:N
fprintf('%d ',R(i));
end
fprintf('\n');
fitness=fitness/sum(fitness);

distance_min=zeros(C+1,1); %%各次迭代的最小的種群的距離
while C>=0
fprintf('迭代第%d次\n',C);
%%選擇操作
nn=0;
for i=1:size(popm,1)
len_1(i,1)=myLength(D,popm(i,:));
jc=rand*0.3;
for j=1:size(popm,1)
if fitness(j,1)>=jc
nn=nn+1;
popm_sel(nn,:)=popm(j,:);
break;
end
end
end
%%每次選擇都保存最優的種群
popm_sel=popm_sel(1:nn,:);
[len_m len_index]=min(len_1);
popm_sel=[popm_sel;popm(len_index,:)];

%%交叉操作
nnper=randperm(nn);
A=popm_sel(nnper(1),:);
B=popm_sel(nnper(2),:);
for i=1:nn*Pc
[A,B]=cross(A,B);
popm_sel(nnper(1),:)=A;
popm_sel(nnper(2),:)=B;
end
%%變異操作
for i=1:nn
pick=rand;
while pick==0
pick=rand;
end
if pick<=Pmutation
popm_sel(i,:)=Mutation(popm_sel(i,:));
end
end
%%求適應度函數
NN=size(popm_sel,1);
len=zeros(NN,1);
for i=1:NN
len(i,1)=myLength(D,popm_sel(i,:));
end
maxlen=max(len);
minlen=min(len);
distance_min(C+1,1)=minlen;
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);
fprintf('minlen=%d\n',minlen);
R=popm_sel(rr(1,1),:);
for i=1:N
fprintf('%d ',R(i));
end
fprintf('\n');
popm=[];
popm=popm_sel;
C=C-1;
%pause(1);
end
figure(3)
plot_route(pos,R);
axis([-3 3 -3 3]);

2. 貪婪演算法幾個經典例子

問題一：貪心演算法的例題分析 例題1、[0-1背包問題]有一個背包，背包容量是M=150。有7個物品，物品不可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。物品 A B C D E F G重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg價值 10$ 40$ 30$ 50$ 35$ 40$ 30$分析：目標函數：∑pi最大約束條件是裝入的物品總重量不超過背包容量：∑wi 64輸出一個解，返回上一步驟c--（x,y) ← c計算(x,y）的八個方位的子結點，選出那些可行的子結點循環遍歷所有可行子結點，步驟c++重復2顯然⑵是一個遞歸調用的過程，大致如下：C++程序： #define N 8void dfs(int x,int y,int count){ int i,tx,ty; if(count>N*N) { output_solution();輸出一個解 return; } for(i=0; i>

問題二：收集各類貪心演算法（C語言編程）經典題目 tieba./...&tb=on網路的C語言貼吧。 全都是關於C的東西。

問題三：幾種經典演算法回顧 今天無意中從箱子里發現了大學時學演算法的教材《演算法設計與分析》，雖然工作這么幾年沒在什麼地方用過演算法，但演算法的思想還是影響深刻的，可以在系統設計時提供一些思路。大致翻了翻，重溫了一下幾種幾種經典的演算法，做一下小結。分治法動態規劃貪心演算法回溯法分支限界法分治法1）基本思想將一個問題分解為多個規模較小的子問題，這些子問題互相獨立並與原問題解決方法相同。遞歸解這些子問題，然後將這各子問題的解合並得到原問題的解。2）適用問題的特徵該問題的規模縮小到一定的程度就可以容易地解決該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題3）關鍵如何將問題分解為規模較小並且解決方法相同的問題分解的粒度4）步驟分解->遞歸求解->合並 divide-and-conquer(P) { if ( | P | >

問題四：求三四個貪心演算法的例題（配源程序代碼，要帶說明解釋的）！非常感謝 貪心演算法的名詞解釋
ke./view/298415
第一個貪心演算法 （最小生成樹）
ke./view/288214
第二個貪心演算法 （Prim演算法）
ke./view/671819
第三個貪心演算法 （kruskal演算法）
ke./view/247951
演算法都有詳細解釋的

問題五：求 Java 一些經典例子演算法 前n項階乘分之一的和
public class jiecheng {
public static void main(String[] args)
{
double sum=0;
double j=1;
int n=10;
for(int i=1;i 問題六：關於編程的貪心法 定義
所謂貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。 貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。
[編輯本段]貪心演算法的基本思路
1.建立數學模型來描述問題。 2.把求解的問題分成若干個子問題。 3.對每一子問題求解，得到子問題的局部最優解。 4.把子問題的解局部最優解合成原來解問題的一個解。 實現該演算法的過程： 從問題的某一初始解出發； while 能朝給定總目標前進一步 do 求出可行解的一個解元素； 由所有解元素組合成問題的一個可行解。 下面是一個可以試用貪心演算法解的題目，貪心解的確不錯，可惜不是最優解。
[編輯本段]例題分析
[背包問題]有一個背包，背包容量是M=150。有7個物品，物品不可以分割成任意大小。 要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 價值 10 40 30 50 35 40 30 分析： 目標函數： ∑pi最大 約束條件是裝入的物品總重量不超過背包容量：∑wi>

問題七：求解一貪心演算法問題 最快回答那個不懂別亂說，別誤人子弟。
這題標準的貪心演算法，甚至很多時候被當做貪心例題
要求平均等待時間，那麼就得用 總等待時間 / 人數
所以只用關心總等待時間，
如果數據大的在前面，那麼後面必然都要加一次這個時間，所以按從小到大排。
給你寫了個，自己看吧。
#include stdafx.h
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin >> n;
for(int i = 0; i > arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i 問題八：分治演算法的應用實例 下面通過實例加以說明： 給你一個裝有1 6個硬幣的袋子。1 6個硬幣中有一個是偽造的，並且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。為了幫助你完成這一任務，將提供一台可用來比較兩組硬幣重量的儀器，利用這台儀器，可以知道兩組硬幣的重量是否相同。比較硬幣1與硬幣2的重量。假如硬幣1比硬幣2輕，則硬幣1是偽造的；假如硬幣2比硬幣1輕，則硬幣2是偽造的。這樣就完成了任務。假如兩硬幣重量相等，則比較硬幣3和硬幣4。同樣，假如有一個硬幣輕一些，則尋找偽幣的任務完成。假如兩硬幣重量相等，則繼續比較硬幣5和硬幣6。按照這種方式，可以最多通過8次比較來判斷偽幣的存在並找出這一偽幣。另外一種方法就是利用分而治之方法。假如把1 6硬幣的例子看成一個大的問題。第一步，把這一問題分成兩個小問題。隨機選擇8個硬幣作為第一組稱為A組，剩下的8個硬幣作為第二組稱為B組。這樣，就把1 6個硬幣的問題分成兩個8硬幣的問題來解決。第二步，判斷A和B組中是否有偽幣。可以利用儀器來比較A組硬幣和B組硬幣的重量。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量不相等，則存在偽幣，並且可以判斷它位於較輕的那一組硬幣中。最後，在第三步中，用第二步的結果得出原先1 6個硬幣問題的答案。若僅僅判斷硬幣是否存在，則第三步非常簡單。無論A組還是B組中有偽幣，都可以推斷這1 6個硬幣中存在偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。假設需要識別出這一偽幣。把兩個或三個硬幣的情況作為不可再分的小問題。注意如果只有一個硬幣，那麼不能判斷出它是否就是偽幣。在一個小問題中，通過將一個硬幣分別與其他兩個硬幣比較，最多比較兩次就可以找到偽幣。這樣，1 6硬幣的問題就被分為兩個8硬幣（A組和B組）的問題。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果沒有偽幣，則演算法終止。否則，繼續劃分這兩組硬幣來尋找偽幣。假設B是輕的那一組，因此再把它分成兩組，每組有4個硬幣。稱其中一組為B1，另一組為B2。比較這兩組，肯定有一組輕一些。如果B1輕，則偽幣在B1中，再將B1又分成兩組，每組有兩個硬幣，稱其中一組為B1a，另一組為B1b。比較這兩組，可以得到一個較輕的組。由於這個組只有兩個硬幣，因此不必再細分。比較組中兩個硬幣的重量，可以立即知道哪一個硬幣輕一些。較輕的硬幣就是所要找的偽幣。 在n個元素中找出最大元素和最小元素。我們可以把這n個元素放在一個數組中，用直接比較法求出。演算法如下：void maxmin1(int A[],int n,int *max,int *min){ int i;*min=*max=A[0];for(i=0;i *max) *max= A[i];if(A[i] >

問題九：回溯演算法的典型例題 八皇後問題：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。

問題十：什麼是演算法，都什麼，舉個例子，謝謝 演算法就是解決問題的具體的方法和步驟，所以具有以下性質：
1、有窮性： 一個演算法必須保證執行有限步之後結束（如果步驟無限，問題就無法解決）
2、確切性：步驟必須明確，說清楚做什麼。
3、輸入：即解決問題前我們所掌握的條件。
4、輸出：輸出即我們需要得到的答案。
5、可行性：邏輯不能錯誤，步驟必須有限，必須得到結果。
演算法通俗的講：就是解決問題的方法和步驟。在計算機發明之前便已經存在。只不過在計算機發明後，其應用變得更為廣泛。通過簡單的演算法，利用電腦的計算速度，可以讓問題變得簡單。

3. 請高手幫忙：MATLAB程序 編寫一個程序，要求實現下列演算法：首先將圖像分割成許多8X8的子圖像

clearall;

closeall;

clc;

I=double(imread('elain.bmp'));%讀入圖像

imshow(uint8(I));%顯示圖像

[Mro,Nco]=size(I);%獲得讀入圖像的大小

fun1=@fft2;%獲得fft變換函數的句柄

Imagefft=blkproc(I,[8,8],fun1);%圖像塊進行fft變換

Imtemp=double(zeros(Mro,Nco));%設置臨時變數用於存處理後的圖像值

forii=1:8:Mro

forjj=1:8:Nco

Imtemp(ii:ii+3,jj:jj+3)=Imagefft(ii:ii+3,jj:jj+3);%捨去小的變換系數

end

end

fun2=@ifft2;

Imageifft=blkproc(Imtemp,[8,8],fun2);%分塊逆變換

huifu=uint8(abs(Imageifft));%取整

figure;

imshow(huifu);%顯示圖像

4. 求貨郎擔問題的matlab演算法

貨郎擔問題有很多解法，模擬退火，遺傳演算法，動態規劃等。

基於matlab TSP問題遺傳演算法的實現
%TSP問題（又名：旅行商問題，貨郎擔問題）遺傳演算法通用matlab程序
%D是距離矩陣，n為種群個數,建議取為城市個數的1~2倍，
%C為停止代數，遺傳到第 C代時程序停止,C的具體取值視問題的規模和耗費的時間而定
%m為適應值歸一化淘汰加速指數 ,最好取為1,2,3,4 ,不宜太大
%alpha為淘汰保護指數,可取為0~1之間任意小數,取1時關閉保護功能,最好取為0.8~1.0
%R為最短路徑,Rlength為路徑長度
function [R,Rlength]=geneticTSP(D,n,C,m,alpha)

[N,NN]=size(D);
farm=zeros(n,N);%用於存儲種群
for i=1:n
farm(i,:)=randperm(N);%隨機生成初始種群
end
R=farm(1,:);%存儲最優種群
len=zeros(n,1);%存儲路徑長度
fitness=zeros(n,1);%存儲歸一化適應值
counter=0;

while counter<c

for i=1:n
len(i,1)=myLength(D,farm(i,:));%計算路徑長度
end
maxlen=max(len);
minlen=min(len);
fitness=fit(len,m,maxlen,minlen);%計算歸一化適應值
rr=find(len==minlen);
R=farm(rr(1,1),:);%更新最短路徑

FARM=farm;%優勝劣汰，nn記錄了復制的個數
nn=0;
for i=1:n
if fitness(i,1)>=alpha*rand
nn=nn+1;
FARM(nn,:)=farm(i,:);
end
end
FARM=FARM(1:nn,:);

[aa,bb]=size(FARM);%交叉和變異
while aa<n
if nn<=2
nnper=randperm(2);
else
nnper=randperm(nn);
end
A=FARM(nnper(1),:);
B=FARM(nnper(2),:);
[A,B]=intercross(A,B);
FARM=[FARM;A;B];
[aa,bb]=size(FARM);
end
if aa>n
FARM=FARM(1:n,:);%保持種群規模為n
end

farm=FARM;
clear FARM
counter=counter+1

end

Rlength=myLength(D,R);

function [a,b]=intercross(a,b)
L=length(a);
if L<=10%確定交叉寬度
W=1;
elseif ((L/10)-floor(L/10))>=rand&&L>10
W=ceil(L/10);
else
W

http://blog.renren.com/share/231644124/531791903

5. 利用matlab計算多個坐標點，可以互相連接的最短距離

這個問題一般是TSP問題，該回答來自工中號一匹大懶蟲
旅行商問題，即TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
TSP問題是一個組合優化問題。該問題可以被證明具有NPC計算復雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。
旅行推銷員問題是圖論中最著名的問題之一，即「已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉迴路」。Edmonds，Cook和Karp等人發現，這批難題有一個值得注意的性質，對其中一個問題存在有效演算法時，每個問題都會有有效演算法。[1]
迄今為止，這類問題中沒有一個找到有效演算法。傾向於接受NP完全問題（NP-Complete或NPC）和NP難題（NP-Hard或NPH）不存在有效演算法這一猜想，認為這類問題的大型實例不能用精確演算法求解，必須尋求這類問題的有效的近似演算法。
此類問題中，經典的還有 子集和問題； Hamilton迴路問題；最大團問題。

6. 背包問題的演算法

1)登上演算法
用登山演算法求解背包問題 function []=DengShan(n,G,P,W) %n是背包的個數，G是背包的總容量，P是價值向量，W是物體的重量向量 %n=3;G=20;P=[25,24,15];W2=[18,15,10];%輸入量 W2=W; [Y,I]=sort(-P./W2);W1=[];X=[];X1=[]; for i=1:length(I) W1(i)=W2(I(i)); end W=W1; for i=1:n X(i)=0; RES=G;%背包的剩餘容量 j=1; while W(j)<=RES X(j)=1; RES=RES-W(j); j=j+1; end X(j)=RES/W(j); end for i=1:length(I) X1(I(i))=X(i); end X=X1; disp('裝包的方法是');disp(X);disp(X.*W2);disp('總的價值是：');disp(P*X');

時間復雜度是非指數的

2)遞歸法
先看完全背包問題
一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,
每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max{f(x-i)+c[i]} 當x>=w[i] 1<=i<=n
可使用遞歸法解決問題程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,編程很簡單,但當m較大時,容易超時.
4.2 改進的遞歸法
改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函數的值保存起來,開辟一個
一維數組即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
3)貪婪演算法
改進的背包問題：給定一個超遞增序列和一個背包的容量，然後在超遞增序列中選（只能選一次）或不選每一個數值，使得選中的數值的和正好等於背包的容量。

代碼思路：從最大的元素開始遍歷超遞增序列中的每個元素，若背包還有大於或等於當前元素值的空間，則放入，然後繼續判斷下一個元素；若背包剩餘空間小於當前元素值，則判斷下一個元素
簡單模擬如下：

#define K 10
#define N 10

＃i nclude <stdlib.h>
＃i nclude <conio.h>

void create(long array[],int n,int k)
{/*產生超遞增序列*/
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{/*輸出當前的超遞增序列*/
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}

void beibao(long array[],int cankao[],long value,int count)
{/*背包問題求解*/
int i;
long r=value;
for(i=count-1;i>=0;i--)/*遍歷超遞增序列中的每個元素*/
{
if(r>=array[i])/*如果當前元素還可以放入背包，即背包剩餘空間還大於當前元素*/
{
r=r-array[i];
cankao[i]=1;
}
else/*背包剩餘空間小於當前元素值*/
cankao[i]=0;
}
}

void main()
{
long array[N];
int cankao[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)/*所有已經選中的元素之和*/
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
貪婪演算法的另一種寫法，beibao函數是以前的代碼，用來比較兩種演算法：

#define K 10
#define N 10

＃i nclude <stdlib.h>
＃i nclude <conio.h>

void create(long array[],int n,int k)
{
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}

void beibao(long array[],int cankao[],long value,int count)
{
int i;
long r=value;
for(i=count-1;i>=0;i--)
{
if(r>=array[i])
{
r=r-array[i];
cankao[i]=1;
}
else
cankao[i]=0;
}
}

int beibao1(long array[],int cankao[],long value,int n)
{/*貪婪演算法*/
int i;
long value1=0;
for(i=n-1;i>=0;i--)/*先放大的物體，再考慮小的物體*/
if((value1+array[i])<=value)/*如果當前物體可以放入*/
{
cankao[i]=1;/*1表示放入*/
value1+=array[i];/*背包剩餘容量減少*/
}
else
cankao[i]=0;
if(value1==value)
return 1;
return 0;
}

void main()
{
long array[N];
int cankao[N]={0};
int cankao1[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
printf("\nSecond method:\n");
if(beibao1(array,cankao1,value,N)==1)
{
for(i=0;i<N;i++)
if(cankao1[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}

4)動態規劃演算法

解決0/1背包問題的方法有多種，最常用的有貪婪法和動態規劃法。其中貪婪法無法得到問題的最優解，而動態規劃法都可以得到最優解，下面是用動態規劃法來解決0/1背包問題。

動態規劃演算法與分治法類似，其基本思想是將待求解問題分解成若干個子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的，若用分治法解這類問題，則分解得到的子問題數目太多，以至於最後解決原問題需要耗費過多的時間。動態規劃法又和貪婪演算法有些一樣，在動態規劃中，可將一個問題的解決方案視為一系列決策的結果。不同的是，在貪婪演算法中，每採用一次貪婪准則便做出一個不可撤回的決策，而在動態規劃中，還要考察每個最優決策序列中是否包含一個最優子序列。

0/1背包問題

在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對於可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示選取物品i) 取得最大值。
在該問題中需要決定x1 .. xn的值。假設按i = 1，2，...，n 的次序來確定xi 的值。如果置x1 = 0，則問題轉變為相對於其餘物品(即物品2，3，.，n)，背包容量仍為c 的背包問題。若置x1 = 1，問題就變為關於最大背包容量為c-w1 的問題。現設r?{c，c-w1 } 為剩餘的背包容量。
在第一次決策之後，剩下的問題便是考慮背包容量為r 時的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之後的一個最優方案，如果不是，則會有一個更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一個更好的方案。
假設n=3, w=[100,14,10], p=[20,18,15], c= 116。若設x1 = 1，則在本次決策之後，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因為[x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 並非最優策略。即x= [ 1，0，1] 可改進為x= [ 1，1，0 ]。若設x1 = 0，則對於剩下的兩種物品而言，容量限制條件為116。總之，如果子問題的結果[x2，x3 ]不是剩餘情況下的一個最優解，則[x1，x2，x3 ]也不會是總體的最優解。在此問題中，最優決策序列由最優決策子序列組成。假設f (i,y) 表示剩餘容量為y，剩餘物品為i，i + 1，...，n 時的最優解的值，即：利用最優序列由最優子序列構成的結論，可得到f 的遞歸式為：
當j>=wi時： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式
當0<=j<wi時：f(i,j)=f(i+1,j) ②式
fn( 1 ,c) 是初始時背包問題的最優解。
以本題為例：若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。因此最優解f ( 1 , 11 6 ) = m a x {f(2，11 6)，f(2，11 6 - w1)+ p1} = m a x {f(2，11 6)，f(2，1 6)+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
現在計算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩餘容量c-w1中尋求最優解，用f (2, c-w1) 表示最優解。依此類推，可得到所有的xi (i= 1.n) 值。
在該例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計算x2 及x3，此時r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。

7. 貪心演算法中的matlab演算法怎麼做

1.數論演算法
求兩數的最大公約數
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;

求兩數的最小公倍數
function lcm(a,b:integer):integer;
begin
if a< b then swap(a,b);
lcm:=a;
while lcm mod b >0 do inc(lcm,a);
end;

素數的求法
A.小范圍內判斷一個數是否為質數：
function prime (n: integer): Boolean;
var I: integer;
begin
for I:=2 to trunc(sqrt(n)) do
if n mod I=0 then
begin
prime:=false; exit;
end;
prime:=true;
end;

B.判斷longint范圍內的數是否為素數（包含求50000以內的素數表）：
procere getprime;
var
i,j:longint;
p:array[1..50000] of boolean;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i< 50000 do
begin
if p then
begin
j:=i*2;
while j< 50000 do
begin
p[j]:=false;
inc(j,i);
end;
end;
inc(i);
end;
l:=0;
for i:=1 to 50000 do
if p then
begin
inc(l);
pr[l]:=i;
end;
end;{getprime}
function prime(x:longint):integer;
var i:integer;
begin
prime:=false;
for i:=1 to l do
if pr >=x then break
else if x mod pr=0 then exit;
prime:=true;
end;{prime}

2．

3．

4.求最小生成樹
A.Prim演算法：
procere prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do
begin
lowcost:=cost[v0,i];
closest:=v0;
end;
for i:=1 to n-1 do
begin
{尋找離生成樹最近的未加入頂點k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]< min) and (lowcost[j]< >0) then
begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {將頂點k加入生成樹}
{生成樹中增加一條新的邊k到closest[k]}
{修正各點的lowcost和closest值}
for j:=1 to n do
if cost[k,j]< lwocost[j] then
begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}
B.Kruskal演算法：(貪心)
按權值遞增順序刪去圖中的邊，若不形成迴路則將此邊加入最小生成樹。
function find(v:integer):integer; {返回頂點v所在的集合}
var i:integer;
begin
i:=1;
while (i< =n) and (not v in vset) do inc(i);
if i< =n then find:=i
else find:=0;
end;
procere kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset:=;{初始化定義n個集合，第I個集合包含一個元素I}
p:=n-1; q:=1; tot:=0; {p為尚待加入的邊數，q為邊集指針}
sort;
{對所有邊按權值遞增排序，存於e[I]中，e[I].v1與e[I].v2為邊I所連接的兩個頂點的序號，e[I].len為第I條邊的長度}
while p >0 do
begin
i:=find(e[q].v1);j:=find(e[q].v2);
if i< >j then
begin
inc(tot,e[q].len);
vset:=vset+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;

5.最短路徑
A.標號法求解單源點最短路徑：
var
a:array[1..maxn,1..maxn] of integer;
b:array[1..maxn] of integer; {b指頂點i到源點的最短路徑}
mark:array[1..maxn] of boolean;

procere bhf;
var
best,best_j:integer;
begin
fillchar(mark,sizeof(mark),false);
mark[1]:=true; b[1]:=0;{1為源點}
repeat
best:=0;
for i:=1 to n do
If mark then {對每一個已計算出最短路徑的點}
for j:=1 to n do
if (not mark[j]) and (a[i,j] >0) then
if (best=0) or (b+a[i,j]< best) then
begin
best:=b+a[i,j]; best_j:=j;
end;
if best >0 then
begin
b[best_j]:=best；mark[best_j]:=true;
end;
until best=0;
end;{bhf}

B.Floyed演算法求解所有頂點對之間的最短路徑：
procere floyed;
begin
for I:=1 to n do
for j:=1 to n do
if a[I,j] >0 then p[I,j]:=I else p[I,j]:=0;
{p[I,j]表示I到j的最短路徑上j的前驅結點}
for k:=1 to n do {枚舉中間結點}
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[j,k]< a[i,j] then
begin
a[i,j]:=a[i,k]+a[k,j];
p[I,j]:=p[k,j];
end;
end;
C. Dijkstra 演算法：
類似標號法，本質為貪心演算法。
var
a:array[1..maxn,1..maxn] of integer;
b,pre:array[1..maxn] of integer; {pre指最短路徑上I的前驅結點}
mark:array[1..maxn] of boolean;
procere dijkstra(v0:integer);
begin
fillchar(mark,sizeof(mark),false);
for i:=1 to n do
begin
d:=a[v0,i];
if d< >0 then pre:=v0 else pre:=0;
end;
mark[v0]:=true;
repeat {每循環一次加入一個離1集合最近的結點並調整其他結點的參數}
min:=maxint; u:=0; {u記錄離1集合最近的結點}
for i:=1 to n do
if (not mark) and (d< min) then
begin
u:=i; min:=d;
end;
if u< >0 then
begin
mark:=true;
for i:=1 to n do
if (not mark) and (a[u,i]+d< d) then
begin
d:=a[u,i]+d;
pre:=u;
end;
end;
until u=0;
end;
D.計算圖的傳遞閉包
Procere Longlink;
Var
T:array[1..maxn,1..maxn] of boolean;
Begin
Fillchar(t,sizeof(t),false);
For k:=1 to n do
For I:=1 to n do
For j:=1 to n do
T[I,j]:=t[I,j] or (t[I,k] and t[k,j]);
End;

8. tSp Concorder演算法原理

tsp問題遺傳演算法將多目標按照線性加權的方式轉化為單目標，然後應用傳統遺傳演算法求解
其中w_i表示第i個目標的權重，f_k表示歸一化之後的第i個目標值。我們很容易知道，這類方法的關鍵是怎麼設計權重。比如，Random Weight Genetic Algorithm (RWGA) 採用隨機權重的方式，每次計算適應度都對所有個體隨機地產生不同目標的權重，然後進行選擇操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基於線性加權的多目標遺傳演算法。如果有K個目標，VEGA 會隨機地將種群分為K個同等大小子種群，在不同的子種群按照不同的目標函數設定目標值，然後再進行選擇操作。VEGA 實質上是基於線性加權的多目標遺傳演算法。VEGA 是第一個多目標遺傳演算法，開啟了十幾年的研究潮流。
1.TSP問題是指假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。本文使用遺傳演算法解決att30問題，即30個城市的旅行商問題。旅行商問題是一個經典的組合優化問題。一個經典的旅行商問題可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發，需要經過所有城市後，回到出發地。應如何選擇行進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完全無向圖中，找一個權值最小的Hamilton迴路。由於該問題的可行解是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸，它是一個NP完全問題。TSP問題可以分為對稱和不對稱。在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖，而不對稱TSP則形成有向圖。對稱性TSP問題可以將解的數量減少了一半。所以本次實驗的TSP問題使用att48數據，可在tsplib中下載數據包。演化演算法是一類模擬自然界遺傳進化規律的仿生學演算法，它不是一個具體的演算法，而是一個演算法簇。遺傳演算法是演化演算法的一個分支，由於遺傳演算法的整體搜索策略和優化計算是不依賴梯度信息，所以它的應用比較廣泛。我們本次實驗同樣用到了遺傳演算法（用MATLAB編寫）來解決TSP問題。

9. matlab運行程序時不報錯，只顯示出ans=程序名，這是為什麼，以下是詳細代碼，用pso演算法求解tsp問題

換個名字就好了。
不要使用「純數字」、「關鍵字」等等。
名稱裡面，也不要有運算符號：－、＋等等。
也不要用漢字。