எடுத்துக்காட்டுகளுடன் பேராசை அல்காரிதம்: பேராசை முறை மற்றும் அணுகுமுறை

பேராசை அல்காரிதம் என்றால் என்ன?

இல் பேராசை அல்காரிதம் செயல்பாட்டின் எந்த கட்டத்திலும் அந்த வளத்தின் அதிகபட்ச, உடனடி கிடைக்கும் தன்மையின் அடிப்படையில் ஒரு தொகுப்பு வளங்கள் மீண்டும் மீண்டும் பிரிக்கப்படுகின்றன.

பேராசை அணுகுமுறையின் அடிப்படையில் ஒரு சிக்கலைத் தீர்க்க, இரண்டு நிலைகள் உள்ளன

  1. பொருட்களின் பட்டியலை ஸ்கேன் செய்கிறது
  2. உகப்பாக்கம்

இந்த நிலைகள் இந்த பேராசை அல்காரிதம் டுடோரியலில், வரிசையின் பிரிவின் போக்கில் இணையாக மூடப்பட்டுள்ளன.

பேராசை கொண்ட அணுகுமுறையைப் புரிந்து கொள்ள, நீங்கள் மறுபயன்பாடு மற்றும் சூழல் மாறுதல் பற்றிய வேலை அறிவு வேண்டும். குறியீட்டை எவ்வாறு கண்டுபிடிப்பது என்பதைப் புரிந்துகொள்ள இது உதவுகிறது. உங்கள் சொந்த தேவையான மற்றும் போதுமான அறிக்கைகளின் அடிப்படையில் பேராசை முன்னுதாரணத்தை நீங்கள் வரையறுக்கலாம்.

இரண்டு நிபந்தனைகள் பேராசை முன்னுதாரணத்தை வரையறுக்கின்றன.

  • ஒவ்வொரு படிப்படியான தீர்வும் ஒரு பிரச்சனையை அதன் சிறந்த ஏற்றுக்கொள்ளப்பட்ட தீர்வை நோக்கி கட்டமைக்க வேண்டும்.
  • பிரச்சனையின் கட்டமைப்பை ஒரு குறிப்பிட்ட எண்ணிக்கையிலான பேராசை படிகளில் நிறுத்த முடிந்தால் போதுமானது.

கோட்பாடு தொடர்ந்து, பேராசை தேடல் அணுகுமுறையுடன் தொடர்புடைய வரலாற்றை விவரிப்போம்.

இந்த பேராசை அல்காரிதம் டுடோரியலில், நீங்கள் கற்றுக்கொள்வீர்கள்:

பேராசை வழிமுறைகளின் வரலாறு

பேராசை கொண்ட வழிமுறைகளின் ஒரு முக்கிய மைல்கல் இங்கே:

  • பேராசை அல்காரிதங்கள் 1950 களில் பல வரைபட நடை வழிமுறைகளுக்கு கருத்தியல் செய்யப்பட்டன.
  • Esdger Djikstra குறைந்த பரந்த மரங்களை உருவாக்குவதற்கான வழிமுறையை கருத்தியல் செய்தது. அவர் நெதர்லாந்து தலைநகர் ஆம்ஸ்டர்டாமில் உள்ள பாதைகளின் இடைவெளியைக் குறைப்பதை நோக்கமாகக் கொண்டார்.
  • அதே தசாப்தத்தில், ப்ரிம் மற்றும் க்ருஸ்கல் எடையுள்ள பாதைகளில் பாதை செலவுகளைக் குறைப்பதை அடிப்படையாகக் கொண்ட தேர்வுமுறை உத்திகளை அடைந்தனர்.
  • 70 களில், அமெரிக்க ஆராய்ச்சியாளர்கள், கோர்மென், ரிவெஸ்ட் மற்றும் ஸ்டீன் ஆகியோர் அல்காரிதம்ஸ் புத்தகத்திற்கான கிளாசிக்கல் அறிமுகத்தில் பேராசை கொண்ட தீர்வுகளை மீண்டும் மீண்டும் உட்கட்டமைப்பு செய்ய முன்மொழிந்தனர்.
  • பேராசை தேடல் முன்னுதாரணம் 2005 ஆம் ஆண்டில் என்ஐஎஸ்டி பதிவுகளில் வேறு வகையான தேர்வுமுறை உத்தியாக பதிவு செய்யப்பட்டது.
  • இன்றுவரை, வலையை இயக்கும் நெறிமுறைகளான திறந்த-குறுகிய-பாதை-முதல் (OSPF) மற்றும் பல நெட்வொர்க் பாக்கெட் மாறுதல் நெறிமுறைகள் ஒரு பிணையத்தில் செலவழிக்கும் நேரத்தைக் குறைக்க பேராசை மூலோபாயத்தைப் பயன்படுத்துகின்றன.

