Задачи!

[Гост]

1. Безкрайна равнина – пустиня. Знаете, че има
петролно находище с формата на квадрат с размери 1 км x 1
км. Как ще го търсите?
2. Август. Жега 38 градуса по Целзий, а вие имате
само 2 жетона за телефон в джоба. Стоите на един безлюден
път, безкраен в двете посоки. Знаете, че някъде на този път
има хубава кръчма с безплатна ледено-студена бира. (или
сладолед ... по избор), но не знаете в коя посока. Как ще
намерите кръчмата?

[Davids]

Първата си ми изглежда като textbook пример за обхождане в ширина (BFS - breadth first search) в безкрайна квадратна мрежа.

Втората е интересна, поне аз не се сещам от раз за интуитивно оптимален подход, но ще да е нещо от сорта на експоненциално ускоряващо махало в двете посоки на пътя. Т.е. първо 2 км надясно, после се връщаме до началото и 4км наляво, после пак 8км надясно и на всяка врътка удвояваме проверената дистанция на посоката и ги редуваме. Всяка следваща итерация ще е три пъти по-сложна от предходната, което ни дава сложност $3^n$ и това не ми звучи много оптимално, та най-вероятно трябва да се помисли още.

[peyo]

1. Безкрайна равнина – пустиня. Знаете, че има
петролно находище с формата на квадрат с размери 1 км x 1
км. Как ще го търсите?

Първата си ми изглежда като textbook пример за обхождане в ширина (BFS - breadth first search) в безкрайна квадратна мрежа.

Аз си мисля, че по-скоро ще търсим по спирала (архимедова или може би квадратна?!) с растояние между съседните линии 1 км.

Като се замисля повече, по-голям смисъл има спиралата да е квадратна, защото архимедовата май ще е по-малко ефективна. Но също така ние не знаем как е разположен търсения квадрат спрямо осите и може би архимедова е по-добра. Може би една симулация ще даде отговор.

[peyo]

2. Август. Жега 38 градуса по Целзий, а вие имате
само 2 жетона за телефон в джоба. Стоите на един безлюден
път, безкраен в двете посоки. Знаете, че някъде на този път
има хубава кръчма с безплатна ледено-студена бира. (или
сладолед ... по избор), но не знаете в коя посока. Как ще
намерите кръчмата?

Това което трябва да минимизираме е пътя който ще изминем. Ако знаем колко най-далече е възможно да се намира кръчмата, тогава оптималното решение ще е да вървим това разстояние надясно и ако не я намерим да се върнем наляво. Тогава ще изминем 3-пъти повече път. Но вероятността да уцелим вярната посока е 0.5, значи средно ще изминем 2-пъти повече път.

Ако не знаем нищо за разтоянието, но знаем колко време ще живеем без бира е по-сложно. Например тогава вървим 1/3 от това време надясно, ако не е там , вървим останалите 2/3 наляво и може би ще оцелеем и средно ше вървим 2 пъти повече път в случаите когато оцелеем. Или може би просто върви надясно докато можем и ако оцеллеем ще сме вървяли по оптималния път. Тук не съм сигурен каква е печелившата стратегия.

Ако не знаем нищо за разстоянието и живеем безкрайно, то тогава трябва да измислим някаква наляво-надясно стратегия. Акои всеки път когато сменим посоката умножаваме разстоянието от нулата с някакъв коефицент тогава става много интересно. Ето една симулация на този коефицент който е по X , а по Y е средно колко пъвече път вървим спрамо разстоянието до кръчмата:

pustinia2.png (35.98 KiB) Прегледано 1195 пъти

Виждаме много интересни минимуми, които не съм сигурен по каква формула могат да се получат.