الگوریتم تشخیص برخورد دو مسیر در چهار راه

[morteza_bn]

سلام
می خوام الگوریتمی بنویسم که برخورد دومسیر رو تشخیص بده فرض کنید هر خیابون یک شماره داره که مسیرها بصورت 12 ،14،43،32،... در یک آرایه قرار دارند مثلا 14 یعنی مسیر 1 به 4 .
حالا می خوام یه الگوریتمی بنویسم که وقتی دو مسیر با هم تداخل دارن رو تشخیص بده...
کسی میتونه کمک کنه

[xxxxx_xxxxx]

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

[morteza_bn]

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

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

[xxxxx_xxxxx]

مهم همون تشکیل گراف هست...کسی راه حلی برای تشکیل گراف داره
با استفاده از ماتریس (آرایه دو بعدی) پیاده سازی کنید. هر دو بعد، رأس های گراف هستند. یعنی یک ماتریس n*n خواهیم داشت. پر کردن ماتریس هم با 0 و 1 انجام میشه. مثلاً اگر مسیر 23 داریم، خانه [2,3] ماتریس رو 1 میزاریم.



چجوری میشه چهارراه رو پیاده سازی کرد بصورتی که تشخیص داد دو مسیر با هم تداخل دارن
بعد از پر کردن خانه های ماتریس، به ستون یا سطر یک رأس نگاه میکنیم. مثلاً اگر به ستون رأس 2 نگاه کنیم، هر جا که عدد 1 داشت، تقاطع های مسیر 2 با سایر مسیرهاست.

[morteza_bn]

با استفاده از ماتریس (آرایه دو بعدی) پیاده سازی کنید. هر دو بعد، رأس های گراف هستند. یعنی یک ماتریس n*n خواهیم داشت. پر کردن ماتریس هم با 0 و 1 انجام میشه. مثلاً اگر مسیر 23 داریم، خانه [2,3] ماتریس رو 1 میزاریم.

بعد از پر کردن خانه های ماتریس، به ستون یا سطر یک رأس نگاه میکنیم. مثلاً اگر به ستون رأس 2 نگاه کنیم، هر جا که عدد 1 داشت، تقاطع های مسیر 2 با سایر مسیرهاست.

ممنون از جوابتون...همه اینارو میدونم...
سوال من در مورد خود الگوریتم تشخیص هستش...مشکل من اینه که چجوری بفهمی مسیر 12 با مسیر 14 تداخل داره وبعد درون آرایه 1 قرار بدی... یعنی تشخیص تداخل که بعد از تشخیص، گراف رو تشکیل بدیم...امیدوارم متوجه شده باشید...!

[xxxxx_xxxxx]

سلام،



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



مشکل من اینه که چجوری بفهمی مسیر 12 با مسیر 14 تداخل داره وبعد درون آرایه 1 قرار بدی... یعنی تشخیص تداخل که بعد از تشخیص، گراف رو تشکیل بدیم...امیدوارم متوجه شده باشید...!
اول باید گراف رو تشکیل بدید؛ بعد از روی گراف، تداخل ها رو تشخیص میدید. شما گفتید مسیرها تو یک آرایه ذخیره شده، مثلاً 12، 43، 32، 14 و ...
مثلاً مسیر 14 یعنی از مکان 1 به مکان 4 یک مسیر هست. درسته؟
خب، حالا این مکان ها رو، سطر و ستون ماتریس درنظر میگیرید. مثلاً اگر 4 تا مکان دارید با نام های 1 و 2 و 3 و 4، باید یک ماتریس 4x4 درست کنید. حالا اون آرایه اولیه تون رو پیمایش میکنید و مسیرها رو از توش میخونید. مثلاً مسیر 14 رو میخونید، و بعد روی ماتریس، خونه موردنظر رو علامت میزارید. شکل زیر:


63569



وقتی تکلیف همه خونه های ماتریس مشخص شد. برای پیدا کردن تداخل ها به یک سطر یا ستون نگاه کنید، هرجا که 1 بود یعنی مسیری بین شماره سطر و ستونش وجود داره.


مشکل من اینه که چجوری بفهمی مسیر 12 با مسیر 14 تداخل داره
برای بررسی این اصلاً نیازی به گراف نیست. مبدأ هر دو مسیر، مکان 1 هست. پس تداخل دارند!

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

[morteza_bn]

سلام،

خب پس مشکلی نباید باشه دیگه!

