ხარბი იდეა და როდის ცდება

ხარბი ალგორითმი პასუხს ნაბიჯ-ნაბიჯ აგებს და ყოველ ნაბიჯზე იმ ვარიანტს იღებს, რომელიც ამ წამს საუკეთესოდ გამოიყურება. გადაფიქრება არ იცის: გაკეთებული არჩევანი საბოლოოა.

ამიტომ ხარბი ალგორითმები მოკლე და სწრაფია, ჩვეულებრივ ერთი სორტირება და ერთი გავლა, O(n log n). მახე ისაა, რომ „ახლა საუკეთესო“ ყოველთვის „საერთოდ საუკეთესო“ არ არის. ხარბი ალგორითმი სწორია მხოლოდ მაშინ, როცა ორი პირობა სრულდება:

• ხარბი არჩევანის თვისება: არსებობს ოპტიმალური პასუხი, რომელიც ხარბი არჩევანით იწყება.
• ოპტიმალურობის თვისება ქვეამოცანებისთვის: ამ არჩევანის შემდეგ დარჩენილი იგივე ამოცანის უფრო პატარა ვერსიაა.

ე.ი. ხარბი არასდროს არის „თავისთავად სწორი“. ირჩევ წესს და ან ამტკიცებ, ან კონტრმაგალითით ამტყუნებ.

ავიღოთ ნებისმიერი ოპტიმალური განრიგი და შევხედოთ მის პირველ აქტივობას o₁. ხარბის პირველი არჩევანი g ყველაზე ადრე მთავრდება, ამიტომ end(g) ≤ end(o₁). ჩავანაცვლოთ o₁ g-ით: რაც o₁-ის შემდეგ იყო, g-ს ვერ გადაეფარება, რაოდენობა არ იცვლება, ესე იგი ახალი განრიგიც ოპტიმალურია და უკვე ხარბი არჩევანით იწყება.

იგივე მსჯელობა გავიმეოროთ დარჩენილ დროზე და ოპტიმალურ განრიგს ნაბიჯ-ნაბიჯ ხარბ განრიგად ვაქცევთ ისე, რომ არცერთ აქტივობას არ ვკარგავთ.

გაცვლის არგუმენტი ხარბი წესის დამტკიცების სტანდარტული ხერხია: აჩვენე, რომ ხარბი არჩევანის ოპტიმალურ ამოხსნაში ჩასმა მას არ აუარესებს. სხვა „ბუნებრივი“ წესები ამ ტესტს ვერ აბარებს: „ჯერ ადრე დაწყებული“ ერთ გრძელ აქტივობას ებლანდება, „ჯერ უმოკლესი“ კი მოკლეს, რომელიც ორ სხვას ეფარება.