الگوریتم هلد-کارپ

الگوریتم HELD-Karp که همچنین الگوریتم Bellman-Held-Karpet نامیده می‌شود، الگوریتم برنامه‌نویسی پویا در سال ۱۹۶۲ به‌طور مستقل توسط بلمن و توسط هلد و کارپ برای حل مسئله فروشنده دوره گرد (TSP) پیشنهاد شده‌است.

الگوریتم

TSP یک فرمت از مساله مدار همیلتونی است. این مساله می‌تواند به عنوان توضیح: پیدا کردن یک تور ازN شهرستانها در یک کشور (با فرض تمام شهرستانها برای بازدید قابل دسترسی هستند)، درتور باید (الف) بازدید هر شهرستان فقط یک بارباشد، (ب) به نقطه شروع بازگردیم، (ج) فاصله حداقل باشد. دیدگاه کلی تر، TSP به عنوان مسئله فروشنده دوره گرد متقارن (sTSP)، مشکل نامتقارن فروشنده دوره گرد (aTSP)، و مسئله فروشنده دوره گرد چند سفر (mTSP) طبقه‌بندی شده‌است.mTSPبه‌طور کلی به عنوان پاسخ مساله آرام مسیریابی وسائل نقلیه می‌باشد.

مدل گراف

sTSP: Let V= {v1 ,... , vn} مجموعه‌ای از شهرستانها می‌شود E= {(R,S):R,S∈V } لبه تنظیم می‌شود، وdrs = dsrیک اندازه‌گیری هزینه‌های مرتبط با لبه می‌باشد(r, s) ∈ E. aTSP:اگرdrs ≠ dsr برای حداقل یک(r, s)سپسsTSP می‌شود یک aTSP . .aTSP و sTSP در نمودارهای مختلف تعریف شده - کامل جهت دار و بدون جهت. sTSP می‌تواند در بسیاری از موارد، به عنوان یک مسئله از aTSP در نظر گرفته شود. mTSP: mTSPتعریف می‌شود به عنوان یک مجموعه داده از گره‌ها، اجازه وجودm فروشند واقع در یک گره انبارواحد وجود دارد. گره باقی‌مانده (شهرستانها) که توسط گره‌های میانی بازدید شده‌اند. سپس، mTSP شامل پیدا کردن تور برای همه m فروشنده، که همه شروع و پایان در انبار، به طوری که هر گره میانی است دقیقاً یک بار بازدید و کل هزینه بازدید از تمام گره به حداقل برسد.

الگوریتم

شرح در زیر روش برنامه‌نویسی پویا است: یک مشخصه بهینه‌سازی برای TSP وجود دارد: هرزیرمسیر از یک مسیر حداقل فاصله آن از خود حداقل فاصله است. محاسبه راه حل تمام زیر مسئله با شروع از کوچکترین است. هر گاه یک راه حل محاسبه نیاز به راه حل برای مشکلات کوچکتر با استفاده از معادلات بازگشتی بالا، نگاه کردن به این راه حل که در حال حاضر محاسبه می‌شود. برای محاسبه یک تور حداقل فاصله، استفاده از معادله نهایی برای تولید گره LST، و تکرار برای گره‌های دیگراست. برای این مشکل ما نمی‌توانند بفهمند که زیر مسئله ما نیاز به حل دارد، بنابراین ما همه آن‌ها را حل می‌کنیم. شماره شهرستانها ۱، ۲،، N و فرض کنیم که ما در شهرستان ۱ شروع، و فاصله بین شهرستان iو شهرستانj,dij است. زیر مجموعه S را در نظر بگیرید S⊆ {۲،، N} از شهرستانها و برای C ∈ S, let D(S, c) باشد حداقل فاصله، با شروع در شهرستان ۱، بازدید از تمام شهرستانها در S و در پایان در شهرستان ج است. مرحله اول:اگر S = {c}سپس D(S, c) = d1,cدرغیر اینصورت D(S, c) = minx∈S−c (D(S − c, x) + dx,c) مرحله دوم: حداقل فاصله برای یک تور کامل از تمام شهرستانها M = minc∈{2,... ,N} (D({2, . . . , N}, c) + dc,۱) یک تور n1 , . . . , nN است از حداقل فاصله فقط زمانی که آن را برآورده شود M = D({2, . . . , N}, nN) + dnN,1

