Tree

[goodboy2]

سلام . خیلی گشتم و سعی کردم اما جواب نگرفتم ( نگید اول بگرد بعد بیا )
کد ساخت درخت با 4 بچه و insert و search رو میخوام :|
سوال : داده های نود ها (بچه ها) از نوع ماتریس 3 در 3 هست . آیا نوع نود در اینجا آبجکت میشه ؟ یا آرایه میشه ؟
اینارو میخوام

[vahid-p]

آرایه هم خودش آبجکته. پس یک آرایه 3*3 در هر نود به عنوان مقدار اون نود ذخیره کنید.
کلا نحوه insert و search وابسته به نوع درخت هست. درخت یک داده ساختار کلی هست.

برای حل پازل 1-8 میخوای؟

[goodboy2]

آرایه هم خودش آبجکته. پس یک آرایه 3*3 در هر نود به عنوان مقدار اون نود ذخیره کنید.
کلا نحوه insert و search وابسته به نوع درخت هست. درخت یک داده ساختار کلی هست.

برای حل پازل 1-8 میخوای؟

واوو استاد از کجا فهمیدید
بله پروژه 8پازل رو دارم .
کل 13 روز رو با php صرف کردم بنویسم آخرشم بخاطر کمبودای php نتونستم :| الان میخوام با جاوا بنویسم .
برای همین درخت و 3 خونه و آبجکت و اینسرت و ... رو پرسیدم.
دادا خودتون دانشجو بودین ترم آخرم هستم هرچی کمکتون میاد دریغ نفرمایید مخم طی 4 سال خالی شده دیگه

[vahid-p]

شما برای اینکه مراحل تکراری رو انجام ندید باید ببینید قبلا چنین حالتی ایجاد شده یا نه. برای این منظور یکی از بهترین ساختارها درخت جستجو دودویی هست که مراحل تکراری رو سریع پیدا کنید و انجام ندید.
پیاده سازی BST:
http://algorithms.tutorialhorizon.co...mplementation/

و به یک درخت برای ایجاد حالات مختلف نیاز دارید، در حقیقت چیزی که در پست اول پرسیدید.
تابع getEuclides هم فاصله حالت فعلی از حالت مطلوب رو محاسبه میکنه و ارتباطی با ساخت درخت نداره.

public class Tree {



    TNode root;





    public Tree(String str) {

        root = new TNode(str, null);

    }





    void addLeft(TNode pn, TNode tn) {

        pn.left = tn;

    }





    void addRight(TNode pn, TNode tn) {

        pn.right = tn;

    }





    void addUp(TNode pn, TNode tn) {

        pn.up = tn;

    }





    void addDown(TNode pn, TNode tn) {

        pn.down = tn;

    }





    private class TNode {





        TNode parentNode;

        TNode left;

        TNode right;

        TNode up;

        TNode down;

        String value;

        int euclids;





        TNode(String val, TNode p) {

            left = null;

            right = null;

            up = null;

            down = null;

            value = val;

            euclids = getEuclids();

            parentNode = p;

        }





        void setLeft(TNode le) {

            left = le;

        }





        void setRight(TNode ri) {

            right = ri;

        }





        void setUp(TNode u) {

            up = u;

        }





        void setDown(TNode dow) {

            down = dow;

        }





        boolean isFinal() {

            return euclids == 0;

        }





        int getEuclids() {

            int sum = 0, v = 0, h = 0;

            for (int i = 0; i < 9; i++) {

                switch (value.charAt(i) - '0') {

                    case 1:

                        v = i / 3;

                        h = i % 3;

                        break;

                    case 2:

                        v = i / 3;

                        h = i % 3 - 1;

                        break;

                    case 3:

                        v = i / 3;

                        h = i % 3 - 2;

                        break;

                    case 4:

                        v = i / 3 - 1;

                        h = i % 3 - 2;

                        break;

                    case 0:

                        v = i / 3 - 1;

                        h = i % 3 - 1;

                        break;

                    case 8:

                        v = i / 3 - 1;

                        h = i % 3;

                        break;

                    case 5:

                        v = i / 3 - 2;

                        h = i % 3 - 2;

                        break;

                    case 6:

                        v = i / 3 - 2;

                        h = i % 3 - 1;

                        break;

                    case 7:

                        v = i / 3 - 2;

                        h = i % 3;

                        break;

                }

                sum += Math.abs(v) + Math.abs(h);

            }

            return sum;

        }

    }

}

