Look-ahead (backtracking)
ব্যাকট্র্যাকিং অ্যালগরিদমগুলিতে, সামনের দিকে তাকানো হল একটি উপপ্রক্রিয়ার জন্য সাধারণ শব্দ যা তার একটি মান মূল্যায়নের জন্য একটি শাখা পরিবর্তনশীল বেছে নেওয়ার প্রভাবগুলি পূর্বাভাস করার চেষ্টা করে। সামনের দিকে তাকানোর দুটি প্রধান লক্ষ্য হল পরবর্তী মূল্যায়নের জন্য একটি পরিবর্তনশীল নির্বাচন করা এবং সেটিকে বরাদ্দ করার জন্য মানগুলির ক্রম নির্বাচন করা। সীমাবদ্ধ সন্তুষ্টি একটি সাধারণ সীমাবদ্ধ সন্তুষ্টি সমস্যায়, প্রতিটি পরিবর্তনশীল একটি ডোমেনে একটি মান নিতে পারে। একটি ব্যাকট্র্যাকিং অ্যালগরিদম তাই পুনরাবৃত্তভাবে একটি পরিবর্তনশীল বেছে নেয় এবং তার প্রতিটি সম্ভাব্য মান পরীক্ষা করে; প্রতিটি মানের জন্য অ্যালগরিদম পুনরাবৃত্তিমূলকভাবে চালানো হয়। মূল্যায়নের জন্য একটি প্রদত্ত পরিবর্তনশীল বেছে নেওয়ার প্রভাবগুলি পরীক্ষা করতে বা এটিকে দেওয়ার জন্য মানগুলির ক্রম নির্ধারণ করতে লুক ফরোয়ার্ড ব্যবহার করা হয়। সামনের দিকে তাকানোর কৌশল একটি চলকের উপর একটি নির্দিষ্ট অ্যাসাইনমেন্টের প্রভাব মূল্যায়নের সহজ কৌশলকে ফরওয়ার্ড চেকিং বলা হয়। বর্তমান আংশিক সমাধান এবং মূল্যায়নের জন্য একটি প্রার্থী নিয়োগের পরিপ্রেক্ষিতে, এটি পরীক্ষা করে যে অন্য একটি পরিবর্তনশীল একটি সামঞ্জস্যপূর্ণ মান নিতে পারে কিনা। অন্য কথায়, এটি প্রথমে বিবেচিত চলকের জন্য সম্ভাব্য মান সহ বর্তমান আংশিক সমাধানটি প্রসারিত করে; তারপরে এটি অন্যান্য প্রতিটি চলককে বিবেচনা করে যা এখনও বরাদ্দ করা হয়নি, এবং বর্ধিত আংশিক সমাধানের সাথে সামঞ্জস্যপূর্ণ কোনও মূল্যায়ন বিদ্যমান কিনা তা পরীক্ষা করে। আরও সাধারণভাবে, ফরওয়ার্ড চেকিং বর্ধিত অ্যাসাইনমেন্টের সাথে সামঞ্জস্যপূর্ণ মানগুলি নির্ধারণ করে। একটি চেহারা-এগিয়ে কৌশল যা আরও বেশি সময়সাপেক্ষ হতে পারে তবে আরও ভাল ফলাফল তৈরি করতে পারে তা চাপের ধারাবাহিকতার উপর ভিত্তি করে। অর্থাৎ, একটি নতুন চলকের জন্য একটি মান সহ বর্ধিত আংশিক সমাধান দেওয়া হলে, এটি সমস্ত অনির্দিষ্ট চলকের জন্য চাপের সামঞ্জস্য প্রয়োগ করে। অন্য কথায়, যে কোনও অনির্দিষ্ট চলকের জন্য, যে মানগুলি ধারাবাহিকভাবে অন্য চলকের মধ্যে প্রসারিত করা যায় না সেগুলি সরানো হয়। ফরওয়ার্ড চেকিং এবং চাপের সামঞ্জস্যের মধ্যে পার্থক্য হল যে, প্রথমটি শুধুমাত্র সামঞ্জস্যের জন্য একটি একক অনির্দিষ্ট পরিবর্তনশীলকে পরীক্ষা করে, অন্যদিকে দ্বিতীয়টি পারস্পরিক সামঞ্জস্যের জন্য অনির্ধারিত পরিবর্তনশীলের জোড়াও পরীক্ষা করে। সীমাবদ্ধতা সন্তুষ্টি সমস্যা সমাধানের জন্য লুক-ফরোয়ার্ড ব্যবহার করার সবচেয়ে সাধারণ উপায় হল আর্ক-কন্সিস্টেন্সি (এম. এ. সি) অ্যালগরিদম বজায় রাখা। চাপের সামঞ্জস্যের সাথে জড়িত আরও দুটি পদ্ধতি হল পূর্ণ এবং আংশিক সামনের দিকে তাকানো। তারা চাপের সামঞ্জস্য প্রয়োগ করে, তবে প্রতিটি জোড়া চলকের জন্য নয়। বিশেষত, সম্পূর্ণ চেহারা প্রতিটি জোড়া অনির্ধারিত চলক বিবেচনা করে এবং তাদের মধ্যে চাপের সামঞ্জস্য প্রয়োগ করে। এটি বৈশ্বিক চাপের ধারাবাহিকতা প্রয়োগ করার চেয়ে আলাদা, যার জন্য সম্ভবত এক জোড়া পরিবর্তনশীলকে একাধিকবার পুনর্বিবেচনার প্রয়োজন হতে পারে। পরিবর্তে, একবার সম্পূর্ণ নজর দেওয়ার পরে এক জোড়া চলকের মধ্যে চাপের সামঞ্জস্য প্রয়োগ করা হয়, এই জুটিকে আর বিবেচনা করা হয় না। সামনের দিকে আংশিক চেহারা একই রকম, তবে ভেরিয়েবলের একটি প্রদত্ত ক্রম বিবেচনা করা হয় এবং প্রতিটি জুটির জন্য চাপের সামঞ্জস্য কেবল একবার প্রয়োগ করা হয়। চাপের সামঞ্জস্যের উপর ভিত্তি করে এগিয়ে দেখুন পথের সামঞ্জস্য এবং সাধারণ আই-সামঞ্জস্য বা সম্পর্কিত চাপের সামঞ্জস্যের সাথে কাজ করার জন্যও প্রসারিত করা যেতে পারে। সামনের দিকে তাকানোর ফলাফলগুলি মূল্যায়নের জন্য পরবর্তী পরিবর্তনশীল এবং এই পরিবর্তনশীলকে দেওয়ার জন্য মানগুলির ক্রম নির্ধারণ করতে ব্যবহৃত হয়। বিশেষত, যে কোনও অনির্দিষ্ট পরিবর্তনশীল এবং মানের জন্য, সেই পরিবর্তনশীলকে সেই মানের সাথে সেট করার প্রভাবগুলি অনুমান করে। পরবর্তী চলকের পছন্দ এবং এটি দেওয়ার জন্য পরবর্তী মানের পছন্দটি পরিপূরক, এতে মানটি সাধারণত এমনভাবে বেছে নেওয়া হয় যাতে একটি সমাধান (যদি থাকে) যত তাড়াতাড়ি সম্ভব পাওয়া যায়, যখন পরবর্তী চলকটি সাধারণত এমনভাবে বেছে নেওয়া হয় যাতে অসন্তোষজনক (যদি বর্তমান আংশিক সমাধানটি অসন্তুষ্ট হয়) যত তাড়াতাড়ি সম্ভব প্রমাণিত হয়। মূল্যায়নের জন্য পরবর্তী চলকের পছন্দ বিশেষভাবে গুরুত্বপূর্ণ, কারণ এটি চলমান সময়ে সূচকীয় পার্থক্য তৈরি করতে পারে। যত তাড়াতাড়ি সম্ভব অসন্তোষজনক প্রমাণ করার জন্য, বরাদ্দ হওয়ার পরে কয়েকটি বিকল্প রেখে যাওয়া চলকগুলি পছন্দের। এই ধারণাটি শুধুমাত্র পরিবর্তনশীল/মান জোড়ার সন্তোষজনকতা বা অসন্তোষযোগ্যতা পরীক্ষা করে বাস্তবায়িত করা যেতে পারে। বিশেষত, পরবর্তী যে পরিবর্তনশীলটি বেছে নেওয়া হয় তা হল ন্যূনতম সংখ্যক মান যা বর্তমান আংশিক সমাধানের সাথে সামঞ্জস্যপূর্ণ। পরিবর্তে, সামঞ্জস্যতা কেবল আংশিক সামঞ্জস্য পরীক্ষা করে বা উপরে আলোচিত বিবেচনা করা যে কোনও কৌশল ব্যবহার করে মূল্যায়ন করা যেতে পারে। একটি পরিবর্তনশীলকে সম্ভাব্যভাবে বরাদ্দ করার জন্য নিম্নলিখিত তিনটি পদ্ধতি রয়েছেঃ ন্যূনতম-দ্বন্দ্বঃ পছন্দের মানগুলি হল সেগুলি যা অনির্দিষ্ট ভেরিয়েবলের ডোমেন থেকে সর্বনিম্ন মোট মানগুলি সরিয়ে দেয় যা সামনের দিকে তাকিয়ে মূল্যায়ন করা হয়; সর্বাধিক-ডোমেন-আকারঃ পছন্দের মানগুলি হল সেগুলি যা অনির্দিষ্ট ভেরিয়েবলের জন্য তৈরি করা ক্ষুদ্রতম ডোমেনে মানগুলির সংখ্যা সর্বাধিক করে, যা সামনের দিকে তাকিয়ে মূল্যায়ন করা হয়; সমাধানগুলি অনুমান করুনঃ পছন্দের মানগুলি হল সেগুলি যা সর্বাধিক সংখ্যক সমাধান তৈরি করে, যেমন মূল্যায়ন করা হয় সামনের দিকে এই অনুমান করে যে অনির্দিষ্ট ভেরিয়েবলের ডোমেনে থাকা সমস্ত মান একে অপরের সাথে সামঞ্জস্যপূর্ণ; অন্য কথায়, একটি মানের জন্য অগ্রাধিকার প্রাপ্ত হয় সামনের দিকে তাকানোর ফলে সমস্ত ডোমেনের আকারকে গুণ করে। পরীক্ষাগুলি প্রমাণ করেছে যে এই কৌশলগুলি বড় সমস্যাগুলির জন্য কার্যকর, বিশেষত ক্ষুদ্র-দ্বন্দ্বগুলির ক্ষেত্রে। র্যান্ডমাইজেশন কখনও কখনও একটি পরিবর্তনশীল বা মান বেছে নেওয়ার জন্যও ব্যবহৃত হয়। উদাহরণস্বরূপ, যদি কোনও পরিমাপ অনুযায়ী দুটি চলক সমানভাবে পছন্দ করা হয়, তবে পছন্দটি এলোমেলোভাবে করা যেতে পারে। তথ্যসূত্র সীমাবদ্ধ প্রোগ্রামিং অনুসন্ধান অ্যালগরিদম