பேராசை உத்திகள் மற்றும் முடிவுகள்

தர்க்கம் அதன் எளிதான வடிவத்தில் 'பேராசை' அல்லது 'பேராசை இல்லை' என்று கொதிக்கப்பட்டது. ஒவ்வொரு அல்காரிதம் கட்டத்திலும் முன்னேற எடுக்கப்பட்ட அணுகுமுறையால் இந்த அறிக்கைகள் வரையறுக்கப்பட்டன.

உதாரணமாக, ஜிக்ஸ்ட்ராவின் அல்காரிதம் ஒரு செலவுச் செயல்பாட்டைக் கணக்கிடுவதன் மூலம் இணையத்தில் புரவலர்களை அடையாளம் காணும் படிநிலை பேராசை மூலோபாயத்தைப் பயன்படுத்தியது. செலவுச் செயல்பாட்டால் திரும்பிய மதிப்பு அடுத்த பாதை 'பேராசை' அல்லது 'பேராசை இல்லாதது' என்பதை தீர்மானிக்கிறது.

சுருக்கமாக, எந்த கட்டத்திலும் அது உள்ளூர் பேராசை இல்லாத ஒரு படியை எடுத்தால் ஒரு வழிமுறை பேராசைப்படுவதை நிறுத்துகிறது. பேராசையின் பிரச்சனைகள் மேலும் பேராசையின் நோக்கம் இல்லாமல் நிறுத்தப்படும்.

பேராசை அணுகுமுறையின் பண்புகள்

பேராசை முறையின் முக்கிய பண்புகள்:

  • செலவுகள் அல்லது மதிப்பு பண்புகளுடன், ஆர்டர் செய்யப்பட்ட ஆதாரங்களின் பட்டியல் உள்ளது. இவை ஒரு கணினியில் உள்ள தடைகளை அளவிடுகின்றன.
  • ஒரு கட்டுப்பாடு பொருந்தும் நேரத்தில் நீங்கள் அதிகபட்ச அளவு வளங்களை எடுப்பீர்கள்.
  • உதாரணமாக, ஒரு செயல்பாட்டு திட்டமிடல் பிரச்சனையில், வளச் செலவுகள் மணிநேரங்களில் இருக்கும், மேலும் செயல்பாடுகள் தொடர் வரிசையில் செய்யப்பட வேண்டும்.

பேராசை அணுகுமுறையை ஏன் பயன்படுத்த வேண்டும்?