اگر هم کد آمادشو میخوای که 8 puzzle java code بزنی تو اینترنت هست

[goodboy2]

شما برای اینکه مراحل تکراری رو انجام ندید باید ببینید قبلا چنین حالتی ایجاد شده یا نه. برای این منظور یکی از بهترین ساختارها درخت جستجو دودویی هست که مراحل تکراری رو سریع پیدا کنید و انجام ندید.
پیاده سازی BST:
http://algorithms.tutorialhorizon.co...mplementation/

و به یک درخت برای ایجاد حالات مختلف نیاز دارید، در حقیقت چیزی که در پست اول پرسیدید.
تابع getEuclides هم فاصله حالت فعلی از حالت مطلوب رو محاسبه میکنه و ارتباطی با ساخت درخت نداره.
اگر هم کد آمادشو میخوای که 8 puzzle java code بزنی تو اینترنت هست

خدا عوض بده ممنونم ک جواب دادید .


توضیح نمیخواد کد ؟ up down left roight چیه ؟ چپ و راست بچه ها و آپ هم پرنت هست (آیا؟) پس downl چی هست !!
این search نداره ؟! و اینسرت در درخت دودویی نیاز به دانستن لفت و رایت نداره که خودش بر اساس کوچک بزرگی تو درخت اضافه میکنه پس آیا نمیشد یه متد فقط بنام add باشه که مقدار بگیره بذاره تو درخت !!!؟ همین !
یه سوال دیگه ! مقادیر تمامی ماتریس های این درخت همه 1 تا 8 و 0 هست فقط جاشون فرق داره حالا چطور باید دو ماتریس رو مقایسه کنم و کوچیکرو بذارم شاخه چپ و بزرگرو بذارم شاخه راست ؟

[vahid-p]

up left right down همشون بچه ها هستن که جهت جابه جایی خانه خالی در پازل رو مشخص میکنه. اگر دقت کنید نوشته parentNode که اون پرنت هست.

این search نداره ؟! و اینسرت در درخت دودویی نیاز به دانستن لفت و رایت نداره که خودش بر اساس کوچک بزرگی تو درخت اضافه میکنه پس آیا نمیشد یه متد فقط بنام add باشه که مقدار بگیره بذاره تو درخت !!!؟ همین !

من کد درخت دودویی رو نذاشتم. اون لینکی که دادم کدش هست.

[goodboy2]

up left right down همشون بچه ها هستن که جهت جابه جایی خانه خالی در پازل رو مشخص میکنه. اگر دقت کنید نوشته parentNode که اون پرنت هست.


من کد درخت دودویی رو نذاشتم. اون لینکی که دادم کدش هست.

من خودم یه متد نوشتم که ماتریس رو بهش میدی و اون تمام ماتریس های حالت رو میده بیرون (مثلا خانه خالی میره بالا میشه یه ماتریس میره پایین میشه یه ماتریس دیگه و...)
بعد این ماتریس های حالت رو به درخت اضافه میخوام کنم و هر بار بررسی کنم درخت رو که آیا به جواب رسیده یا نه !
این روش منه .

یه سوال دیگه ! مقادیر تمامی ماتریس های این درخت همه 1 تا 8 و 0 هست فقط جاشون فرق داره حالا چطور باید دو ماتریس رو مقایسه کنم و کوچیکرو بذارم شاخه چپ و بزرگرو بذارم شاخه راست ؟

[goodboy2]

