בהנתן גרף לא מכוון ופשוט, נניח ואני מריץ
BFS מצומת כלשהי, U
אני תמיד אקבל את אותו עץ BFS?
או שיכול להיות שיש בחירה רנדומלית מבין השכנים ואז אפילו עבור הרצות מאותו מקום התחלתי אני עלול לקבל עצים שונים?
אבל צורת הבחירה מובנית בתוך האלגוריתם, כלומר לפי איך שאני רואה את זה הוא תמיד יבחר אחד משני הדברים, ובהכרח יבחר את אותו הדבר בכל הרצה.
אלא אם כן האלגוריתם מוגדר להיות עם בחירה רנדומלית אני לא מבין למה אני יכול לקבל שני עצים שונים.
Hi,
BFS as you learned in class does not specify a tie-breaking choice because it works for any tie-breaking choice, even randomized ones. Obviously, when you program BFS, you will have to program some way to break ties, implicitly or explicitly.
In this course all the algorithms we consider are deterministic, so if you have a deterministic choice, then yes, you will always have the same output given the same input.
If you have a randomized tie-breaking rule (not sure why it would be useful in BFS, but it's possible), then obviously your output will depend on the random bits. In that case in my example from above, you can choose 2 with some probability and 4 with some probability, and get different trees for different executions.
Notice that the queue is not randomized though!
אז במקרה שלנו, נאמר בשיעורי הבית, אני יכול להתייחס לאלגוריתם כדטרמיניסטי? כלומר נקבל את אותו העץ בכל ריצה?
You can always assume the algorithms in the course are deterministic, so in that sense, yes.
But just to be very clear, it really depends on the question.
For example, if I ask "will BFS always have the same output on a specific graph?" I probably mean, "will every algorithm that is a deterministic BFS algorithm have the same output on a specific graph". I am probably not asking whether something deterministic always acts the same way, because that really has very little to do with this course…
We try to be as clear as possible, but we are human.. In general, if you are unsure about exactly what we mean, please just ask us. Do you have a particular question in mind?
כן, נניח שאלה 6ב בש.ב
אני יכול בקלות להפריך אותה בהנתן שעל אותו גרף אקבל תמיד את אותו עץ ביאפאס , אך קיימים שני עצים פורשים של מסלולים קצרים ביותר שונים.
לכן ברור כי עץ הביאפאס יתאים לכל היותר לאחד מהם אך לא לשני
אך בצורת ההפרכה שהראתי אני מסתמך לחלוטין על העובדה שעץ הביאפאס ישאר זהה , כי אם לא ייתכן שהוא ייצא מתאים לשניהם.
That question is asking "is there some BFS…" i.e. is there some implementation of BFS that will give this tree?
It is not asking "does some specific implementation of BFS give all trees?"
So if it doesn't depend on implementation, how do you generally define a BFS tree?