راهنمایی برای قرار دادن بهینه نقاط

[mahsa_z]

سلام خدمت تمام استادید. دوستان من ی برنامه میخوام بنویسم که مثلا یک صفحه 20 خانه ای داریم و ده تا نقطه. و حالا میخوام این ده تا نقطه بصورت بهرین حالت ممکن توی صفحه پخش بشن که توی کل صفحه قرار داشته باشن. دوستان توجه داشته باشید که وقتی برنامه رو اجرا میکنم مکان نقطه ها و فاصله نقطه ها از یکدیگر بصورت تصادفی تولید میشن و در صفحه قرار میگیرن و حالا من باید ی تابعی بنویسم ک مشخص کنه ایا این راه حل بهترین طرز قرار گرفتنه یا طرز قرار گرفتن بهتری هم وجود داره(منظور از بهترین طرز اینه ک در کل صفحه پخش شده باشن و کم هزینه ترین مسیر باشه). برنامم خودش در حالت اول Nتا راه حل پیشنهاد میده و من باید تشخیص بدم ک کدوم یک از این راه حل ها بهترین راه حل هست(یعنی اول هزینه هر کدوم از Nتا راه حل رو حساب کنم و بهترین رو انتخاب کنم) و اون رو بعنوان راه حل نهایی انتخاب کنم. حالا من نمیدونم چطور ب برنامه بفمونم ک بهترین حالت قرار گیری نقاط چطور هست. دوستانی ک با بحث فیت نس الگوریتم ژنتیک آشنایی دارن فکر کنم کامل منظورم رو متوجه بشن.
باتشکر

[hamid_hr]

الان درست صورت مساله رو متوجه نشدم

مثلا یک صفحه 20 خانه ای داریم و ده تا نقطه. و حالا میخوام این ده تا نقطه بصورت بهرین حالت ممکن توی صفحه پخش بشن که توی کل صفحه قرار داشته باشن

منظور از بهترین حالت چی هست؟
مثلا کمترین فاصله رو با هم داشته باشن؟ یا بیشترین فاصله، با یه مساله دیکه مثل کمترین هزینه و یا هرچی

[mahsa_z]

الان درست صورت مساله رو متوجه نشدم

منظور از بهترین حالت چی هست؟
مثلا کمترین فاصله رو با هم داشته باشن؟ یا بیشترین فاصله، با یه مساله دیکه مثل کمترین هزینه و یا هرچی

منظورم اینه ک نقطه ها توی صفحه طوری پخش بشن ک بهترین حالت ممکن باشه. یعنی ن از هم دور باشن و ن بهم نزدیک باشن. مثلا فرض کنید اگه بخواهیم از نقطه x به نقطه دیگه ای بریم و سه نقطه a,b,c وجود داشته باشن و فاصله x از a برابر 20 و فاصله x تا b برابر 1 و فاصله x تا c برابر 10 باشه ما باید نقطه c رو انتخاب کنیم.

[hamid_hr]

خب ببینین میتونین یک جمعیت اولیه درس کنین شثلا شامل 100 تا والد
خب حالا میاین بر اساس همین نزدیکی و دوری اونو مرتب میکنین بعد اون والد هایی که وسط جمعیت قرار میگیرند بین 40 تا 60 میشن حالت های بهینه شما تو این جمعیت
حالا برا ساخت جمعیت بعدی از این جمعیت بیشراز این والدها (ردیف 40 تا 60) استفاده کنین
روی اینها mutation , crossover انجام بدین و یه تعدادی هم رو بدون تغییر.
باید یه تعداد هم فرزند جدید درست کنین که اونطوری همه سطح شما پوشش داده بشه

[mahsa_z]

خب ببینین میتونین یک جمعیت اولیه درس کنین شثلا شامل 100 تا والد
خب حالا میاین بر اساس همین نزدیکی و دوری اونو مرتب میکنین بعد اون والد هایی که وسط جمعیت قرار میگیرند بین 40 تا 60 میشن حالت های بهینه شما تو این جمعیت
حالا برا ساخت جمعیت بعدی از این جمعیت بیشراز این والدها (ردیف 40 تا 60) استفاده کنین
روی اینها mutation , crossover انجام بدین و یه تعدادی هم رو بدون تغییر.
باید یه تعداد هم فرزند جدید درست کنین که اونطوری همه سطح شما پوشش داده بشه

من با عملیات تولید جمعیت اول و crossover و mutation مشکلی ندارم . من فقط مشکلم تشخیص مسیر درسته. یعنی من نمیدونم چطور این تشخیص دوری یا نزدیکی رو برای نقطه های اطراف x پیدا کنم ک بعد مرتب سازیشون کنم

[hamid_hr]

خب احتمالا فاصله اقلیدوسی رو باید حساب کنید
اگر داده ها در فضای دو بعدی باشه اینطوری میشه

|x2-x1|+|y2-y1|

[mahsa_z]

خب احتمالا فاصله اقلیدوسی رو باید حساب کنید
اگر داده ها در فضای دو بعدی باشه اینطوری میشه

|x2-x1|+|y2-y1|

بله دوست عزیز من بلدم ک مثلا ی تابع بنویسم و دو مختصات بهش بدم و تابع فاصله دو نقطه رو برگردونه ولی من بلد نیستم ک این محسابات رو برای تمام فضای حالت انجام بده و نمیدونم ک چطور این فاصله رو برای تمام نقطه ها نسبت به همدیگه بدست بیارم. من باید فاصله تمام 10 نقطه موجود رو نسبت بهم بدست بیارم

[hamid_hr]

خب شما نیاز دارید دو تا حلقه تودرتو درست کنید از 0 تا 10

for(i=0;1<10;1++)

{

for(j=0;j<10;j++){

//محاسبه فاصله اقلیدوسی بین نقطه i,j

{

{

اینطوری بین تمام نقاط فاصله محاسبه میشه