دادا اصن یه چیزی . من فک کنم با درخت دودویی bst کارم را نمیوفته . یعنی :
درختی باید داشته باشم که دو تا بچه داره اما نحوه اضافه شدن فرزند به پرنت مقایسه ای نیست . یعنی اول روت بعد سمت چپش بعد راستش و همینجوری :
Untitled.png
و هر بار که اضافه میکنم تو درت بررسی میکنم که قبلا اضافه شده یا نه در اینصورت تکراری هم نداریم دیگه . اینطوری دیگه نیازی به مقایسه ماتریس ها ندارم و هر بار حالت های هر ماتریس رو که گرفتم میذارم تو درخت .
یعنی یه متد یکی یکی از درخت(ماتریس هارو) میگیره بعد حالت هاشو (ماتریس های دیگه) رو در میاره میذاره تو درخت باز (و تکراری بودن یا نبودن و جواب بودن یا نبودن ) رو هم بررسی میکنه .
این فک کنم جواب بده . برای همین فقط کد درختی رو میخوام که bst نباشه و مثل شکل بالا یکی یکی add کنه و یک متد search برای بررسی تکرار هم داشته باشه همین !
میدونم کلا روش پرسیدن و ... غلطه اما بخدا اگه همین پروژرو هم بدم از فردا سوال درسی نمیپرسم

[vahid-p]

خب پس از bst استفاده نکن (ولی اینجوری سرچ تو درخت خیلی خیلی طول خواهد کشید).
همون کد دومی کلاس Tree رو یکم تغییرش بده (من به جای ماتریس 3*3 یک رشته رو در نظر گرفتم مثلا 102387645 که به ترتیب از چپ به راست و بالا به پایین پازل و 0 یعنی خانه خالی). مثلا این کد زیر فکر کنم بتونه درخت رو به صورت DFS سرچ کنه:

 boolean isDuplicated(String val, TNode node){ if(node==null) return false;

return node.value.equals(val) || isDuplicated(val, node.left) || isDuplicated(val, node.right) || isDuplicated(val, node.up) || isDuplicated(val, node.down);

}

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

[goodboy2]

خب پس از bst استفاده نکن (ولی اینجوری سرچ تو درخت خیلی خیلی طول خواهد کشید).
همون کد دومی کلاس Tree رو یکم تغییرش بده (من به جای ماتریس 3*3 یک رشته رو در نظر گرفتم مثلا 102387645 که به ترتیب از چپ به راست و بالا به پایین پازل و 0 یعنی خانه خالی). مثلا این کد زیر فکر کنم بتونه درخت رو به صورت DFS سرچ کنه:

 boolean isDuplicated(String val, TNode node){ if(node==null) return false;

return node.value.equals(val) || isDuplicated(val, node.left) || isDuplicated(val, node.right) || isDuplicated(val, node.up) || isDuplicated(val, node.down);

}

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

یه چیزایی بذهنم رسید .

[goodboy2]

متن کد حذف شد

[goodboy2]

آقا اشکالو پیدا کردم فقط بگید چطوری حلش کنم !(توصیح میخوام نه کد)
تعداد دفعات insert شدن از تعداد دفعات بررسی درخت (در متد start) بیشتره . یعنی تعدادی از شاخه ها رو رد میکنه و بررسی نمیکنه
یعنی :
Untitled.png
حالا چی کار کنم ؟ یعنی یجوری که درخته هر بار از اول شروع کنه جست و جو کنه ! یا مثلا اونی که در سطح بالاتر insert شد رو هم بررسی کنه !
روشی بلدید ؟

[goodboy2]

متن کد حذف شد

[vahid-p]

اگر عجله ندارید من تا چند روز آینده میتونم کدتون رو چک کنم. ولی الان به دلیل امتحان، واقعا سوالی که آنالیز بخواد نمیتونم وقت بذارم!

یا سایر دوستان اگر تاپیک رو پیگیری کردن، بتونن چک کنن.

[goodboy2]

اگر عجله ندارید من تا چند روز آینده میتونم کدتون رو چک کنم. ولی الان به دلیل امتحان، واقعا سوالی که آنالیز بخواد نمیتونم وقت بذارم!

یا سایر دوستان اگر تاپیک رو پیگیری کردن، بتونن چک کنن.

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