பேராசை அணுகுமுறையைப் பயன்படுத்துவதற்கான காரணங்கள் இங்கே:

  • பேராசை கொண்ட அணுகுமுறை சில பரிமாற்றங்களைக் கொண்டுள்ளது, இது உகப்பாக்கத்திற்கு ஏற்றதாக இருக்கலாம்.
  • மிக முக்கியமான தீர்வை உடனடியாக அடைவது ஒரு முக்கிய காரணம். செயல்பாட்டுத் தேர்வு சிக்கலில் (கீழே விளக்கப்பட்டுள்ளது), தற்போதைய செயல்பாட்டை முடிப்பதற்கு முன் அதிக செயல்பாடுகளைச் செய்ய முடிந்தால், இந்த செயல்பாடுகளை ஒரே நேரத்தில் செய்ய முடியும்.
  • மற்றொரு காரணம், ஒரு பிரச்சினையை ஒரு நிபந்தனையின் அடிப்படையில் மீண்டும் மீண்டும் பிரிப்பது, அனைத்து தீர்வுகளையும் இணைக்க வேண்டிய அவசியமில்லை.
  • செயல்பாட்டுத் தேர்வு பிரச்சனையில், உருப்படிகளின் பட்டியலை ஒரு முறை மட்டுமே ஸ்கேன் செய்து சில செயல்பாடுகளைக் கருத்தில் கொண்டு 'ரிகர்சிவ் டிவிஷன்' படி அடையப்படுகிறது.

செயல்பாட்டு தேர்வு சிக்கலை எவ்வாறு தீர்ப்பது

செயல்பாட்டு திட்டமிடல் எடுத்துக்காட்டில், ஒவ்வொரு செயல்பாட்டிற்கும் ஒரு 'தொடக்கம்' மற்றும் 'முடிக்க' நேரம் உள்ளது. ஒவ்வொரு செயல்பாடும் குறிப்புக்கு ஒரு எண்ணால் குறியிடப்படுகிறது. இரண்டு செயல்பாட்டு வகைகள் உள்ளன.

  1. செயல்பாடாக கருதப்படுகிறது : ஆக்டிவிட்டி, இது மீதமுள்ள ஒன்றுக்கு மேற்பட்ட செயல்பாடுகளைச் செய்யும் திறன் பகுப்பாய்வு செய்யப்படும் குறிப்பு.
  2. மீதமுள்ள செயல்பாடுகள்: கருதப்பட்ட செயல்பாட்டிற்கு முன்னதாக ஒன்று அல்லது அதற்கு மேற்பட்ட குறியீடுகளில் செயல்பாடுகள்.

மொத்த கால அளவு செயல்பாட்டைச் செய்வதற்கான செலவை அளிக்கிறது. அதாவது (பூச்சு - தொடக்கம்) ஒரு செயல்பாட்டின் செலவாக நமக்கு காலத்தை அளிக்கிறது.

பேராசை அளவு என்பது ஒரு கருதப்பட்ட செயல்பாட்டின் போது நீங்கள் செய்யக்கூடிய மீதமுள்ள செயல்பாடுகளின் எண்ணிக்கை என்பதை நீங்கள் அறிந்து கொள்வீர்கள்.

பேராசை அணுகுமுறையின் கட்டிடக்கலை

படி 1)

செயல்பாட்டு செலவினங்களின் பட்டியலை ஸ்கேன் செய்து, குறியீட்டு 0 என கருதப்படும் குறியீடாகத் தொடங்குங்கள்.

படி 2)

அதிகப்படியான செயல்பாடுகளை அந்த நேரத்தில் முடிக்க முடிந்தால், கருதப்படும் செயல்பாடு முடிவடைகிறது, ஒன்று அல்லது அதற்கு மேற்பட்ட மீதமுள்ள செயல்பாடுகளைத் தேடத் தொடங்குங்கள்.

படி 3)

மீதமுள்ள செயல்பாடுகள் இல்லை என்றால், தற்போதைய மீதமுள்ள செயல்பாடு அடுத்ததாகக் கருதப்படும் செயல்பாடாகும். புதியதாகக் கருதப்படும் செயல்பாட்டுடன் படி 1 மற்றும் படி 2 ஐ மீண்டும் செய்யவும். மீதமுள்ள நடவடிக்கைகள் எதுவும் இல்லை என்றால், படி 4 க்குச் செல்லவும்.

