تالار گفتمان مانشت

حتما به مشکلی که من برخوردم شما هم برخورد کردید در درخت هافمن

اگر حاصل محاسبه دو مقدار برابر بشه مثلا به 10 و ما دو مقدار اولیه 10 رو هم داشته باشیم
(یعنی در کل سه مقدار برابر که یکی از اش محاسبه به دست اومده و دوتاش مقدار اولیه هستند)
با چه ترتیبی باید این سه رو ترکیب کنیم؟
حتما متوجه شدید که درخت حاصل یکسان نخواهد بود

آره ولی اون مجموع حافظه استفاده شده فرقی نمیکنه.
فقط کدها هست که فرق میکنه.

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

(03 بهمن 1389 07:12 ب.ظ)afagh1389 نوشته شده توسط: [ -> ]آره ولی اون مجموع حافظه استفاده شده فرقی نمیکنه.
فقط کدها هست که فرق میکنه.

خوب حالا به هر حای یه چیزی فرق می کنه دیگه.
بحث من هم سر همین تفاوت هست

(03 بهمن 1389 07:51 ب.ظ)javadjj نوشته شده توسط: [ -> ]متاسفانه من عینا با این موضوع برخورد داشتم و مهم نظر طراح هستش و اونچه اون حل کرده و در ضمن هر دو نوع رو هم تو گزینه‌ها میزارن و نظر هم نظر خودشون اما من اگه گره جدید باشه میدم سمت راست و گرهی هم که حاصل جمع وزن های قبلی هستش رو سمت چپ

یعنی اگر درست متوجه شده باشم، یکی از دوتا گره مقدار اولیه رو با اون گره حاصل محاسبه قبلی می گیری آقا جواد؟
یا دوتا جدید‌ها رو جدا با هم حساب می کنی؟

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

خب نتیجه ای که از جمع دو تا نود بدست میاد چه الویتی نسبت به اعدادی که توی لیست موجود هستند داره کمتر از اوناست یا بیشتر؟
شما میگید به ترتیب، عددی که تازه بدست اومده کجا قرار میگیره بخصوص اگه اعداد مرتب نباشند

(04 بهمن 1389 02:42 ب.ظ)zr2358 نوشته شده توسط: [ -> ]خب نتیجه ای که از جمع دو تا نود بدست میاد چه الویتی نسبت به اعدادی که توی لیست موجود هستند داره کمتر از اوناست یا بیشتر؟
شما میگید به ترتیب، عددی که تازه بدست اومده کجا قرار میگیره بخصوص اگه اعداد مرتب نباشند

من جایی نگفتم مرتب باشن. بیبنید اگر 3 تا 10 توی یک مجموعه باشن از چپ به راست بدون در نظر گرفتن ترتیب بزگتر یا کوچکتر 2 تا 10 سمت چپ رو با هم جمع می کنی حاصل میشه 20. باز هم از چپ دنبال دو تا عدد کوچکتر میگردی مثلا 13 که قاعدتا با اون 10 باقیمونده جمع میشه میشه 23 . حالا تو مجموعه دنبال دوتا کوچکتر میگردیم که شاید اون 23 و 20 باشن یا شاید مثلا 15 با 20 باشه. اگر عدد تکراری داشت که مثل شیوه ای گه گفتم عمل می کنیم و اگر نبود که شیوه معمولی رو اجرا می کنیم و دو تا عدد جدید اضافه می کنیم.

(04 بهمن 1389 02:47 ب.ظ)grayman نوشته شده توسط: [ -> ]

(04 بهمن 1389 02:42 ب.ظ)zr2358 نوشته شده توسط: [ -> ]خب نتیجه ای که از جمع دو تا نود بدست میاد چه الویتی نسبت به اعدادی که توی لیست موجود هستند داره کمتر از اوناست یا بیشتر؟
شما میگید به ترتیب، عددی که تازه بدست اومده کجا قرار میگیره بخصوص اگه اعداد مرتب نباشند

من جایی نگفتم مرتب باشن. بیبنید اگر 3 تا 10 توی یک مجموعه باشن از چپ به راست بدون در نظر گرفتن ترتیب بزگتر یا کوچکتر 2 تا 10 سمت چپ رو با هم جمع می کنی حاصل میشه 20. باز هم از چپ دنبال دو تا عدد کوچکتر میگردی مثلا 13 که قاعدتا با اون 10 باقیمونده جمع میشه میشه 23 . حالا تو مجموعه دنبال دوتا کوچکتر میگردیم که شاید اون 23 و 20 باشن یا شاید مثلا 15 با 20 باشه. اگر عدد تکراری داشت که مثل شیوه ای گه گفتم عمل می کنیم و اگر نبود که شیوه معمولی رو اجرا می کنیم و دو تا عدد جدید اضافه می کنیم.

می دونم، متوجه منظورتون شدم
بحث این تاپیک اینه که مثلا اعداد زیر رو داریم
10 5 10 5 ...
دو تا 5 رو که با هم جمع کردیم جواب میشه 10
بعد دو تا 10 که توی اعداد اولیه هستند رو با هم جمع می کنید یا یکی از اونا رو با 10ی که الان با جمع 5ها بدست آوردی؟
شما میگید به ترتیب از چپ، حالا این 10ی که داریم قبل از ایناست یا بعدش یا ...

zr2358 جان
من به نتیجه ای که رسیدم این هست که باید حاصل اون دو تا 5 رو( که شده یک 10) با یکی از 10‌ها بگیریم
با اینکه این حالت درخت هافمن بدتری می ده‌، اما در تست های سال های قبل گویا این درخت بد مورد نظر بوده.

اون 10 که از مجموع دو تا 5 بدست آمده اولویتش پایین‌تر از 10 هایی است که تو مجموعه هست. البته من تا حالا ندیدم که این طوری باشه ولی طبق همون روشی که در کتاب بالاکرشتاین دیدم اولویت با عناصر قدیمی‌تر توی مجموعه است. منظور از قدیمی‌تر این که هنوز وارد درخت هافمن نشدن. اینجا 2 تا 10 باقیونده اولویت دارن نسبت به 10 که حاصل 2 تا 5 هست.
اگر بعد از جمع کردن هم نتایج بدست اومده یکسان بود دوباره باز اولویت با اونیه که از قبل تو مجموعه بوجو اومده نسبت به این عنصر مشابه جدید.

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

(05 بهمن 1389 12:35 ق.ظ)grayman نوشته شده توسط: [ -> ]اون 10 که از مجموع دو تا 5 بدست آمده اولویتش پایین‌تر از 10 هایی است که تو مجموعه هست. البته من تا حالا ندیدم که این طوری باشه ولی طبق همون روشی که در کتاب بالاکرشتاین دیدم اولویت با عناصر قدیمی‌تر توی مجموعه است. منظور از قدیمی‌تر این که هنوز وارد درخت هافمن نشدن. اینجا 2 تا 10 باقیونده اولویت دارن نسبت به 10 که حاصل 2 تا 5 هست.
اگر بعد از جمع کردن هم نتایج بدست اومده یکسان بود دوباره باز اولویت با اونیه که از قبل تو مجموعه بوجو اومده نسبت به این عنصر مشابه جدید.

دقیقا منم همینو می گم. این حالت بهینه رو می ده
اما در بسیاری از تست‌ها حالت غیر بهینه پاسخ بوده
دلیل اش هم واضح نیست

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

در ادامه صحبت های جناب دکتر در این تاپیک زیر خاکی باید گفت :

الگوریتم هافمن بهینه است پس در بدترین حالت نباید مصرف حافظه ای بیشتر از حالت معمول داشته باشیم .
در الگوریتم هافمن اگر تعداد بیشترین تکرار یک حرف از کمترین تعداد تکرار حرفی ، کمتر باشد آنگاه الگوریتم هافمن مزیتی ندارد .

یه نکته جالب ، ارسال های بالا رو ببینید ( بغیر از خود جناب دکتر ) الان همه بچه هایی که یه موقع اینجا در بحث علمی شرکت داشتن ؛ تمامی اونها الان دارن ارشد میخونن، مانشت در سال 89 خیلی قوی بود علتش هم همین بحث های علمی بود و اینکه کمتر به حاشیه میرفتن بچه ها . الان مانشت یکم تو حاشیه ها زیاد میره