中文字幕无码av不卡一区,亚洲综合AV永久无码精品一区二区,黑人巨大白妞出浆,黄色高清无码免费看,久久久久免费精品国产,久久无码人妻丰满熟妇区毛片,欧美日韩国产综合草草,久久福利网站,亚洲一区二区三区中文字幕在线,av国内精品久久久久影院

對(duì)于AI產(chǎn)品經(jīng)理來(lái)說(shuō)，掌握一些算法是必要的。本文將從五個(gè)方面，講述AI產(chǎn)品經(jīng)理必修的貪心算法，希望對(duì)你有幫助。

去年“新智元”有一篇報(bào)道《清華畢業(yè)計(jì)算機(jī)教授遭持槍劫車(chē)，靠“貪心算法”追回秒殺美國(guó)警察》，整個(gè)故事像看微小說(shuō)一樣，可對(duì)于核心問(wèn)題“貪心算法”是什么并沒(méi)有說(shuō)清楚，于是就有了下面的內(nèi)容。

一、什么是貪心算法

貪心的意思在于在作出選擇時(shí)，每次都要選擇對(duì)自身最為有利的結(jié)果，保證自身利益的最大化，貪心算法就是利用這種貪心思想而得出一種算法。

貪心算法可以簡(jiǎn)單描述為：大事化小，小事化了。對(duì)于一個(gè)較大的問(wèn)題，通過(guò)找到與子問(wèn)題的重疊，把復(fù)雜的問(wèn)題劃分為多個(gè)小問(wèn)題。并且對(duì)于每個(gè)子問(wèn)題的解進(jìn)行選擇，找出最優(yōu)值，進(jìn)行處理，再找出最優(yōu)值，再處理。也就是說(shuō)貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)的選擇，從而希望得到結(jié)果是最好或最優(yōu)的算法。

貪心算法在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。

二、貪心算法基本思路

步驟一：建立數(shù)學(xué)模型來(lái)描述問(wèn)題。

步驟二：把求解的問(wèn)題分成若干個(gè)子問(wèn)題。

步驟三：對(duì)每個(gè)子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。

步驟四：把子問(wèn)題的解局部最優(yōu)解合成原來(lái)問(wèn)題的一個(gè)解。

三、貪心算法的選擇

所謂貪心選擇是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，換句話說(shuō)，當(dāng)考慮做何種選擇的時(shí)候，我們只考慮對(duì)當(dāng)前問(wèn)題最佳的選擇而不考慮子問(wèn)題的結(jié)果。

貪心算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。

我們下面通過(guò)示例來(lái)看一下貪心算法如何選擇。

四、貪心算法示例

看一下《算法導(dǎo)論》中的經(jīng)典例題：活動(dòng)選擇問(wèn)題。

有n個(gè)需要在同一天使用同一個(gè)教室的活動(dòng)a1，a2……an，教室同一時(shí)刻只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)ai都有一個(gè)開(kāi)始時(shí)間si和結(jié)束時(shí)間fi 。一旦被選擇后，活動(dòng)ai就占據(jù)半開(kāi)時(shí)間區(qū)間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個(gè)活動(dòng)就可以被安排在這一天。該問(wèn)題就是要安排這些活動(dòng)使得盡量多的活動(dòng)能不沖突的舉行（標(biāo)紅的是我們利用貪心算法求出的結(jié)果1、4、8、11）。

第一步：分析題目

目標(biāo)函數(shù)count（n）活動(dòng)次數(shù)最多。

約束條件是下一個(gè)活動(dòng)開(kāi)始時(shí)間大于或等于上一個(gè)活動(dòng)開(kāi)始時(shí)間s[i]>=f[j]。

第二步：選擇解題思路

• 每次選擇開(kāi)始時(shí)間最早的活動(dòng)
• 每次選擇持續(xù)時(shí)間最短的活動(dòng)
• 每次選取結(jié)束時(shí)間最早的活動(dòng)

第三步：證明上面哪種思路可以應(yīng)用于本題

為了方便，我們用不同顏色的線條代表每個(gè)活動(dòng)，線條的長(zhǎng)度就是活動(dòng)所占據(jù)的時(shí)間段，藍(lán)色的線條表示我們已經(jīng)選擇的活動(dòng)；紅色的線條表示我們沒(méi)有選擇的活動(dòng)。

1）如果我們每次都選擇開(kāi)始時(shí)間最早的活動(dòng)，不能得到最優(yōu)解

證明（反證法）：

