لم أستطع كتابة كودها بالسي! لا أدري إن كانت تتحقق برمجيا!

[A.S Hack 185]

السلام عليكم أيها الأخوة، وطيب الله أوقاتكم

لدي مشكلة في برمجة التالي بالسي::

افرض أن لدي خمسة أجهزة (من 0 -4) كل واحد منها يستطيع التواصل لاسلكيا في نطاق محدود يمثله الدائرة الكبيرة الحاوية للدوائر الصغيرة(اﻷجهزة)، ألاحظ من الشكل أن الجهاز رقم 0 يستطيع الوصول للجهاز رقم 2 بقفزة واحدة فقط، كذلك الجهاز رقم 2 يستطيع الوصول للجهاز رقم 3 بقفزة واحدة فقط، بينما الجهاز رقم 1 ورقم 4 لا يستطيعان الاتصال بأي جهاز، قمت بكتابة كود بلغة السي، يكون مصفوفة ثنائية البعد، فكانت على هذا الشكل:

اﻷرقام تمثل عدد القفزات المطلوبة للوصول للجهاز اﻵخر، والرقم -1 يشير لقفزة الجهاز إلى نفسه (غير عملي لذلك جعلته بقيمة سالبة).

المشكلة::

ألاحظ من الرسم (ويمكن استنتاج ذلك من المصفوفة اﻷولى) أن الجهاز (n0) يستطيع الوصول للجهاز (n3) ولكن بقفزتين، لهذا يجب أن تكون المصفوفة بهذا الشكل::

فكيف أستطيع كتابة كود يقرأ المصفوفة القديمة ويكتشف عدد القفزات اﻷكثر من قفزة واحدة (قد تكون قفزتين أو أكثر)، ويغير في المصفوفة.

بمعنى آخر الكود الذي كتبته يستطيع فقط مليء المصفوفة بعدد قفزة واحدة وإلا بعدم إمكانية القفز (الوصول) --> مع أن اﻷمكانية واردة بأكثر من قفزة، ويمكن استنتاج ذلك من المصفوفة اﻷولى! ولكن كيف!!

ملاحظة أرجو أن يكون الكود عاما، ﻷن مواقع الأجهزة تختلف دوريا أي أن المصفوفة ومواقع اﻷجهزة هنا كان للمثال فقط، فقد تتحرك اﻷجهزة. (اﻷجهزة تعبر عن شبكة AD Hoc).

تم تعديل 28 Jul 2010 بواسطه A.S Hack

[Speed_Of_Light 141]

أرى أنه من الخطأ تمثيل هذا بمصفوفة، بل الأصح تمثيلها بشجرة

حيث يتم البحث بالشجرة بالطرق المعروفة (بالعمق أولاً أو بالعرض أولاً) ثم يتم إيجاد العقدة (الجهاز) المطلوب ...

[namespace 39]

أرى أنه من الخطأ تمثيل هذا بمصفوفة، بل الأصح تمثيلها بشجرة

حيث يتم البحث بالشجرة بالطرق المعروفة (بالعمق أولاً أو بالعرض أولاً) ثم يتم إيجاد العقدة (الجهاز) المطلوب ...

كلام سليم

كما ستحتاج Recursion ( الاستدعاء الذاتي ) على الأكيد سواء استخدمت الشجرة أو المصفوفة

[Khaled Alshaya 826]

و عليكم السلام أخي العزيز,

سؤالان قبل أن نحاول الإجابة على سؤالك بإذن الله,

ماهو نظام التشغيل الذي تعمل عليه الأجهزة؟ لأن فعل شيء كهذا ممكن بسهولة أكثر بكثير باستخدام الـ Network Stack المتوفرة في أنظمة التشغيل. و بناء Graph, و كتابة Routing Protocol من الصفر أصعب بكثير من استخدام الـ IP protocol.

ماذا تريد من فعل شيء كهذا؟ للاستفادة فقط من تجربتك :)

تحياتي....

تم تعديل 29 Jul 2010 بواسطه Khaled.Alshaya

[A.S Hack 185]

حيّاكم الله أخواني وأهلا بنقاشكم...

بداية هل الخط الذي أكتب به واضح لكم أم لا! ﻷن خطوطكم غير واضحة وصغيرة بالنسبة لي .. ربما ﻷني في Ubunto

بالعموم...

أخي العزيز Khaled.Alshaya لا تحملني ما لا طاقة لي به :happy: أنا فقط أقوم بعمل training خارج بلدي، والعمل الموكل لي من قبل المرشد هو محاكاة شبكة AD Hoc لتجريب خوارزمية جديدة من رأس مرشدي اﻷكادمي وإن أدت لنتاءج طيبة يمكننا نشرها....

المرشد كتب كود بإستخدام لغة السكربت TCL، يقوم كوده باﻵتي:

يكوّن 20 عقدة (nodes) بمواقع مختلفة في كل مرة، بحيث تتم كتابة الاحداثيات x و y لكل عقدة في ملف نصي، ... وكل ما علي القيام به هو أن أكتب كود بلغة السي يقرأ هذا الملف ويحدد عدد القفزات الممكنة للعقدة للوصول لكل العقد الأخرى ويجب أن أضع النتاءج في مصفوفة ثناءية مثل ما كان موضح في الصورة.... اﻵن أنا كتبت كود يستطيع انتاج المصفوفة اﻵولى وتحديد العقد المتجاورة عن طريق قفزة واحدة ولكن لم أجد سبيلا لكيفية كتابة كود يستطيع الكشف عن امكانية الوصول لعقدة معينة بأكثر من قفزة!! ملحوضة افترضت مدى معين للمسافة التي يصل لها مدى العقدة الواحدة (transmission range) هو ما تمثله الداءرة الكبيرة ، والملحوضة الثانية يجب أن تكون النتاءج مخزنة على شكل مصفوفة ثناءية البعد !!! أتمنى أن أوصلت الفكرة بشكل مناسب!!,

وجوابا على سؤالك بوجه أدق... كل ما أقوم به هو فقط للمحاكاة، فليس هنالك عقد حقيقية بها نضام تشغيل بل تنتج تلقاءيا باستخدام NS2 وهو برنامج محاكاة للشبكات.

أخي Speed_Of_Light

هل يمكن أن أتعامل مع tree بواسطة المصفوفة مثلا!!!

وأخي namespace

إن عملت recursive فما هو شرط ايقافه!! مثلا ...

بارك الله فيكم جميعا، وأنتضر طلّة متفاءلة أخرى منكم أحباءي ...

تم تعديل 29 Jul 2010 بواسطه A.S Hack

[A.S Hack 185]

هذا هو الكود اللذي كتبته

#include <math.h>

#include <string.h>

float dist( float x1 , float y1 ,float x2 , float y2){
float term1 = (x2-x1)*(x2-x1);
float term2 = (y2-y1)*(y2-y1);
double term3 =term1+term2;
double dist=sqrt(term3);
return dist;
}


int main(){

char s[1000000];
float x[2000];
float y[2000];
FILE *fp;
FILE *fw;
FILE *num;
int count=1 , c2=1 ,j=0;
fp = fopen("post" , "rt");
fw = fopen("num" , "wt");
int nn=0;
while (fscanf(fp ,"%s" ,s) !=EOF){

fscanf(fp ,"%s" ,s);
if(count%2==0){
printf("%s \n",s) ;
fprintf( fw, "%s\n", s );
nn++;

}
count++;
}

fclose(fp);
fclose(fw);
nn=nn/2;
printf("Number of nodes is %i \n",nn) ;


num = fopen("num" , "rt");
int check=0;
float dbl[2000];
while (check!=EOF){
check = fscanf(fp ,"%f" ,dbl);

if(c2%2!=0){
x[j]=*dbl;
c2++;
}
else {
y[j]=*dbl;
j++;
c2--;
}
}

// check some values
printf("node(0)_X is %f \n",x[0]) ;
printf("node(0)_Y is %f \n",y[0]) ;
printf("node(1)_X is %f \n",x[1]) ;
printf("node(1)_Y is %f \n",y[1]) ;
printf("node(2)_X is %f \n",x[2]) ;
printf("node(2)_Y is %f \n",y[2]) ;
printf("node(3)_X is %f \n",x[3]) ;
printf("node(3)_Y is %f \n",y[3]) ;

int q= 0 , r= 0;
double res;
float MX[4][4];

for(q ; q<4 ; q++){//First loop

for(r=(q);r<4;r++){//S loop
res=dist(x[q],y[q],x[r],y[r]);
MX[q][r]=res;
MX[r][q]=res;
printf("the distance between n%i and n%i is %f \n",q,r,res);

}//S loop

}//First loop

q=0, r=0;
float MTX[4][4];
for(q;q<nn;q++){
for(r=0;r<nn;r++){
if(q==r)
MTX[q][r]=-1;
else if(MX[q][r]<=250){
MTX[q][r]=1;
MTX[r][q]=1;}
else {
MTX[q][r]=0;
MTX[r][q]=0;
}
}
}



/*
q=0;
r=0;
int scan=0;
//multiple hopes!!


for(q;q<nn;q++){
for(r=0;r<nn;r++){
if(MTX[q][r]==0){
//*******scan******
for(scan; scan<nn; scan++){
if(MTX[scan][r]==1)


}
//*******scan******

}



}}

//multiple hopes!!

*/


q=0;
r=0;
printf("\n\n");
for(q=0 ; q<nn ; q++){
for(r=0; r<nn ; r++){
printf("%f\t",MTX[q][r]);
if(r==(nn-1))
printf("\n\n");
}

}



return 0;
}

#include <stdio.h>

وهذه محتوات الملف الذي اقرأه (للتجربة)

اسم الملف post

$node_(0) set Y_ 630.709548275553
$node_(1) set X_ 335.378426731267
$node_(1) set Y_ 705.218369898051
$node_(2) set X_ 605.143502138810
$node_(2) set Y_ 646.840983803160
$node_(3) set X_ 456.415353531334
$node_(3) set Y_ 972.847205988397

