屬性選擇的貪心演算法

❶ TSP問題的遍歷演算法和貪心演算法有什麼區別,為什麼不選擇遍歷演算法

所有問題遍歷演算法的時間復雜度是最高的，但是對於TSP問題來說貪心演算法一般是得不到最優解的

❷ 貪心演算法中，通常會讓證明貪心選擇性，請問，證明貪心選擇性的實質是什麼怎樣說明一個問題具有貪心選擇呢

一般都是要最省事的比如
設有n中不同面值的硬幣，個硬幣的面值春雨數組T[1：n]中，現在要用這些面值的硬幣來找錢。可以使用的各種面值的硬幣個數存於數組Coins[1:n]中。
對任意簽署0<=m<=20001，設計一個用最少硬幣找錢m的方法。

用貪心演算法，先用最大面值的，直到超出之前再改用更小面值的，超出之前再用更更小面值的。。直到正好。這樣最少
程序實例
#include<stdio.h>

void main()
{
int m;
int i;
printf("please input m:");
scanf("%d",&m);
int T[6] ={100,50,20,10,5,1};
int coins[6] = {0};
for(i = 0; i < 6; )
{
if(m < T[i])
{
i++;
continue;
}
while(m >= T[i])
{
m -= T[i];
coins[i]++;
}
i++;

}

for(i = 0; i < 6; i++)
if(coins==0)
printf("%-4d有 %-2d張\n",T[i],coins[i]);
printf("\n");
}

❸ 貪心演算法的特性

貪婪演算法可解決的問題通常大部分都有如下的特性：
⑴隨著演算法的進行，將積累起其它兩個集合：一個包含已經被考慮過並被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。
⑵有一個函數來檢查一個候選對象的集合是否提供了問題的解答。該函數不考慮此時的解決方法是否最優。
⑶還有一個函數檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數一樣，此時不考慮解決方法的最優性。
⑷選擇函數可以指出哪一個剩餘的候選對象最有希望構成問題的解。
⑸最後，目標函數給出解的值。
⑹為了解決問題，需要尋找一個構成解的候選對象集合，它可以優化目標函數，貪婪演算法一步一步的進行。起初，演算法選出的候選對象的集合為空。接下來的每一步中，根據選擇函數，演算法從剩餘候選對象中選出最有希望構成解的對象。如果集合中加上該對象後不可行，那麼該對象就被丟棄並不再考慮；否則就加到集合里。每一次都擴充集合，並檢查該集合是否構成解。如果貪婪演算法正確工作，那麼找到的第一個解通常是最優的。

❹ 貪心演算法的介紹

貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

❺ 使用貪心演算法解決活動安排問題時使用什麼優先貪心選擇策略

貪心選擇性質：所求問題的整體最優解可以通過一系列局部最優的選擇來得到。
就是說，你需要證明當前問題可以通過選擇最好的那個元素（比如01背包，總能夠通過選擇當前重量最小的物品來得到最優解）來解決問題
證明：（每一步所做的貪心選擇最終導致問題的整體最優解）
//基本思路：考察一個問題的最優解，證明可修改該最優解，使得其從貪心選擇開始，然後用數學歸納法證明每一步都可以通過貪心選擇得到最優解
1，假定首選元素不是貪心選擇所要的元素，證明將首元素替換成貪心選擇所需元素，依然得到最優解；
2，數學歸納法證明每一步均可通過貪心選擇得到最優解

❻ 關於數據挖掘中決策樹的知識

在數據挖掘中，有很多的演算法是需要我們去學習的，比如決策樹演算法。在數據挖掘中，決策樹能夠幫助我們解決更多的問題。當然，關於決策樹的概念是有很多的，所以說我們需要多多學習多多總結，這樣才能夠學會並且學會數據挖掘的知識，在這篇文章中我們就重點為大家介紹一下關於決策樹的相關知識。
1.決策樹的演算法
決策樹的演算法是以樹狀結構表示數據分類的結果。一般情況，一棵決策樹包含一個根節點、若干個內部結點和若干個葉結點。而葉結點對應於決策結果，其他每個結點則對應於一個屬性測試；每個結點包含的樣本集合根據屬性測試的結果被劃分到子結點中；根結點包含樣本全集，從根結點到每個葉結點的路徑對應了一個判定測試序列。決策樹學習的目的就是為了產生一棵泛化能力強，即能處理未見示例能力強的決策樹。這些就是決策樹演算法的結構。
2.決策樹的原理
一般來說，決策樹歸納的基本演算法是貪心演算法，自頂向下以遞歸方式構造決策樹。而貪心演算法在每一步選擇中都採取在當前狀態下最優的選擇。在決策樹生成過程中，劃分選擇即屬性選擇度量是關鍵。通過屬性選擇度量，選擇出最好的將樣本分類的屬性。這樣就能夠方便數據屬性的劃分，然後，下一步是樹的剪枝。在決策樹學習中，為了盡可能正確分類訓練樣本，結點劃分過程將不斷重復，這樣才能夠使用決策樹解決很多的問題。而分類是數據挖掘中的一種應用方法，而決策樹則是一種典型的普遍使用的分類方法，並且決策樹技術早已被證明是利用計算機模擬人決策的有效方法。
3.決策樹的現狀
近年來隨著信息技術、計算機科學的迅速發展，決策樹作為重要方法之一，越來越受到人們的關注。而其在人工智慧方面的潛力以及與越來越多新技術的結合，由此可見，決策樹在數據挖掘乃至數據分析中還是有很長的使用時間，這就是決策樹至今經典的原因。
在這篇文章中我們給大家介紹了關於數據挖掘中決策樹的知識，當大家學習了決策樹的概念，決策樹的結構以決策樹的原理，就能夠掌握決策樹的基礎知識。不過要想學習數據挖掘，還是要學習更多的知識，希望這篇文章能夠幫助到大家。

❼ 貪心演算法選擇問題

題目：學校出去春遊啦 輸入春遊的人數N 已知有單車B輛（B>=N） 再輸入學校給大家共經費A元

設每個人都帶了錢 帶的錢是M1,M2,M3······MN 且大家幫自己的錢給別人 只能共用經費A元 再輸入每輛單車的價錢 ：C1,C2,C3······CB 求最多能有幾個人能騎上單車

這題我們用的就是貪心演算法

程序如下

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<iomanip>
#defineMAXN10000
usingnamespacestd;
intn,B,A,M[MAXN],C[MAXN],ans,mid;
boolcheck(intnn)
{
intcount=0,i=n-nn+1,j=1;
while(i<=n)
{
if(M[i]>=C[j])
count+=C[j]-M[i];
i++;
j++;
}
returncount-A;
}
intsort(inta[],intn)
{
for(inti=0;i<n;i++)
{
for(intj=0;j<i;j++)
if(a[i]<a[j])
{
inttemp=a[i];a[i]=a[j];a[j]=temp;
}
}
}
intmain()
{
cin>>n>>B>>A;
for(inti=0;i<n;i++)
cin>>M[i];
for(inti=0;i<B;i++)
cin>>C[i];
sort(M,n);
sort(C,B);
intl=0,r=n;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid))
{
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
cout<<ans;
return0;
}