به عنوان مثال

ماتریس فاصله:

توابع توضیحات: g (X، S) - با شروع از ۱، مسیر مینیمم هزینهٔ به پایان می‌رسد در راس X، عبور راس در مجموعه S دقیقاً یک بار cxy - هزینه لبه به پایان می‌رسد در x از Y P(X,S) - راس دوم به گذشته به x از مجموعه S. مورد استفاده برای ساخت مسیر TSP برگشت به آخر..

k = 0, null set:
Set ∅:
  g(2, ∅) = c21 = ۱
  g(3, ∅) = c31 = ۱۵
  g(4, ∅) = c41 = ۶
k = 1, consider sets of 1 element:
Set {2}:
  g(3,{2}) = c32 + g(2, ∅) = c32 + c21 = ۷ + ۱ = 8 p(۳,{۲}) = ۲
  g(4,{2}) = c42 + g(2, ∅) = c42 + c21 = ۳ + ۱ = 4 p(۴,{۲}) = ۲
Set {3}:
  g(2,{3}) = c23 + g(3, ∅) = c23 + c31 = ۶ + ۱۵ = 21 p(۲,{۳}) = ۳
  g(4,{3}) = c43 + g(3, ∅) = c43 + c31 = ۱۲ + ۱۵ = 27 p(۴,{۳}) = ۳
Set {4}:
  g(2,{4}) = c24 + g(4, ∅) = c24 + c41 = ۴ + ۶ = 10 p(۲,{۴}) = ۴
  g(3,{4}) = c34 + g(4, ∅) = c34 + c41 = ۸ + ۶ = 14 p(۳,{۴}) = ۴
k = 2, consider sets of 2 elements:
Set {2,3}:
  g(4,{2,3}) = min {c42 + g(2,{3}), c43 + g(3,{2})} = min {3+21, 12+8}= min {24, 20}= ۲۰
  p(4,{2,3}) = ۳
Set {2,4}:
  g(3,{2,4}) = min {c32 + g(2,{4}), c34 + g(4,{2})} = min {7+10, 8+4}= min {17, 12} = ۱۲
  p(3,{2,4}) = ۴
Set {3,4}:
  g(2,{3,4}) = min {c23 + g(3,{4}), c24 + g(4,{3})} = min {6+14, 4+27}= min {20, 31}= ۲۰
  p(2,{3,4}) = ۳
Length of an optimal tour:
 f = g(1,{2,3,4}) = min { c12 + g(2,{3,4}), c13 + g(3,{2,4}), c14 + g(4,{2,3}) }
= min {2 + 20, 9 + 12, 10 + 20} = min {22, 21, 30} = ۲۱
Successor of node 1: p(1,{2,3,4}) = ۳
Successor of node 3: p(3, {2,4}) = ۴
Successor of node 4: p(4, {2}) = ۲
Backtracking the optimal TSP tour reaches: 1 → ۲ → ۴ → ۳ → ۱

شبه برنامه

function algorithm TSP (G, n)
  for k := 2 to n do
  C({1, k}, k) := d1,k
  end for
  for s := 3 to n do
  for all S ⊆ {1, 2, . . . , n}, |S| = s do
  for all k ∈ S do
  {C(S, k) = minm≠1,m≠k,m∈S [C(S − {k}, m) + dm,k ]}
  end for
  end for
  end for
  opt := mink≠1 [C({1, 2, 3, . . . , n}, k) + d1,k]
  return (opt)
  end