پیدا کردن نزدیکترین مسیر در یک ماتریس 2 بعدی

[ahmadsystemco]

سلام خدمت تمامی دوستان عزیز
می خواستم ببینم این مساله را چجوری میشه حل کرد:
یک آرایه 2 بعدی از صفرها و یکها داریم که یک ماتریس یا یک جدول nxn را نشان می دهند. مکان هر (یک) در این ماتریس مختصات یک شیء در دنیای واقعی است (x,y).
نقطه آغازین مساله داده می شود و باید از آن نقطه نزدیکترین مسیری که به تمام یک ها سر بزند را پیدا کنیم.

خروجی الگوریتم فقط باید ترتیب حرکت بین 1 ها را نشان دهد.
مثلا
(5,5)->(3,2)->(4,4)->....->END

لطفا یک نفر کمکم کنه.
من خودم تابعی که تمام مسیر ها برود و کوچکترین را انتخاب بکند را نوشتم ولی وقتی تعداد 1 ها زیاد می شد برنامه کم می آورد. این برنمه را توی سی نوشتم ولی .....
حداکثر اندازه ماتریس 30x30 می باشد.

لطفا راهنمایی کنید.

[MIDOSE]

برنامه ی خود را قرار بدهید تا دوستان بهتر بتونند نظر بدهند.

موفق باشید.

[ahmadsystemco]

چشم
این هم سورس برنامه یکمی مشکل داره :گریه:

[saeedr22]

الگوریتم مسیر maze رو جستجو کنبن.
منظور شما همون الگوریتم maze هستش.

[mortezamsp]

نخیر ! ایشان منظورشان الگوریتم درخت پوشای کمینه یا الگوریتم پرایم و کراسکال و اینها میباشد .

آقا شما باید اول بیاید یه گراف تعریف کنید که رئوس اون رو همون 1 های ماتریس اصلی تشکیل بدن و ، و از هرراسی به همه رئوس دیگر یال داشته باشیم ، و مقدار هر یال هم همون distance بین اون دو راس _ یا بین اون دو 1 در ماتریس اصلی _ باشه . آخرش هم الگوریتم کراسکال یا پرایم رو اجرا کن . بلدی که ؟

الگوریتم پرایم :
http://barnamenevis.org/forum/picture.php?albumid=512&pictureid=1170

بعدشم اون برنامتون خیلی خیلی طول میکشه چون اولا همش فراخوانی بازگشتیه و پیچیدگیشون هم نمایی هست ، بعدشم دارید آرایه way رو هربار بعنوان آرگومان بطور کامل میفرستید ، حداقل اشاره گرش رو هم نمیفرستید .

[ahmadsystemco]

سلام خدمت دوستان
از تمامی شما ممنونم.
دوستان عزیز من بد جوری گیر کردم می شه یه راهنمایی خوب بکنید.
من از هر چیزی که می تونستم استفاده کنم در برنامه استاده کردم و چیز بیشتری نمی تونم استفاده بکنم.

یک مطالبی درباره الگوریتم دایکسترا خوندم ولی نمی دونم چجوری اون را تو c++ اجرا کنم.
کراسکال و پرایم که بماند اصلا نرفتم سراغشون.

لطفا کمک کنید. :قلب:

[mortezamsp]

اینجا سورس سی پلاس این الگوریتم ها رو قرار میدم ، اگه مشکلی داشتی باز بپرس .

[ahmadsystemco]

سلام خدمت دوستان عزیز
من یک برنامه نوشتم و توی اون از الگوریتم پرایم استفاده کردم ولی برنامه کار نمی ده.
تو این برنامه یک تابع برای ساختن ماتریکس همانی گراف نوشتم به نام GenerateAdjacencyMatrix و یک تابع هم به نام prim که الگوریتم را انجام می دهد و مسیر بدست آمده را در یک آرایه به نام path قرار می دهد.
ولی الگوریتم کار نمی ده. فکر کنم توی تبدیل شبه کد الگوریتم به کد سی مشکل دارم. دوستان اگه می شه یک نگاه به این کد بندزید و اگه میشه اونو تصحیح کنید. اگر هم شد لطفا کد الگوریتم دایجکسترا و یا کراسکال را برای این برنامه بنویسید.


