貨郎問題????

    一筆畫問題

const max=6;{頂點(diǎn)數(shù)為6}
type shuzu=array[1..max,1..max]of 0..max;
const a:shuzu {圖的描述與定義 1:連通;0:不通}
=((0,1,0,1,1,1),
(1,0,1,0,1,0),
(0,1,0,1,1,1),
(1,0,1,0,1,1),
(1,1,1,1,0,0),
(1,0,1,1,0,0));
var
bianshu:array[1..max]of 0..max; {與每一條邊相連的邊數(shù)}
path:array[0..1000]of integer; {記錄畫法,只記錄頂點(diǎn)}
zongbianshu,ii,first,i,total:integer;

procedure output(dep:integer); {輸出各個頂點(diǎn)的畫法順序}
var sum,i,j:integer;
begin
inc(total);
writeln('total:',total);
for i:=0 to dep do write(Path);writeln;
end;

function ok(now,i:integer;var next:integer):boolean;{判斷第I條連接邊是否已行過}
var j,jj:integer;
begin
j:=0; jj:=0;
while jj<>i do begin inc(j);if a[now,j]<>0 then inc(jj);end;
next:=j;
{判斷當(dāng)前頂點(diǎn)的第I條連接邊的另一端是哪個頂點(diǎn),找出后賦給NEXT傳回}
ok:=true;
if (a[now,j]<>1) then ok:=false; {A[I,J]=0:原本不通}
end; { =2:曾走過}

procedure init; {初始化}
var i,j :integer;
begin
total:=0; {方案總數(shù)}
zongbianshu:=0; {總邊數(shù)}
for i:=1 to max do
for j:=1 to max do
if a[i,j]<>0 then begin inc(bianshu);inc(zongbianshu);end;
{求與每一邊連接的邊數(shù)bianshu}
zongbianshu:=zongbianshu div 2; {圖中的總邊數(shù)}
end;

procedure find(dep,nowpoint:integer); {dep:畫第幾條邊;nowpoint:現(xiàn)在所處的頂點(diǎn)}
var i,next,j:integer;
begin
for i:=1 to bianshu[nowpoint] do {與當(dāng)前頂點(diǎn)有多少條相接,則有多少種走法}
if ok(nowpoint,i,next) then begin {與當(dāng)前頂點(diǎn)相接的第I條邊可行嗎?}
{如果可行,其求出另一端點(diǎn)是NEXT}
a[nowpoint,next]:=2; a[next,nowpoint]:=2; {置成已走過標(biāo)志}
path[dep]:=next; {記錄頂點(diǎn),方便輸出}
if dep < zongbianshu then find(dep+1,next) {未搜索完每一條邊}
else output(dep);
path[dep]:=0; {回溯}
a[nowpoint,next]:=1; a[next,nowpoint]:=1;
end;

begin
init; {初始化,求邊數(shù)等}
for first:=1 to max do {分別從各個頂點(diǎn)出發(fā),嘗試一筆畫}
fillchar(path,sizeof(path),0);
path[0]:=first; {記錄其起始的頂點(diǎn)}
writeln('from point ',first,':');readln;
find(1,first); {從起始點(diǎn)first,一條邊一條邊地畫下去}
end.

    銀行家算法其實(shí)是很普通的但是比較經(jīng)典的算法，每本OS的書上都講的，主要用來防止產(chǎn)生死鎖的，

    形象的講：銀行發(fā)放貸款（對不同的客戶，有分期貸的）不能使有限可用資金匱乏而導(dǎo)致整個銀行無法運(yùn)轉(zhuǎn)，也就是說每次請求貸款時，銀行要考慮他能否憑著貸款完成項(xiàng)目還清貸款使銀行運(yùn)轉(zhuǎn)正常，

    （借用flyingcoolhwak寫的步驟）

    令Request(i)是進(jìn)程P(i)請求向量，如果Request(i)[j]=k，則進(jìn)程P(i)希望請求j類資源k個。

    算法步驟如下：

    1、如果Request(i)>Need(i)則出錯(請求量超過申報的最大量),否則轉(zhuǎn)2、

    2、如果Requdst(i)>Available則P(i)等待，否則轉(zhuǎn)3、

    3、系統(tǒng)對P(i)所請求的資源實(shí)施試探分配，更改數(shù)據(jù)結(jié)構(gòu)中的數(shù)值

    4、Available<-Available-Request(i)
       Allocation(i)<-Allocation(i)+Request(i)
       Need(i)<-Need(i)-Request(i)

    5、執(zhí)行安全性算法(如下)，如果是安全的則承認(rèn)試分配，否則廢除試分配，讓進(jìn)程P(i)等待

    貨郎擔(dān)問題

    問題描述

    歐幾里德貨郎擔(dān)問題是對平面給定的n個點(diǎn)確定一條連結(jié)各點(diǎn)的、閉合的游歷路線問題。圖1(a)給出了七個點(diǎn)問題的解。Bitonic旅行路線問題是歐幾里德貨郎擔(dān)問題的簡化，這種旅行路線先從最左邊開始，嚴(yán)格地由左至右到最右邊的點(diǎn)，然后再嚴(yán)格地由右至左到出發(fā)點(diǎn)，求路程最短的路徑長度。圖1（b）給出了七個點(diǎn)問題的解。

    請?jiān)O(shè)計一種多項(xiàng)式時間的算法，解決Bitonic旅行路線問題

上一頁  [1] [2]