الگوریتم حریصانه: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Haniyeh120 (بحث | مشارکت‌ها) |
|||
خط ۳۱:
به زبان ساده، در روش حریصانه طی هر مرحله یک عنصر به روش حریصانه به مجموعه جواب اضافه شده، شرط محدودیت‌ها بررسی شده و در صورت نبود مشکل، عنصر و عناصر بعدی به همین ترتیب به مجموعه جواب اضافه می‌شوند. در طی این گام‌ها اگر به یک شرط نهایی خاص برسیم، یا امکان انتخاب عنصر دیگری برای اضافه کردن به مجموعه جواب وجود نداشته باشد، الگوریتم پایان یافته و مجموعه جواب به دست آمده به عنوان جواب بهینه ارائه می‌شود. توجه داشته باشید که ممکن است بر اساس نوع مسئله، ترتیب اضافه شدن عناصر به مجموعه جواب اهمیت داشته باشد.<ref>{{پک| ابراهیم علایی فرادنبه - محمدرضا علایی|۱۳۹۲|ک=طراحی الگوریتم ایران|ص=258}}</ref>
<br /><source lang="c++" line="1">
set_greedy(C){
S = ∅;
خط ۸۲:
توجه کنید در انتخاب فوق، ملاک انتخاب، برای انتخاب بهترین سکه در هر مرحله (بهینهٔ محلی) سکه است و در انتخاب سکه در هر مرحله به انتخاب‌های قبلی و بعدی کاری نداریم. در این شیوه اجازهٔ فکر کردن دربارهٔ یک انتخاب انجام شده را نداریم؛ یعنی هنگامی که سکه‌ای پذیرفته شد به طور دائم جزو حل به حساب می‌آید و هنگامی هم که سکه‌ای رد می‌شود به‌طور دائم از حل کنار گذاشته می‌شود. <ref>{{پک| ابراهیم علایی فرادنبه - محمدرضا علایی|۱۳۹۲|ک=طراحی الگوریتم ایران|ص=259,258}}</ref>
کد مربوط به روش اول:<source lang="python" line="1">
procedure change ({c_1}, {c_2}, {...}, {c_r}: value of denominations of coin, where {c_1} > {c_2} > {...} > {c_r}; n : a positive integer) {
for i := 1 to r {
خط ۱۱۴:
و wi ،pi ،w همگی اعداد صحیح هستند. راه حل جستجوی جامع این است که همهٔ زیرمجموعه‌های این n قطعه را در نظر بگیریم، زیرمجموعه‌هایی را که وزن کل آن‌ها از w فراتر نرود، کنار می‌گذاریم و از میان آن‌هایی که باقی می‌ماند، آن را که بیشترین ارزش را دارد، انتخاب می‌کنیم. <ref>{{پک| ابراهیم علایی فرادنبه - محمدرضا علایی|۱۳۹۲|ک=طراحی الگوریتم ایران|ص=287,288}}</ref>
<br /><source lang="c++" line="1">
void greedy_knap_sack(w, n){
sort(p, w);
خط ۱۴۸:
<br />
<source lang="cpp" line="1">
void greedyColoring(std::vector<V>)
{
خط ۲۲۸:
<source lang="python" line="1">
def egyptianFraction(nr, dr):
print("The Egyptian Fraction " +
خط ۲۷۸:
==== '''[[الگوریتم_دکسترا|الگوریتم دایسترا (دکسترا)]]:''' ====
این الگوریتم در سال 1956 توسط [[ادسخر_دیکسترا|ادسخر دکسترا]] (Edsger Dijkstra) اثبات شد؛ که جزو الگوریتم‌های [[پیمایش گراف|جستجوی گراف]] است، و سؤالاتی چون [[مسئله یافتن کوتاه‌ترین مسیر|کوتاه‌ترین مسیر از یک رأس]] در [[گراف وزن‌دار|گراف‌های بدون وزن منفی]] را حل می‌کند. همچنین در [[مسیریابی (شبکه)|مسیریابی]] (routing) و به عنوان یک [[رویه (علوم رایانه)|زیرروال]] (subroutine) در الگوریتم‌های دیگر [[گراف (ریاضی)|گراف]] استفاده می‌شود. <ref>{{پک| Jesse Russell- Ronald Cohn|2012|ک=Dijkstra's Algorithm}}</ref>
<br /><syntaxhighlight lang="python" line="1">
def dijkstra(Adj, w, s):
parent = [None] * len(Adj) # Same
parent[s] = s # init
d = [math.inf] * len(Adj) # as
d[s] = 0 # before.
Q = PriorityQueue.build(Item(id=u, key=d[u]) for u in Adj)
while len(Q) > 0:
u = Q.delete_min().id # Delete and process u
for v in Adj[u]: # Same
if d[v] > d[u] + w(u,v): # relax
d[v] = d[u] + w(u,v) # as
parent[v] = u # before.
Q.decrease_key(id=v, new_key=d[v]) # NEW!
return d, parent
</syntaxhighlight>
== پانویس ==
| |||