படி 4)

கருதப்பட்ட குறியீடுகளின் இணைப்பைத் திருப்பித் தரவும். செயல்திறனை அதிகரிக்க பயன்படும் செயல்பாட்டு குறியீடுகள் இவை.

பேராசை அணுகுமுறையின் கட்டிடக்கலை



குறியீடு விளக்கம்

 #include #include #include #define MAX_ACTIVITIES 12 

குறியீட்டின் விளக்கம்:

  1. தலைப்பு கோப்புகள்/வகுப்புகள் சேர்க்கப்பட்டுள்ளது
  2. பயனரால் வழங்கப்பட்ட அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகள்.
 using namespace std; class TIME { public: int hours; public: TIME() { hours = 0; } }; 

குறியீட்டின் விளக்கம்:

  1. ஸ்ட்ரீமிங் செயல்பாடுகளுக்கான பெயர்வெளி.
  2. TIME க்கான வகுப்பு வரையறை
  3. ஒரு மணி நேர முத்திரை.
  4. ஒரு நேர இயல்புநிலை கட்டமைப்பாளர்
  5. மணி மாறிகள்.
 class Activity { public: int index; TIME start; TIME finish; public: Activity() { start = finish = TIME(); } }; 

குறியீட்டின் விளக்கம்:

  1. செயல்பாட்டிலிருந்து ஒரு வகுப்பு வரையறை
  2. கால அளவை வரையறுக்கும் நேர முத்திரைகள்
  3. அனைத்து நேர முத்திரைகளும் இயல்புநிலை கட்டமைப்பாளரில் 0 ஆக ஆரம்பிக்கப்படும்
 class Scheduler { public: int considered_index,init_index; Activity *current_activities = new Activity[MAX_ACTIVITIES]; Activity *scheduled; 

குறியீட்டின் விளக்கம்:

  1. திட்டமிடுபவர் வகுப்பு வரையறையின் பகுதி 1.
  2. கருதப்பட்ட அட்டவணை வரிசையை ஸ்கேன் செய்வதற்கான தொடக்க புள்ளியாகும்.
  3. சீரற்ற நேர முத்திரைகளை ஒதுக்க துவக்க குறியீடு பயன்படுத்தப்படுகிறது.
  4. புதிய ஆபரேட்டரைப் பயன்படுத்தி செயல்பாட்டுப் பொருட்களின் வரிசை மாறும் வகையில் ஒதுக்கப்படுகிறது.
  5. திட்டமிடப்பட்ட சுட்டிக்காட்டி பேராசைக்கான தற்போதைய அடிப்படை இடத்தை வரையறுக்கிறது.
 Scheduler() { considered_index = 0; scheduled = NULL; ... ... 

குறியீட்டின் விளக்கம்:

  1. திட்டமிடுபவர் கட்டமைப்பாளர் - திட்டமிடுபவர் வகுப்பு வரையறையின் பகுதி 2.
  2. கருதப்பட்ட குறியீட்டு தற்போதைய ஸ்கேனின் தற்போதைய தொடக்கத்தை வரையறுக்கிறது.
  3. தற்போதைய பேராசை அளவு தொடக்கத்தில் வரையறுக்கப்படவில்லை.
 for(init_index = 0; init_index 

குறியீட்டின் விளக்கம்:

  1. தற்போது திட்டமிடப்பட்டுள்ள ஒவ்வொரு செயல்பாட்டின் தொடக்க நேரங்களையும் இறுதி நேரங்களையும் துவக்க ஏ ஃபார் லூப்.
  2. தொடக்க நேர துவக்கம்.
  3. முடிவு நேர துவக்கம் எப்போதும் தொடக்க நேரத்திற்குப் பிறகு அல்லது சரியாக.
  4. ஒதுக்கப்பட்ட காலத்தை அச்சிட பிழைத்திருத்த அறிக்கை.
 public: Activity * activity_select(int); }; 

குறியீட்டின் விளக்கம்:

  1. பகுதி 4 - திட்டமிடல் வகுப்பு வரையறையின் கடைசி பகுதி.
  2. செயல்பாட்டைத் தேர்ந்தெடுக்கும் செயல்பாடு ஒரு தொடக்கப்புள்ளி குறியீட்டை அடித்தளமாக எடுத்து பேராசை கொண்ட தேடலை பேராசை கொண்ட உப பிரச்சனைகளாக பிரிக்கிறது.
 Activity * Scheduler :: activity_select(int considered_index) { this->considered_index = considered_index; int greedy_extent = this->considered_index + 1; … … 

  1. நோக்கம் தீர்மானம் ஆபரேட்டரைப் பயன்படுத்தி (: :), செயல்பாட்டு வரையறை வழங்கப்படுகிறது.
  2. கருதப்படும் அட்டவணை மதிப்பு மூலம் அழைக்கப்படும் குறியீடாகும். பேராசை_எக்ஸ்டென்ட் என்பது ஒரு குறியீட்டுக்கு பிறகு தொடங்கப்பட்ட ஒரு குறியீடாகும்.
 Activity * Scheduler :: activity_select(int considered_index) { while( (greedy_extent current_activities[greedy_extent]).start.hours current_activities[considered_index]).finish.hours )) { printf('
Schedule start:%d 
finish%d
 activity:%d
', (this->current_activities[greedy_extent]).start.hours, (this->current_activities[greedy_extent]).finish.hours, greedy_extent + 1); greedy_extent++; } … ... 

குறியீட்டின் விளக்கம்:

  1. முக்கிய தர்க்கம்- பேராசை அளவு மட்டுமே நடவடிக்கைகளின் எண்ணிக்கை.
  2. தற்போதைய செயல்பாட்டின் தொடக்க நேரங்கள், கருதப்படும் செயல்பாடு (கருதப்படும் குறியீட்டால் கொடுக்கப்பட்டவை) முடிவதற்கு முன்பே திட்டமிடப்பட்டவையாகச் சரிபார்க்கப்படும்.
  3. இது முடிந்தவரை, ஒரு விருப்ப பிழைத்திருத்த அறிக்கை அச்சிடப்படுகிறது.
  4. செயல்பாட்டு வரிசையில் அடுத்த அட்டவணைக்கு முன்னேறுங்கள்
 ... if ( greedy_extent <= MAX_ACTIVITIES ) { return activity_select(greedy_extent); } else { return NULL; } } 

குறியீட்டின் விளக்கம்:

  1. அனைத்து நடவடிக்கைகளும் உள்ளடக்கப்பட்டிருந்தால் நிபந்தனை சரிபார்ப்பு.
  2. இல்லையென்றால், தற்போதைய புள்ளியாகக் கருதப்படும் குறியீட்டைக் கொண்டு உங்கள் பேராசையை மீண்டும் தொடங்கலாம். இது பிரச்சனை அறிக்கையை பேராசையுடன் பிரிக்கும் ஒரு தொடர்ச்சியான நடவடிக்கை.
  3. ஆம் எனில், பேராசையை விரிவுபடுத்துவதற்கான எந்த வாய்ப்பும் இல்லாமல் அது அழைப்பாளருக்குத் திரும்பும்.
 int main() { Scheduler *activity_sched = new Scheduler(); activity_sched->scheduled = activity_sched->activity_select( activity_sched->considered_index); return 0; } 

குறியீட்டின் விளக்கம்:

  1. அட்டவணையாளரை அழைக்க முக்கிய செயல்பாடு பயன்படுத்தப்படுகிறது.
  2. ஒரு புதிய அட்டவணை நிறுவப்பட்டுள்ளது.
  3. செயல்பாடு தேர்ந்தெடுக்கப்பட்ட செயல்பாடு, இது வகை செயல்பாட்டின் சுட்டிக்காட்டியை அளிக்கிறது, பேராசை தேடலுக்குப் பிறகு அழைப்பாளருக்குத் திரும்பும்.

வெளியீடு: | _+_ |

பேராசை வழிமுறைகளின் தீமைகள்

வரிசைப்படுத்துதல் போன்ற ஒவ்வொரு உபப்பிரச்சனைக்கும் தீர்வு தேவைப்படும் பேராசைப் பிரச்சினைகளுக்கு இது ஏற்றதல்ல.

இத்தகைய பேராசை வழிமுறை பயிற்சி சிக்கல்களில், பேராசை முறை தவறாக இருக்கலாம்; மோசமான நிலையில் உகந்த தீர்வுக்கு கூட வழிவகுக்கும்.

எனவே பேராசை கொண்ட வழிமுறைகளின் தீமை தற்போதைய பேராசை நிலைக்கு முன்னால் என்ன இருக்கிறது என்று தெரியாமல் பயன்படுத்துகிறது.

பேராசை முறையின் தீமையின் சித்திரம் கீழே:

இங்கே காட்டப்படும் பேராசை ஸ்கேனில் ஒரு மரமாக (அதிக மதிப்பு அதிக பேராசை), ஒரு வழிமுறை நிலை மதிப்பு: 40, அடுத்த மதிப்பாக 29 ஐ எடுக்க வாய்ப்புள்ளது. மேலும், அதன் தேடலானது 12. இல் முடிவடைகிறது, இது 41 மதிப்பாகும்.

இருப்பினும், அல்காரிதம் துணை-உகந்த பாதையை எடுத்தால் அல்லது ஒரு வெற்றி மூலோபாயத்தை ஏற்றுக்கொண்டால். பின்னர் 25 ஐத் தொடர்ந்து 40 வரும், மற்றும் ஒட்டுமொத்த செலவு மேம்பாடு 65 ஆக இருக்கும், இது ஒரு துணை முடிவாக 24 புள்ளிகள் அதிகமாகும்.

பேராசை வழிமுறைகளின் எடுத்துக்காட்டுகள்

பெரும்பாலான நெட்வொர்க்கிங் வழிமுறைகள் பேராசை அணுகுமுறையைப் பயன்படுத்துகின்றன. சில பேராசை வழிமுறை எடுத்துக்காட்டுகளின் பட்டியல் இங்கே:

  • ப்ரிம்ஸின் குறைந்தபட்ச பரவல் மர வழிமுறை
  • பயண விற்பனையாளர் பிரச்சனை
  • வரைபடம் - வரைபட வண்ணம்
  • க்ருஸ்கலின் குறைந்தபட்ச பரப்பு மர வழிமுறை
  • டிஜ்க்ஸ்ட்ராவின் குறைந்தபட்ச பரந்த மரம் வழிமுறை
  • வரைபடம் - வெர்டெக்ஸ் கவர்
  • நாப்சாக் பிரச்சனை
  • வேலை திட்டமிடல் பிரச்சனை

சுருக்கம்:

சுருக்கமாக, கட்டுரை பேராசை முன்னுதாரணத்தை வரையறுத்தது, பேராசை உகப்பாக்கம் மற்றும் மறுபிறப்பு எப்படி ஒரு புள்ளி வரை சிறந்த தீர்வைப் பெற உதவும் என்பதை காட்டியது. பேராசை அல்காரிதம் பைதான், சி, சி#, பிஎச்பி, ஜாவா போன்ற பல மொழிகளில் பிரச்சனையைத் தீர்ப்பதற்கான பயன்பாடு பரவலாகப் பயன்படுத்தப்படுகிறது. அணுகுமுறை. இறுதியில், பேராசை அணுகுமுறையின் பயன்பாட்டின் தீமைகள் விளக்கப்பட்டது.