例如我們選擇了10號(hào)活動(dòng)（開(kāi)始時(shí)間2點(diǎn)，結(jié)束時(shí)間13點(diǎn)）；

2號(hào)活動(dòng)待選擇（開(kāi)始時(shí)間3點(diǎn)，結(jié)束時(shí)間5點(diǎn)）；

則會(huì)出現(xiàn)上圖所示的情況，這顯然違背了約束條件。

2）如果我們每次都選擇持續(xù)時(shí)間最短的活動(dòng)，不能得到最優(yōu)解

證明（反證法）：

例如我們選擇了2號(hào)活動(dòng)（開(kāi)始時(shí)間3點(diǎn)，結(jié)束時(shí)間5點(diǎn)）；

1號(hào)活動(dòng)待選擇（開(kāi)始時(shí)間1點(diǎn)，結(jié)束時(shí)間4點(diǎn)）；

則會(huì)出現(xiàn)上圖所示的情況，這顯然也違背了約束條件。

3）如果我們每次都選取結(jié)束時(shí)間最早的活動(dòng)，能夠得到最優(yōu)解（采用的貪心策略）

那么怎么證明貪心算法是對(duì)的呢？

要證明一個(gè)算法是錯(cuò)的非常簡(jiǎn)單，要證明是對(duì)的卻非常難。對(duì)于貪心算法的證明，一是使用歸納法，二是采用反證法。像上面兩種策略，我們實(shí)際上就用到了反證法。

回到策略本身，按這種方法選擇相容活動(dòng)，能夠?yàn)槲窗才诺幕顒?dòng)留下盡可能多的時(shí)間。

第四步：選好策略，那我們就來(lái)按照貪心算法的基本思路總結(jié)一下

1. 數(shù)學(xué)模型是目標(biāo)函數(shù)count（n）最大，約束條件是s[i]>=f[j]；
2. 求解哪個(gè)活動(dòng)結(jié)束時(shí)間最早（本題目顯然是活動(dòng)1）；
3. 求解哪個(gè)動(dòng)開(kāi)始時(shí)間s[i]大于上一個(gè)活動(dòng)結(jié)束時(shí)間f[j]；
4. 把步驟三求出的活動(dòng)依次取出，作為我們選取的活動(dòng)

上代碼：

這段代碼的含義是：

1. 定義活動(dòng)號(hào)n，活動(dòng)開(kāi)始時(shí)間、結(jié)束時(shí)間Type s[]，Type f[]，布爾邏輯判斷A[]；
2. 定義進(jìn)入算法的活動(dòng)序號(hào)，最終選取的活動(dòng)序號(hào)i，j；
3. 初始活動(dòng)i=1，由于1號(hào)活動(dòng)結(jié)束時(shí)間，所以選取j=1。

從2號(hào)活動(dòng)開(kāi)始進(jìn)入運(yùn)算，具體運(yùn)算規(guī)則：

• 判斷條件：活動(dòng)開(kāi)始時(shí)間（i）>上一個(gè)活動(dòng)結(jié)束時(shí)間（j）
• A[]為true，j選中
• A[]為false，j不選擇
• i自增1位，繼續(xù)判斷，直至i=11

上圖直觀展示了算法的整個(gè)運(yùn)行過(guò)程。

五、貪心算法應(yīng)用

貪心算法應(yīng)用非常廣泛，特別電腦游戲AI或者一些推薦。

以經(jīng)典的跳躍游戲?yàn)槔?/p>

1.題目描述

給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。

數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。

判斷是否能夠到達(dá)最后一個(gè)位置。

2.問(wèn)題分析

先轉(zhuǎn)化為數(shù)學(xué)模型：給定一個(gè)數(shù)組，數(shù)組中每個(gè)位置的數(shù)字代表當(dāng)前位置i能夠向前跳躍num[i]的距離，然后判斷是否能夠從第一個(gè)位置跳到最后一個(gè)位置。

這道題的難點(diǎn)就在于每次跳多遠(yuǎn)的距離算合適呢？

如果從i的位置能跳num[i]距離最遠(yuǎn)能到達(dá)j的位置，那么這中間的任何一個(gè)位置我們都能跳到，但我們具體是跳到i–j之間的哪個(gè)位置才是真正合適的位置？

利用貪心的思想我們的目的是判斷最后能否跳到最后一個(gè)位置，其實(shí)就是只要能保證在i–j之間跳到一個(gè)能夠在下一次跳的更遠(yuǎn)的距離，那么這個(gè)位置就是最合適的位置。

本文由 @CARRIE 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來(lái)自Unsplash，基于CC0協(xié)議