$node_(0) set X_ 834.749253811374

لا أضن إن كانت هذه المواقع - مع مدى وصول الارسال الذي افترضته في الكود - لا أضن أن هناك أكثر من قفزة بين العقد، لكن يمكن تغير الارقام أو\و تغير طول مدى الارسال من هنا بالضبط

else if(MX[q][r]<=250)

مدى الارسال اللذي افترضته هو 250 ... يمكن تغييره للتجربة أو يمكن تغير مواقع العقد في ملف post مثلا!

تم تعديل 29 Jul 2010 بواسطه A.S Hack

[Khaled Alshaya 826]

أخي العزيز,

فهمت المطلوب :)

الطريقة التي تخطر ببالي, هي أن تقوم بتمثيل الشبكة التي لديك على شكل Graph. و من ثم تقوم بتطبيق خوازمية Dijkstra Shortest Path لكل Node, بحيث يصبح لديك في النهاية أقصر طريق إلى كل Node أخرى من الـ Node التي بدأت بها. بهذه الطريقة تحصل على أقصر مسار, إضافة إلى المسار نفسه. تحتاج إلى تطبيق الخوازمية لكل Node على حدة. و عندما يتغير الـ Configuration الخاص بالشبكة, بإضافة Node أو حذفها تقوم بإعادة حساب الطرق مرة أخرى. هذا ما يخطر ببالي حالياً. أنا قمت بكتابة خوازمية Dijkstra و لكني لا أجد الكود الذي كتبته حالياً, و هو ليس صعباً بالمناسبة, يمكنك الذهاب إلى Wikipedia و ستجد شرحاً جيداً هناك أو من أي كتاب خوارزميات. أعتقد أن الخوارزمية ستكون بطيئة نسبياً, إذا كان عدد الـ Node كبيراً جداً, و الحل باعتقادي أن تقوم بتقسيم الـ Nodes إلى مجموعات في كل مجموعة Node رئيسية تمثل نقطة التقاء الـ Node الموجودة في منطقتها, و بالتالي تقوم بتنفيذ الخوارزمية على الـ Regions بدلاً من كل Node.

تحياتي...

[A.S Hack 185]

بورك مسعاك أخي Khaled.Alshaya

سأحاول تطبيق الخوارزميةـ وسأعلمك بالنتاءج... لكن إن وجدت ما قد كتبته عن الخزارزمية فلا تبخل علي.

[romansy 368]

سؤال جميل..

أظن أن عليك اكتشاف هل هناك مسار (بالأصح تقاطع في هذه المسئلة Intersection) بين أي عقدة مثلا A والعقدة الأخرى B.

لمعرفة هل هناك تقاطع بين الدائرتين ، قم يجاد المسافة بين مركز النقطه A والنقطه B (باستخدام Euclidean distance) .. واذا كانت هذه القيمة أكبر من الRaduis (هنا تمثله بRate) لA + B فهذا يعني انه لا يوجد تقاطع..

أيضا قم بمحاولة تمثيل ما تريد محاكاته Modeling،، قم بكتابة Point class يمثل النقطتين.. أكتب كلاس يمثل الrouter (يتكون من النقطه والRate) .. قم بكتابة دالة تستقبل two router وارجع bool تدل على ان هناك تقاطع أم لأ. هكذا ستسهل حل المشكلة بكثير.. اذا لم تستطيع استخدام سي++ فاستبدل الclass ب struct.

بالتوفيق..

تم تعديل 29 Jul 2010 بواسطه Wajdy Essam

[Khaled Alshaya 826]

أعتقد أن لدي فكرة أخرى و هي عن طريق الحصول على الـ Transitive Closure للـ Adjacency Matrix و خلال حسابها سنستطيع الحصول على مسافات الطرق بداية من العقد المتصلة مباشرة, ثم العقد المتصلة بطريق مسافته 2, ثم ثلاثة, و هكذا. و سوف يكون لدينا Distance Matrix بحيث نحصل على الـ Minimum لكل distance بين كل node و الأخرى, و عند حساب قوى الـ Adjacency Matrix فإننا سنعلم المسافة التي تتصل بها كل Node مع الأخرى, و بالتالي نقارن المسافة التي استخلصناها من الـ Adjacency Matrix مع المسافة الموجودة في الـ Distance Matrix. لم أتأكد من الفكرة صراحة و لكن أحببت وضعها لمن يحب مناقشتها أو لديه معلومات أكثر. و أتمنى أن لا أكون قد بدأت التخريف في فكرة لا أصل لها :)

تحياتي...

تم تعديل 29 Jul 2010 بواسطه Khaled.Alshaya

[A.S Hack 185]

شكرا لك أخي خالد لقد أفدتني كثيرا ... طبقت خوارزمية Dijkstra ونجحت بحمد الله... سأضع الكود كاملا لاحقا

اﻷخ وجدي عصام شكرا لك... ما وضحته أخي هو في الحقيقة ما نفذته في الكود السابق ... بارك الله فيك (أو فلنقل بعضا منه)...

سأعود قريبا ﻷضع الكود بإذن الله