/*
Nearest Path Finder
Programming by Ahmadreza Hadidi
ahmadreza_hadidi2020@yahoo.com
*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>

struct Point
{
int x;
int y;
};

double adjacencyMatrix [900][900];
struct Point path[900]; //An array to hold achived path

int objects_n; //the number of 1(s) in the board
int board[30][30];
int board_size;

struct Point objects[900];

struct Point startPoint;

//Functions
void fillBoard();
void generateAdjacencyMatrix();
void prim();

void main()
{

board_size = 3;
fillBoard();
printf("objects : %d\n" ,objects_n);

for(int i=0;i<board_size;i++)
{
for(int j=0;j<board_size;j++)
{
printf("%d", board[i][j]);
}
printf("\n");
}

//get the position of start point
printf("\nPlease enter the start point position :\n\t\tX: ");
scanf("%d" , &startPoint.x);
printf("\t\tY: ");
scanf("%d" , &startPoint.y);

//Generate the adjacency matrix of our graph
generateAdjacencyMatrix();

prim();

//show the path
for(int i=0;i<objects_n; i++)
{
printf("(%d,%d) -> " ,path[i].x ,path[i].y);
}
printf("End");
getch();
}

void prim()
{
int vnear; //the index of nearest vertext in our graph
double min; //the minimum distance beetween to vertexes
struct Point p; //the poit of the path's next vertext

int nearest[900]; //an array to hold nearest point's indexes
double distances[900]; //an array to hold distances beetween vertexes

int currentPosition = 0; //the index of current path position
int n = objects_n;

for(int i=0; i<objects_n; i++)
{
nearest[i] = 0; //Warning
distances[i] = adjacencyMatrix[0][i];
}

while(n-1>0) //reapeat this (objects_n - 1) times
{
min = 2000;
for(int i=1; i<objects_n; i++) //walk through all the points and find the nearest one
{
if(distances[i]>0 && distances[i] < min)
{
min = distances[i];
vnear = i; //set the index of nearest vertex
}
}

//add current achived point to the path
p.x = objects[nearest[vnear]].x;
p.y = objects[nearest[vnear]].y;
path[currentPosition] = p;
currentPosition++;

distances[vnear] = -1; //delete used point from list by negative it's distance

for(int i=0; i<objects_n; i++)
{
if(adjacencyMatrix[i][vnear]<distances[i])
{
distances[i] = adjacencyMatrix[i][vnear];
nearest[i] = vnear;
}
}

n--;
}
}

void fillBoard()
{
objects_n = 0;

for(int i=0;i<board_size;i++)
{
for(int j=0;j<board_size;j++)
{
if(rand()<RAND_MAX/3)
{
board[i][j] = 1;

struct Point p;
p.x = j;
p.y = i;

//add the position of the object to the list of objects
objects[objects_n] = p;
//add to objects count;
objects_n++;
}
else
board[i][j] = 0;
}
}
}

void generateAdjacencyMatrix()
{
int n=0;
struct Point objectsList[900];

//Add the first point of the path
objectsList[0] = startPoint;

if(board[startPoint.y][startPoint.x] == 0)
{
//we imagine that this 0 point is also a 1 point
for(int i=0;i<objects_n;i++)
objectsList[i+1] = objects[i];

objects_n++;
}
else
{
for(int i=0; i<objects_n; i++)
{
if(objects[i].x != startPoint.x && objects[i].y != startPoint.y)
{
objectsList[n+1] = objects[i];
n++;
}
}
}


for(int i=0; i<objects_n; i++)
{
for(int j=0; j<objects_n; j++)
{
//set the distance of each point to other to thr adjacency matrix
adjacencyMatrix[i][j] = sqrt( pow(objectsList[i].x-objectsList[j].x,2) + pow(objectsList[i].y-objectsList[j].y,2) );
}
}

//copy new generated list to the objects
for(int i=0; i<objects_n; i++)
{
objects[i] = objectsList[i];
}
}
واقعا به کمکتون نیاز دارم.
با تشکر

[ahmadsystemco]

سلام دوستان
لطفا کمک کنید بدجوری گیر کردم
اصلا بگید برای اینکه نزدیک ترین مسیر برای طی کردن تمام راسهای یک گراف وزندار را پیدا کنم از چه الگوریتمی استفاده کنم.
آیا الگوریتم پرایم این کار را می کند.
لطفا اگر می شود کد الگوریتم پرایم را در زبان سی و یا سی پلاس پلاس برایم قرار دهید چون توی تبدیل شبه کد آن مشکل دارم.

با تشکر AHS

[qwerty11]

سلام دوستان
لطفا کمک کنید بدجوری گیر کردم
اصلا بگید برای اینکه نزدیک ترین مسیر برای طی کردن تمام راسهای یک گراف وزندار را پیدا کنم از چه الگوریتمی استفاده کنم.
آیا الگوریتم پرایم این کار را می کند.
لطفا اگر می شود کد الگوریتم پرایم را در زبان سی و یا سی پلاس پلاس برایم قرار دهید چون توی تبدیل شبه کد آن مشکل دارم.

با تشکر AHS
راستش اون جمله ایت که بولدش کردم اشتباهه ! احتمالاً باید منظورت کوتاهترین باشه نه نزدیکترین ! چون نزدیکترین که تو این جمله معنی خاصی نمیده.

همونطور که خودتون گفتید میتونین از پریم هم استفاده کنین. از کروسکال هم البته میشه استفاده کرد.

راستش من قبلاً پریم رو با صف اولویت و به زبان جاوا پیاده سازی کردم که خوب نمیتونه برای شما چندان مفید باشه ! اما چرا یه جستجوی ساده تو نت انجام نمیدی !؟

[ahmadsystemco]

سلام خدمت شما دوستان
من بعد از یک عالمه گشت و گذار در نت و پیگیری به این نتایج رسیدم.
1) الگوریتم پرایم درخت پوشای کمینه را می دهد ولی مشکل آن اینست که نمی توان نقطه ای آغازی برای مسیر در نظر گرفت
2) الگوریتم دایجکسترا نزدیک ترین مسیر را می دهد و ممکن است از تمامه رئوس گذر نکند.

لطفا راهنمایی کنید که چه الگوریتمی به کار ببرم که از تمام رئوس بگذرد و دارای نقطه ابتدا باشد.

[qwerty11]

دوست عزیز متوجه نمیشم !؟ :گیج::گیج:


) الگوریتم پرایم درخت پوشای کمینه را می دهد ولی مشکل آن اینست که نمی توان نقطه ای آغازی برای مسیر در نظر گرفت اتفاقاً در الگوریتم پریم هر نقطه ای را میتوان به عنوان نقطه ی آغازی در نظر گرفت !

الگوریتم دایجکسترا نزدیک ترین مسیر را می دهد و ممکن است از تمامه رئوس گذر نکند.بله. الگوریتم دایکسترا برای این مسئله ای که شما میگین هیچ کاربردی نداره.

لطفا راهنمایی کنید که چه الگوریتمی به کار ببرم که از تمام رئوس بگذرد و دارای نقطه ابتدا باشد. الگوریتم پریم !

این جمله ی انگلیسی رو از صفحه ی ویکیپدیا ی مربوط به الگوریتم پریم انتخاب کردم. خوب بهش نگاه کن ! :

Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from Varbitary یعنی دلخواه تا اونجایی که من میدونم !

[ahmadsystemco]

دوست عزیز متوجه نمیشم !؟ :گیج::گیج:

اتفاقاً در الگوریتم پریم هر نقطه ای را میتوان به عنوان نقطه ی آغازی در نظر گرفت !
بله. الگوریتم دایکسترا برای این مسئله ای که شما میگین هیچ کاربردی نداره.
الگوریتم پریم !

این جمله ی انگلیسی رو از صفحه ی ویکیپدیا ی مربوط به الگوریتم پریم انتخاب کردم. خوب بهش نگاه کن ! :
arbitary یعنی دلخواه تا اونجایی که من میدونم !

سلام دوست عزیز
مثل اینه که شما درست به مقاله دقت نکردید:
در سایت ویکیپدیا در این آدرس (http://en.wikipedia.org/wiki/Prim%27s_algorithm) توضیحات الگوریتم پرام هست و اگر شما کمی به آن دقت کنید و عکسهایی که از نحوه ی کار آن الگوریتم نوشته را ببینید متوجه می شوید که اگر چه نقطه آغازی داریم و لی در حین عملیات ممکن است نقطه ای دیگر از طرف دیگر نیز به نقطه آغازی متصل شده و دیگر نقطه مورد نظر نقطه آغازی نباشد.
مثلا در شکل زیر الگوریتم را با نقطه D آغاز کرده ایم:
http://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Prim_Algorithm_1.svg/200px-Prim_Algorithm_1.svg.png (http://en.wikipedia.org/wiki/File:Prim_Algorithm_1.svg)

ولی در مرحله سوم به این حالت رسیده ایم:
http://upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Prim_Algorithm_3.svg/200px-Prim_Algorithm_3.svg.png (http://en.wikipedia.org/wiki/File:Prim_Algorithm_3.svg)

و در مرحله آخر این درخت به دست آمده:
http://upload.wikimedia.org/wikipedia/commons/thumb/b/b9/Prim_Algorithm_7.svg/200px-Prim_Algorithm_7.svg.png (http://en.wikipedia.org/wiki/File:Prim_Algorithm_7.svg)

( در این اشکال مسیر سبز رنگ یال های پیدا شده توسط الگوریتم پرایم است )


خوب حالا چی؟

اینم یک نمونه توی C# ببینید :
http://www.codeproject.com/KB/cs/shorest_rout.aspx

لطفا کمک...........

[qwerty11]

لطفا کمک........... خیلی ببخشید، ولی به نظر من شما به کمک نیاز نداری. شما به چندتا چیز زیر نیاز داری :

1- بری و متن دقیق سوالی که استادتون گفته رو کپی کنی اینجا. (حتی یه نقطه هم جا ننداز)
2- بری ببینی درخت پوشای کمینه یعنی چی ؟
3- الگوریتم پریم چطوری کار میکنه !؟

مورد اول رو خودت باید انجام بدی! ولی اگه 2 تا مورد دیگه رو خوندی و نفهمیدی اونوقت میتونی رو کمک من حساب کنی.

[ahmadsystemco]

خیلی ببخشید، ولی به نظر من شما به کمک نیاز نداری. شما به چندتا چیز زیر نیاز داری :

1- بری و متن دقیق سوالی که استادتون گفته رو کپی کنی اینجا. (حتی یه نقطه هم جا ننداز)
2- بری ببینی درخت پوشای کمینه یعنی چی ؟
3- الگوریتم پریم چطوری کار میکنه !؟

مورد اول رو خودت باید انجام بدی! ولی اگه 2 تا مورد دیگه رو خوندی و نفهمیدی اونوقت میتونی رو کمک من حساب کنی.

دوست عزيز شايد من اشتباه كرده باشم ولي وقتي كه شكل سايت ويكي پديا و برنامه اي كه گذاشتم را ديدم متوجه اين موضوع شدم كه شايد الگوريتم پرايم نقطه آغازي ندارد.
شايد من اشتباه فهميده باشم و مي خواهم بدونم چه الگوريتمي به من كمك مي كنه.

منظور من از نقطه آغازي راسي در گراف است كه ابتداي درخت ما باشد و فقط يك يال به آن متصل شود و همچنين درخت ما نبايد شاخه دار باشد و فقط دنباله اي از رئوس كه همه آنها به جز راس ابتدا و راس انتها بايد دويال داشته باشند.

لطفا من كه هيچ چيز از اينها نمي دونم را راهنمايي كنيد.

[ahmadsystemco]

دوست عزيز يك چيزه ديگه
اين متن هم مرا به اشتباه انداخت:
منبع ويكيپدياي فارسي (http://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D9%BE%D9%88%D8%B4%D8%A7% DB%8C_%D8%A8%D9%87%DB%8C%D9%86%D9%87)

الگوريتم prim
در این روش از یک رأس شروع می کنیم و کمترین یال(یال با کمترین وز ن ) که از آن می گذرد را انتخاب می کنیم . در مرحله بعد یالی انتخاب می‌شود که کمترین وزن را در بین یالهایی که از دو گره موجود می گذرد داشته باشیم . به همین ترتیب در م رحله بعد یالی انتخاب می‌گردد که کمترین وزن را در بین یالهایی که از سه گره موجود می گذرد داشته باشد ......... .

دوست عزيز ببين در اين متن گفته كه در مرحله بعد يالي انتخاب مي شود كه كمترين وزن را بين يالهايي كه از دوگره موجود مي گذرد داشته باشد. پس مي تواند يالي انتخاب شود كه از گره ابتدايي يا همان نقطه شروع بگذرد و ديگر اين گره گره‌ي ابتدايي نيست يعني در وسط درخت قرار گرفته و مساله اينگونه حل نمي شود.

با تشكر

[qwerty11]

دوست عزیز اگه ممکنه بیا یه بار تعریف "درخت پوشای کمینه" رو مرور کنیم :

اول تعریف درخت : درخت یه گرافه که بین هر دو تا راسش دقیقاً یه مسیر وجود داره. به عبارت دیگر هر گراف همبندی که دور نداره یه درخته.

درخت پوشا : درختی که از تمام رئوس گراف بگذرد.

درخت پوشای کمینه : به هر یال در گراف یک وزن نسبت داده شده است. درخت پوشایی در گراف پیدا کنید که مجموع یال های آن کمترین باشد. به درخت فوق درخت پوشای کمینه می گویند.

منظور من از نقطه آغازی راسی در گراف است که ابتدای درخت ما باشد و فقط یک یال به آن متصل شود و همچنین درخت ما نباید شاخه دار باشد و فقط دنباله ای از رئوس که همه آنها به جز راس ابتدا و راس انتها باید دویال داشته باشند.منظورتون از راس ابتدا و انتها چیه آخه !؟ این درختی که شما ازش صحبت میکنین اصلاً ممکنه وجود نداشته باشه ! میشه تو عکس زیر درختی رو که مد نظرتونه مشخص کنین !؟
http://www.img98.com/images/fdjbvlwfdp0fzl6b3yjq.jpg

متوجه شدین!؟ یال درخت پوشای کمینه لزومی نداره که همیشه به راسی که به عنوان راس آغازین انتخاب میکنیم وصل باشه... دقت کن : هیچ لزومی نداره.

اگه تا اینجاشو فهمیدی بگو تا پریم رو هم به زبون خودم بگم...

[ahmadsystemco]

سلام

ببین رفیق مساله را این جوری فرض کن.
4 شیء در مختصات x1,y1 و x2,y2 و x3,y3 و x4,y4 داریم
حال از روی این سه شیء یک گراف وزن دار می سازیم که وزن هر یال آن فاصله ی بین دو شیء است. پس یک گراف کامل داریم که بین تمام رئوس آن یال وجود دارد و می خواهیم مسیری ( یا به عبارتی یال هایی) را انتخاب کنیم که از یک راس شروع شود و به تمام راس های دیگر وصل شود و مجموع وزن یال ها کمینه شود. به این صو رت

http://barnamenevis.org/forum/attachment.php?attachmentid=43147&stc=1&d=1264356160
خوب من برای اینکه این مساله را حل کنم اینگون در نظر دارم که یک درخت می سازیم که راس ابتدای آن راسی است که نقطه آغازی است پس سه راس دیگر می ماند و به این راس متصل اند و شاخه های زیرین درخت می شوند اگر هر کدام را انتخاب کنیم دو راس دیگر با قی می مانند که این ها را نیز شاخه هایی دیگر در نظر می گیریم و الی آخر. یک درخت بدست می آید که 16 راس دارد حال یک مسیری را در آن انتخاب می کنیم که تا آخر یک شاخه برود و به آخرین راس از 4 راسمان برسد و مجموع وزن یال ها مینیموم شود.
بهتر است شکر زیر را ببینید.
http://barnamenevis.org/forum/attachment.php?attachmentid=43148&stc=1&d=1264356160

فرض می کنیم مسیر قرمز مسیری است که ما می خواهیم.

حال یکی به داد من برسه.
می دونم خیلی بد توضیح دادم.
خوب راه حل چیه. می دونم که این یک درخت نیست و برای همین فکر کنم پرایم بدرد نمی خورد و لی من اطلاعات کافی ندارم پس بهتره یک توضیحی درباره پرایم بدهید.

با تشکر

[qwerty11]

می دونم خیلی بد توضیح دادم.
متاسفانه دقیقاً همینطوره :ناراحت: چیزی که من از صحبتهای شما برداشت کردم تقریباً یه راه حل brute force بود! یعنی شما اول میای تمام درخت های ممکن رو تشکیل میدی و از بینشون بهترین رو انتخاب میکنی !؟

ولی من یه بار دیگه ازت خواهش میکنم که متن دقیق سوال رو بزاری اینجا... اون چیزی که من از سوال شما میفهمم دقیقاً درخت پوشای کمینه و الگوریتم پریم هستش. اما نمیدونم شما چرا میگی پریم به درد نمیخوره :متفکر: خوب من پریم رو به زبون خودم توضیح میدم، ایشالا که مشکلت از اشتباه فهمیدن الگوریتم پریم باشه.

تو الگوریتم پریم یه مجموعه داری که مجموعه ی رئوس پیدا شده در درخت بهینه هستن. اسم این مجموعه رو میزاریم G . در ابتدا G خالی هستش. یه راس به دلخواه انتخاب میکنیم و اون رو به G اضافه میکنیم. از این به بعد تمام یال هایی که از رئوس موجود در G عبور میکنند رو در نظر میگیریم. از بین تمام این یالها، یالی رو که کمترین وزن رو داره و میدونیم که اون یکی سرش هم توی G نیست رو انتخاب میکنیم (در واقع اگه اون یکی سرش هم توی G باشه دور تشکیل میده) و اون یال رو به درخت پوشای کمینه و اون یکی راسش رو هم به G اضافه میکنیم. n-1 بار اگه عمل فوق رو انجام بدیم درخت پوشای کمینه برای ما ساخته میشه...

[quantomquery]

سلام

چرا از الگوریتم های کلاسیک استفاده می کنید .

از ژنتیک استفاده کنید . به جواب هم می رسید
یه کرومزوم به تعداد نود ها بگیریدو فیتنس رو هم از ماتریس مجاورت حساب کنید :لبخندساده: