في نظرية المخططات و نظرية المشاكل المعقدة, تُعرف مشكلة التاجر الرحالة كما يلي:
يريد تاجر أن يقوم بجولة كاملة يزور خلالها مدنا حيث يمر بكل المدن مرة
واحدة و وحيدة ثم يعود إلى مدينة الانطلاق. المشكلة هي: ما هو أقصر
طريق؟؟

حول المشكلة

رغم أن صيغة المشكلة تبدو بسيطة, إلا أن الحل صعب جدا, فكلما زاد عدد
المدن زادت صعوبة المشكل: يحتاج الحاسوب إلى حوالي قرنين من الزمن لإيجاد
أقصر مسار يمر على 100 مدينة والعهدة على ذمة الراوي

(( هذا ما قرأته في الموقع العربي لويكيديا)) وعندما قررت التحول إلى النسخة الموقع الانجليزي وجدت الحالة التالية

تم تطبيق نفس المعضلة الرياضية على 15,112 بلدة في ألمانيا وقد تم عمل
الحسابات من خلال شبكة تحتوي على 110 معالج (processors ) سرعة المعالج 500 MHz موزعة بين جامعتي برنستون المشهورة وجامعة رايس ،،، الوقت الذي استغرقته عملية الحسابات هو 22.6 سنة

في السويد تم تطبيق نفس المعضلة وفي نهاية وصلوا إلى نتيجة في منتهى
الغرابة والطرافة ملخصها هو :
it was proven that no shorter tour exists

وأيضا تم الوصول إلى نفس النتيجة بعد تطبيق البرنامج على 33,810 نقطة
ولمدة 15 سنة من العمل على اجهزة الحاسوب
no shorter tour exists

رأيي الشخصي

في مباحث الرياضيات هناك مبحث يسمى بالتوافيق والتباديل على ما أذكر التباديل والتوافيق أسماء يعبر بها علماء الرياضيات عن مجموعات معينة من الأشياء أو الرموز. والتباديل ترتيبات منظمة لمجموعة من الأشياء

التباديل والتوافيق أسماء يعبر بها علماء الرياضيات عن مجموعات معينة من الأشياء أو الرموز. والتباديل ترتيبات منظمة لمجموعة من الأشياء، فمثلاً تعد (أ ب جـ) و(أ جـ ب) و(ب أ جـ)، ثلاثة تباديل لمجموعة الرموز أ، ب، جـ وأعتقد أن الحالات المدروسة أعلاه تنتج أعداد مهولة من التوافيق والتباديل بحيث يقضي الحاسوب كل هذا الوقت في استخراج الحل

لكن مع ذلك لا زلت غير مقتنع أن الكومبيوتر بعظمته الحسابية يستغرق كل هذا الوقت لحل هذه المعضلة التي تبدولي أنها بسيطة قياسا على قدراته

المسألة ليست بالسهولة التي قد تتصورها ....

15112 بلدة ...

اكيد انك تعرف ال ( Factorial ) في الرياضيات ... و رمزها علامة التعجب ( ! )

5! = 2*3*4*5 = 120

تخيل ال ( Factorial ) لرقم مثل !15112 ؟؟
و هو يمثل عدد احتمالات في هذه الحالة لترتيب البلدات على هذا الطريق ..... جرب أن تحسب هذا الناتج و سيكون عندك عدد خرااااااااااااافي
و هو حسب حساباتي =
2.2068576296794525215309608080978e+56597
و لك أن تعي ضخامة هذا الرقم الفلكي بالنظر لل ( Exponential ) .

هذا و نحن لم ندخل بعد في تفاصيل ال ( Combination s ) و ال ( Permutations ) من هذا النوع ، غير حسابات المسافة المعقدة و المتداخلة بين هذه البلدات و التي ستشكل مصفوفة ( Matrix ) ضخمة جدا و لها حساباتها الضخمة ايضا .....

تحتاج ل Super Computer للتعامل مع هذه المسائل ..... غير هيك اعتقد ان هذه الحسابات التي أوردتها قديمة ... فمعالج 500 MHz مكانه المتاحف بصراحة .... هذه تكنولوجيا معالجات عمرها 10 سنوات .

Arrayالمسألة ليست بالسهولة التي قد تتصورها ....
15112 بلدة ...
اكيد انك تعرف ال ( Factorial ) في الرياضيات ... و رمزها علامة التعجب ( ! )
5! = 2*3*4*5 = 120[/quote]

صحيح تذكرت هذا الـ Factorial ويسمى بالعربي المضروب ،
5! : مضروب الخمسة ، المضروب يستعمل في حساب التوافيق والتباديل الممكنة استنادا إلى عدد عناصر المجموعة ، كنت أستعمله في سنة أولى جامعة في كلية العلوم قبل ما انضرب على قلبي واحول لكلية الاقتصاد والتجارة بضغط من الأهل ، وأضطر الآن إلى تصحيح هذا الخطأ مجددا في حياتي.

Array
تخيل ال ( Factorial ) لرقم مثل !15112 ؟؟
و هو يمثل عدد احتمالات في هذه الحالة لترتيب البلدات على هذا الطريق ..... جرب أن تحسب هذا الناتج و سيكون عندك عدد خرااااااااااااافي
و هو حسب حساباتي =
2.2068576296794525215309608080978e+56597
و لك أن تعي ضخامة هذا الرقم الفلكي بالنظر لل ( Exponential ) .[/quote]

ربما يكون كلامك صحيح ، فنحن لا تعني دلالة الرقم لأنني لا نراه إلى جزء من سطر ، هذه الأرقام كتابتها سهلة جدا فمثلا عدد سكان الأرض 6,000,000,000
ومع ان هذا الرقم استهلك 10 digits لكن دلالته على أرض الواقع أضخم بكثير فكيف برقم مثل الذي وضعته لنا

