代價如何演算法

Ⅰ 什麼是傳播代價

傳播代價就是說通過相應的傳播的成本比如說機器人的長距離傳播代價就是通信成本還有就是物質成本

Ⅱ 代價一致搜索是dijkstra嗎

你好，本質上代價一致演算法是dijkstra演算法的一種特殊情況。他們的區別可以從下面幾個方面體會。

代價一致演算法要解決的問題：尋找從根結點到目標節點之間代價最小的路徑，這裡面目標節點是確定的。一旦找到目標節點的最小代價路徑，演算法就停止了。
dijkstra演算法要解決的問題：尋找從根節點到圖中所有節點的代價最小距離，這里沒有給出具體的目標節點，可以認為除了根節點之外其他所有節點都是目標節點。只有當所有節點都被討論之後，演算法才停止。因此對於同樣的圖，dijkstra用的時間和內存比代價一致演算法多。
在數學領域，dijkstra演算法出現的較多，因為數學問題往往具有普遍性。而在人工智慧領域代價一致演算法出現的較多，因為對於一個具體的問題其目標往往是已知的。

dijkstra通常用圖表示，代價一致演算法通常用樹表示。

我也是初學者，上面這些是看了一些資料自己總結的，希望對你理解這兩種演算法有幫助。

Ⅲ ospf協議的代價是如何計算的

Cost = 100×106/鏈路帶寬
這里，鏈路帶寬以bps來表示。也就是說，OSPF的Cost 與鏈路的帶寬成反比，帶寬越高，Cost越小，表示OSPF到目的地的距離越近。舉例來說，FDDI或快速乙太網的Cost為1，2M串列鏈路的Cost為48，10M乙太網的Cost為10等。

這個是搜來的，和我看過的CCNA上說的基本一致。。詳細的你可以看一下地下的鏈接。

Ⅳ Kruskal演算法和Prim演算法構造它的一棵最小代價生成樹的過程

Prim演算法復雜度：O(n2), 與邊無關，適合求邊稠密的網的最小生成樹。

演算法思想：假設N={V,{E}}是連通網，TE是N上最小生成樹中邊的集合。演算法從U={u0},TE ={}開始，重復執行下述操作：在所有u∈U,v∈V-U的邊（u，v）∈E中找一條代價最小的邊（u0,v0）並入集合TE，同時v0並入U，直至U=V為止。

Kruskal演算法復雜度：O(eloge)，相對於Prim而言，適合求邊稀疏的網的最小生成樹。

演算法思想：最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=(V,{})，圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則捨去次邊而選擇下一條代價最小的邊。直至T中所有頂點都在同一連通分量上為止。

Ⅳ 如何用Dijkstra演算法，求出多條代價相同的路徑

偉豬 [轉貼 2005-12-15 20:21:00 ] 發表者: 偉偉豬

/***********************************************
設G=(V,E)是一個每條邊都有非負長度的有向圖，有一個特異的頂點s稱為緣。
單源最短路徑問題，或者稱為最短路徑問題，是要確定從s到V中沒一個其他
頂點的距離，這里從頂點s到x的距離定義為從s到x的最短路徑問題。這個問題
可以用Dijkstra演算法解決。下面我給我了c++下的源代碼！ --by 偉偉豬
************************************************/
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t))
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))

}
cout<<"從源點到其它頂點的最短距離依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}
/*********
頂點個數用n表示，這里給出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具體例子見 電子工業出版社 《演算法設計技巧與分析》148頁
************/

Ⅵ 演算法的時間代價

隨便解釋一下 ，解釋的不好見諒
一個演算法是解決某個問題的，比如n條數據排序問題，那麼對於這個問題「n」就是它的問題規模
那麼解決這個問題的演算法的代價一定是n的函數，記為T(n)
為了比較不同演算法之間的優劣，必須有一種方法將計算代價的函數進行變換，所以提出一種
概念叫做「復雜度」（好像是這么個意思,教材上的那個陰文單詞背不出了)
記作T(n)=O(f(n)),表示代價T(n)和f(n)一樣
比方說一個演算法用時T(n)=n天 ，另一個演算法用f(n)=100n天，可以證明
n=O(100n),那麼就認為兩個演算法復雜度相同（1天和100天復雜度還相同,....)

摟住的後半句就是具體定義，「存在正常數C和N,當問題規模n>N時,有T(n)<=Cf(n)」意思就是說如果有一個正的常數C，和一個正的常數N，當n>N 不等式T(n)<=Cf(n)恆成立，就「稱某演算法的時間(或空間)代價T(n)=O(f(n))」

比如一個演算法的代價是T(n)=100n ，那麼當n>=1時，100n <= 101 n
那麼就可以記作
T(n)=100n = O（n） 這里f(n)是f(n)=n，C=101，N=1

Ⅶ 程序的演算法代價是什麼

時間和空間。

Ⅷ 付出代價最小的死鎖解除演算法

摘要 付出代價最小的死鎖解除演算法

Ⅸ 桶排序的代價

桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當於快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然後只需要對桶中的少量數據做先進的比較排序即可。
對N個關鍵字進行桶排序的時間復雜度分為兩個部分：
(1) 循環計算每個關鍵字的桶映射函數，這個時間復雜度是O(N)。
(2) 利用先進的比較排序演算法對每個桶內的所有數據進行排序，其時間復雜度為 ∑ O(Ni*logNi) 。其中Ni 為第i個桶的數據量。
很顯然，第(2)部分是桶排序性能好壞的決定因素。盡量減少桶內數據的數量是提高效率的唯一辦法(因為基於比較排序的最好平均時間復雜度只能達到O(N*logN)了)。因此，我們需要盡量做到下面兩點：
(1) 映射函數f(k)能夠將N個數據平均的分配到M個桶中，這樣每個桶就有[N/M]個數據量。
(2) 盡量的增大桶的數量。極限情況下每個桶只能得到一個數據，這樣就完全避開了桶內數據的「比較」排序操作。 當然，做到這一點很不容易，數據量巨大的情況下，f(k)函數會使得桶集合的數量巨大，空間浪費嚴重。這就是一個時間代價和空間代價的權衡問題了。
對於N個待排數據，M個桶，平均每個桶[N/M]個數據的桶排序平均時間復雜度為：
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
當N=M時，即極限情況下每個桶只有一個數據時。桶排序的最好效率能夠達到O(N)。
總結：桶排序的平均時間復雜度為線性的O(N+C)，其中C=N*(logN-logM)。如果相對於同樣的N，桶數量M越大，其效率越高，最好的時間復雜度達到O(N)。當然桶排序的空間復雜度為O(N+M)，如果輸入數據非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩定的。

Ⅹ 計算以下程序段演算法的時間代價

A
外側跑了n次，內層跑了1次
共n*1，即O(n)