اول باید گراف رو تشکیل بدید؛ بعد از روی گراف، تداخل ها رو تشخیص میدید. شما گفتید مسیرها تو یک آرایه ذخیره شده، مثلاً 12، 43، 32، 14 و ...
مثلاً مسیر 14 یعنی از مکان 1 به مکان 4 یک مسیر هست. درسته؟
خب، حالا این مکان ها رو، سطر و ستون ماتریس درنظر میگیرید. مثلاً اگر 4 تا مکان دارید با نام های 1 و 2 و 3 و 4، باید یک ماتریس 4x4 درست کنید. حالا اون آرایه اولیه تون رو پیمایش میکنید و مسیرها رو از توش میخونید. مثلاً مسیر 14 رو میخونید، و بعد روی ماتریس، خونه موردنظر رو علامت میزارید. شکل زیر:


63569



وقتی تکلیف همه خونه های ماتریس مشخص شد. برای پیدا کردن تداخل ها به یک سطر یا ستون نگاه کنید، هرجا که 1 بود یعنی مسیری بین شماره سطر و ستونش وجود داره.


برای بررسی این اصلاً نیازی به گراف نیست. مبدأ هر دو مسیر، مکان 1 هست. پس تداخل دارند!

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

واقعا ممنون از اینکه کامل جواب دادید من روش دیگه ای مد نظر داشتم ...
حالا می خوام بدونم با این گراف چطور تشخیص میدید که مسیر 13 با 24 تداخل داره یا 42 با 32...می بینید که با این روش نمیشه(بررسی کنید)...
من گراف رو بصورتی پیاده سازی کردم که هر مسیر یک درایه برای ماتریس هست
12 13 14 21 23 24 ......
12 0 0 0 0 0 ....
13 0 0 0 1 1 .....
14
21
23
24
.
.
.
و اگر دو مسیر با هم تداخل داشته باشند درایه برابر 1 و اگر تداخل نداشته باشند برابر 0 است...

حالا مشکل من تشکیل همین گراف هست چطور میشه از بررسی یک چهارراه متوجه شد که دو مسیر با هم تداخل ندارند یا دارند
البته این مساله فقط برای چهارراه نیست و میتواند 5راه 3راه 6 راه باشد که هر راه هم می تواند سه حالت داشته باشد(یک طرفه ورودی-یک طرفه خروجی یا دو طرفه)بسته به نیاز مخاطب...من می خوام این تشخیص برخورد یک حالت پویا داشته باشد یعنی خود سیستم برخورد رو بگه و ما فقط مسیرها رو به سیستم بدیم...بازم امیدوارم متوجه مشکل شده باشید...
من واقعا شرمنده ام از اینکه نمیتونم منظورمو درست بیان کنم...مشکل از خود منه...بازم به خاطر توضیحات کاملتون ممنونم

[morteza_bn]

سلام دوستان
دلم نیومد این پست بدون نتیجه باشه بنابراین راه حلی رو که برای این موضوع پیدا کردم می گم تا بدرد بقیه هم بخوره
از عزیز دلمxxxxx_xxxxx (http://barnamenevis.org/member.php?46030-xxxxx_xxxxx) هم ممنونم که با سعه صدر راهنمایی کردن
در واقع راه حل الگوریتمی نتونستم برای این موضوع پیدا کنم
ابتدا بگم مساله کلی من این بود که مشخصات یک تقاطع رو دریافت کنم و بگم توی چند زمان امکان داره این ماشین ها در تقاطع حرکت کنند که بدون برخورد باشند (البته این یک مساله کلاسیک و مشهور هست)
من ابتدا مسیرهایی که با هم برخورد دارن رو شناسایی کردم و از روی الگوریتم رنگ آمیزی گراف حداقل تعداد زمانهایی که می تونند ماشین ها حرکت کنند رو پیدا کردم
بخش دوم مساله که تقریبا ساده بود
مشکل در بخش اول بود که من کل مسیر های یک 6 راه که همه دو طرفه هستند و با هم برخورد دارند رو در یک آرایه دو بعدی ذخیره کردم سپس با توجه به ورودی مساله که مشخصات یک تقاطع بود(سه راه،چهار راه،پنج راه و 6 راه که مشخصات هر مسیر بصورت دو طرفه یا یک طرفه داده می شود) همه مسیرها رو ابتدا پیدا کردم و در یک آرایه ذخیره کردم و سپس با مقایسه این آرایه با آرایه دوبعدی مسیرهای دارای برخورد رو شناسایی کردم و...
اگر کسی از دوستا ن راه حل یا الگوریتم دیگه ای برای بخش اول این مساله سراغ داره بذاره تا همه از اون استفاده کنیم
با تشکر