برنامه‌ها انواع و اقسام مختلف
دارند. بسياري از آن‌ها برنامه‌هاي ديتابيسي هستند که داده‌هاي مشخصي را
ذخيره و بازيابي مي‌کنند که از ميان اين‌ها مي‌توان به نرم‌افزارهاي
حسابداري که معروف‌ترين نرم‌افزارها در ايران به‌شمار مي‌آيد اشاره کرد.
برخي از آن‌ها روي انواع فايل‌ها کار مي‌کنند و مبدل هستند و برخي ديگر،
نرم‌افزارهاي تصميم‌گيرنده و مديريتي هستند. استفاده از الگوريتم براي حل
مشکلات طبيعي، يکي از جالب‌ترين چالش‌هايي است که ذهن يک برنامه‌نويس را
به‌خود مشغول مي‌سازد. مساله زير را در نظر بگيريد:
در يک شهر تعدادي
ايستگاه آتش‌نشاني وجود دارد که در سطح شهر پراکنده هستند. ساكنين از فاصله
بسيار زياد بين خانه‌هاي مشخص و نزديكترين ايستگاه شكايت دارند. بنابراين
ايستگاه جديد ساخته مي‌شود. شما بايد محل ايستگاه جديد را طوري مشخص كنيد
که به خانه‌هايي که دورترين هستند، نزديک‌تر باشد. اين شهر حدود 500تقاطع
دارد كه به وسيله جاده‌هايي با طول‌هاي مختلف به هم وصل شده‌اند.
حداكثر 20 قسمت از جاده
را در يك تقاطع معين تقسيم مي‌كند. محل قرار گرفتن خانه‌ها و ايستگاه‌هاي
آتش نشاني شبيه مورد توجه هستند كه در تقاطع‌ها (چهارراه ها) واقع شده
باشند.
به علاوه ما اين را
برعهده مي گيريم كه حداقل يك خانه است كه از هر تقاطع استفاده مي‌كند. ممكن
است بيش از يك ايستگاه آتش نشاني در هر تقاطع وجود داشته باشد.
به‌اين ترتيب بايد روشي
ارائه دهيم که ايستگاه آتش‌نشاني در محلي قرار بگيرد که دسترسي به آن براي
همه آسان باشد، داده‌هاي ورودي مساله ما از فرمت زير پيروي مي‌کنند:
1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10
خط اول نشان‌دهنده اين
است که ما ? تقاطع داريم و يک ايستگاه آتش‌نشاني که در خانه شماره ? قرار
دارد، و خطوط بعدي تقاطع‌ها را مشخص مي‌کند، خب چگونه محل مناسب ايستگاه
آتش‌نشاني را پيدا کنيم؟
راه‌حل
بياييد فرض کنيم که
ايستگاه جديد در تقاطع اول قرار مي‌گيرد، حال بيايد ببينيم فاصله خانه‌هاي
خيابان‌ها در وضعيت فعلي چطور خواهد بود؟ (البته به اين نکته بايد توجه
داشته‌باشيم که تقاطعي که در آن ايستگاه آتش‌نشاني وجود دارد محاسبه
نمي‌شود.) در اين حالت، تقاطع ششم با فاصله 10 کيلومتري، تقاطع پنجم با
فاصله 20 کيلومتري، تقاطع چهارم با فاصله 20 کيلومتري از ايستگاه دوم، و
تقاطع سوم با فاصله 10کيلومتري از ايستگاه دوم قرار مي‌گيرد.
در‌واقع مجموع فواصلي که
اين ايستگاه‌هاي آتش‌نشاني پوشش مي‌دهند به عدد ?? خواهيم رسيد. کافي است
براي بار بعدي، ايستگاه فرضي را در تقاطع سوم بگذاريم و اعداد را محاسبه
کنيم. اين بار نيز مجموع فواصل عدد ?? خواهد بود. براي ديگر تقاطع‌ها
مقادير زير به‌دست مي‌آيد:
تقاطع چهارم:
50
تقاطع پنجم:
40
تقاطع ششم:
60
کوچکترين مجموع عدد براي
هر تقاطع نشان دهنده مکان دقيق قرار گرفتن ايستگاه آتش نشاني است.
به‌عبارت ديگر در حل اين
مساله، همواره با گرافي مشابه با شکل زير سر و کار داريم (اين گراف با
توجه به فرضيات مساله قبلي طراحي شده است.) که در آن رئوس گراف نمايانگر
تقاطع‌ها و يال‌ها نمايانگر طول خيابان‌ها هستند.
وزن هر يال نيز،
نمايانگر فاصله‌اي است که شهروندان تا سر تقاطع (محل قرارگيري ايستگاه
آتش‌نشاني) دارند.
از آنجايي که در ورودي،
سه عدد تقاطع مبدا، تقاطع مقصد و طول تقاطع را مي‌گيريم و قبل‌تر از آن،
شماره تقاطع‌هايي که در آن ايستگاه‌هاي آتش‌نشاني وجود دارند را دريافت
کرده‌ايم، مي‌توانيم با الگوريتمي مشابه الگوريتم زير، به يافتن نتيجه
بپردازيم.
int fire_stations[n];
int num_fire_stations;
get_num_fire_stations();
foreach (
num_fire_stations) {
fire_station[n+1] =
get_fire_stations();
}
for (i = 0; i «
num_stations; i++) {
current_station = 0;
if (current_station !=
fire_station[i]) {
mark_fire_station();
results[i] =
count_distances();
}}
min_result = 9999999;
for (i = 0 ; I «
num_stations; i++) {
min_result = (min_result «
results[i]) ? min_result: results[i];
}
اميربهاءالدين
سبط‌الشيخ