لكن معلوماتي أنه لا يوجد أي عملية حسابية خصوصا تلك التي تستعمل فيها العمليات الحسابية الأربعة ، تأخذ من الكومبيوتر أكثر من بضع ثوان ، حتى قيمة الرقم أعلاه !15112 والذي أتيتني به على ضخامته وصعوبة حسابه لم يستغرق الحصول عليه أكثر من كبسة زر عندي

Array هذا و نحن لم ندخل بعد في تفاصيل ال ( Combination s ) و ال ( Permutations ) من هذا النوع ، غير حسابات المسافة المعقدة و المتداخلة بين هذه البلدات و التي ستشكل مصفوفة ( Matrix ) ضخمة جدا و لها حساباتها الضخمة ايضا .....[/quote]

وهل استعمال المصفوفات يدخل أيضا هنا ، يبدولي أن كل حقول الرياضيات والحقول المعرفية الأخرى تتداخل مع بعضها البعض في مناطق ما ،،،، أخبرني دكتور في الجامعة أن علماء الرياضيات لا يزالون يبحثون منذ قديم الزمان عن القانون العام الذي بموجبه يتم حل أي معادلة رياضية وأخبرني أيضا أنه ضد فكرة التخصص لأنه والكلام مقتبس عنه / لأن هناك حقول من المعرفة لا تفتح إلا لإنسان يتصادف أنه مطلع ومتخصص بل ومسلح (على حد تعبيره) بأكثر من مبحث من مباحث العلوم الطبيعية الكثيرة والمتشعبة وأخبرني عن اكتشاف مثلا في حقل الالكترونيات نسيته قال أن صاحبه لم يكن ليصل إليه لولا أنه تصادف أنه عالم رياضيات ومطلع على مبحث في علوم المنطق اسمه المنطق الضبابي ومبحث آخر مغرق في التخصص بالكيمياء الفيزيائية أيضا نسيته أيضا.

Arrayتحتاج ل Super Computer للتعامل مع هذه المسائل ..... غير هيك اعتقد ان هذه الحسابات التي أوردتها قديمة ... فمعالج 500 MHz مكانه المتاحف بصراحة .... هذه تكنولوجيا معالجات عمرها 10 سنوات .[/quote]

كل معلوماتي عن الـ Super Computer هو أنها تستخدم في عمل محاكاة تجارب للانفجارات النووية تغني عن التجارب الفعلية ، وأن الصين تستميت من أجل الحصول على هذه التكنولوجيا من الولايات المتحدة دون جدوى

عادي
لما كنت في الثانوي عملنا برنامج بسيط بلغة بيسك لحساب الاعداد الاولية (1، 2، 3، 5، 7، الخ)
فكرة البرنامج بسيطة وهو انه يقوم بعمل قسمه *لكل* الاعداد الصحيحة الاقل من عدد صحيح ما (يقوم بعمليات طرح ومن ثم قسمة لكل الاعداد الصحيحة الاصغر منه حتي يصل لقاسم يكون حاصل القسمة عليه عددا صحيحا عندها ينقل للعدد الذي بعده باضافة 1 او قد لا يصل بمعني ان يصل للصفر وكل الاعداد بين الصفر وذاك العدد تولد نتائج كسرية ، عندها يدون الرقم).
كان المعالج 386 وهو سريع جدا لعمل طرح وقسمة (لعب عيال يعني)
لكن الملاحظ ان الجهاز بعد ان يدون اول 100 رقم يبدأ في التباطئ الملحوظ حتي يصل لدقائق للوصول للرقم الاولي التالي بعد وصولة مرحلة الالاف.
مشكور يا ثندر ععلي الموضوع(f)

هذه قضايا معروفة وقديمة في نظرية التعقيد الحسابي computational complexity ،

ومسألة البائع المسافر Traveling Salesman من أشهر المسائل التي تسمى NP-Hard Problems ..

ما يعنيه هذا .. لنفرض أن هناك مسألة معينة كمسألة البائع فيها عدد n ، المطلوب إيجاد خوارزمية معينة algorithm تقوم بحل المسألة لقيمة معينة n ..
كمية الحسابات التي تحتاجها الخوارزمية تمثل كدالة function بدلالة n . طبعاً المهم هنا كيفية نمو هذه الدالة بزيادة n . هل تزيد بمعدل حدودية in the order of a polynomial أو بمعدل أسي exponential growth .. أو إلخ .

يمكن حل المسألة بسرعة إذا كانت هناك خوارزمية تعقيدها يكون بمعدل حدودية .. وتسمى هذه المسائل P problems ، وعادة يقال أنها مسائل سهلة .

أما إذا لم يمكن إيجاد مثل هذه الخوارزمية بالمعدل المطلوب فإنها تسمى Non-deterministic polynomial .. ويرمز لها NP problems .
ففي حالة مسائل NP فإن عدد الدورات iterations لحل المسألة يزيد بزيادة n بشكل خرافي مما يشكل عبئاً على الكمبيوترات لحلها .

الطريف في الموضوع أنها لحد الآن لم يثبت أحد أنه يستحيل إيجاد خوارزمية حدودية لمسائل NP .. وتبقى مسألة مفتوحة هل NP=P أم لا ؟ مع أن معظم الباحثين يعتقدون بعدم تساويهما .


دعك من كل هذا .. جرب إيجاد معكوس مصفوفة بحجم متزايد .. إبدأ من 5000 وتجد أن الكمبيوتر المسكين يعاني أشد العناء .