Russian Qt Forum
Апрель 29, 2024, 05:42 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Интересная задачка
Страниц: [1] 2 3   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Интересная задачка  (Прочитано 20760 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Июнь 26, 2013, 13:37 »
Добрый день

Увидел задачку, и очень она мне понравилась
Цитировать
Дано поле, на котором случайным образом разбросаны пища (мощность 1-10), капканы (мощность 1-10), камни и пустые поля. Транспортер должен обойти максимально возможное число полей за минимальное количество ходов. При этом, если он входит на клетку с пищей, то мощность у него прибавляется на заданное количество единиц, но не более, чем на 100. Если транспортер попадает в капкан, его энергии убавляется (если достигнет нуля - транспортер уничтожен). Камни пройти нельзя.
Правда совсем нет мыслей как делать Улыбающийся А у Вас?

Спасибо
Записан
Bepec
Гость
« Ответ #1 : Июнь 26, 2013, 15:17 »
Нет данных о видимости.

На сколько клеток есть данные? Или всё поле сразу дано? Или же транспортер слепой и знает только  можно в том направлении ехать или нельзя?/* Что будет при столкновение с камнем? мало данных.*/

update: увидел про камень.

Если нет видимости, то простой алгоритм обхода. Если есть - более сложные алгоритмы.
« Последнее редактирование: Июнь 26, 2013, 15:35 от Bepec » Записан
CuteBunny
Гость
« Ответ #2 : Июнь 26, 2013, 15:29 »
Мне кажется алгоритм Прима здесь применим.
Записан
Странник
Гость
« Ответ #3 : Июнь 26, 2013, 15:49 »
уточните следующее:
- начальное поле
- начальная мощность
- требует ли перемещение затрат мощности?
- может ли транспортер перемещаться по диагонали?
- после первого посещения клетки с пищей или капканом она становится пустой?
- должен ли транспортер выжить?
« Последнее редактирование: Июнь 26, 2013, 15:57 от Странник » Записан
Bepec
Гость
« Ответ #4 : Июнь 26, 2013, 15:52 »
Если будут усложнения получится маленький ботик для этой игры (задачи).
 

PS Я в принципе ничего другого от Igors не жду Улыбающийся Отсутствие конкретизированных требований и ограничений и неясная задача :-D Стандарт.
Записан
Old
Джедай : наставник для всех
*******
Online Online

Сообщений: 4349



Просмотр профиля
« Ответ #5 : Июнь 26, 2013, 16:03 »
Можно сделать арену и гонять там ботов, боты делать на javascript. Нужно только определится с API.
Записан
Majestio
Гость
« Ответ #6 : Июнь 26, 2013, 16:06 »
Цитата: Bepec от Июнь 26, 2013,  15:52
Если будут усложнения получится маленький ботик для этой игры (задачи).
PS Я в принципе ничего другого от Igors не жду Улыбающийся Отсутствие конкретизированных требований и ограничений и неясная задача :-D Стандарт.

  • Если "видимость" - с алгоритмом проблем нет. Задача решается обходом дерева перемещений-возвратов, с оценкой весов путей.
  • Если видимости нет - сложнее. Можно попробовать обучающиеся нейронные сети, но это сработает только в том случае, если разброс "сущностей" на поле - случайный-неравномерный или закономерный

ИМХО конечно.
Записан
Bepec
Гость
« Ответ #7 : Июнь 26, 2013, 16:49 »
В принципе несложная задачка, решаемая простыми алгоритмами. НО... Но Igors мастер таких вот размытых задач Показает язык
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Июнь 26, 2013, 17:00 »
Цитата: Странник от Июнь 26, 2013,  15:49
уточните следующее:
- начальное поле
...
- должен ли транспортер выжить?
Цитата: Bepec от Июнь 26, 2013,  15:17
Нет данных о видимости.

На сколько клеток есть данные? Или всё поле сразу дано? Или же транспортер слепой и знает только  можно в том направлении ехать или нельзя?/*
"Ну Вы блин даете" Улыбающийся Зачем говорить о некой "видимости" если условие начинается со слов "дано поле"? Наверное пока дочитали до конца - уже забыли начало Улыбающийся И прекрасный вопрос "должен ли транспортер выжить?" - а сами-то как думаете? Или "начальное поле" - типа нет, сначала он на вертолете летает, а потом уж....   Улыбающийся  

Другие вопросы имеют смысл
Цитата: Странник от Июнь 26, 2013,  15:49
- начальная мощность
- требует ли перемещение затрат мощности?
- может ли транспортер перемещаться по диагонали?
- после первого посещения клетки с пищей или капканом она становится пустой?
(особенно последний). Но ответы на них мне неизвестны (задача не моя). Поэтому мы имеем право принять такие соглашения

- да, есть начальный запас топлива, напр 100 (максимальный)
- нет, перемещение не требует затрат, только капкан уменьшает энергию
- нет, перемещение по диагонали запрещено
- нет, после посещения пищи/капкана они не исчезают.

Хотя я в упор не вижу что это меняет - с этими условиями или др - все равно ни одной мысли нет  Улыбающийся

Цитата: Majestio от Июнь 26, 2013,  16:06
Если "видимость" - с алгоритмом проблем нет. Задача решается обходом дерева перемещений-возвратов, с оценкой весов путей.
Как только я слышу что-то типа "проблем нет" - мгновенно в голове проносится фразв "це дiлa не буде". Максимум человек отпихнется ссылкой на нечто (часто вообще не имеющее отношения) - и все. Или я ошибаюсь ?  Улыбающийся  

Цитата: Majestio от Июнь 26, 2013,  16:06
Если видимости нет - сложнее. Можно попробовать обучающиеся нейронные сети, но это сработает только в том случае, если разброс "сущностей" на поле - случайный-неравномерный или закономерный
Ну пошли понты  Улыбающийся

Цитата: Bepec от Июнь 26, 2013,  16:49
В принципе несложная задачка, решаемая простыми алгоритмами. НО...
Но могут взять за жопу и предложить ответить за свою похвальбу  Улыбающийся
« Последнее редактирование: Июнь 26, 2013, 17:07 от Igors » Записан
Bepec
Гость
« Ответ #9 : Июнь 26, 2013, 17:07 »
Видимость я спрашивал.

Дано поле 40 на 40.

Оно закрыто как в сапёре, ИЛИ мы имеем данные о том, что находится в каждой клетке данного поля?

PS ваша (или скопированная) формулировка имеет двоякое значение. То ли мы имеем все данные, то ли мы имеем только размеры поля.

PPS про выживание вопрос интересный, а не глупый. Открытие последней клетки с капканом (-10hp) убьёт транспортёр (10hp) и что будет? победа или поражение? Веселый В простых играх этот момент меня иногда выбешивал Веселый Когда всё, босса завалил, счастливый стоишь и оп - яд тебя добивает Веселый И вместо "Вы прошли игру" -> "Ты сдох мерзкий герой" Веселый
« Последнее редактирование: Июнь 26, 2013, 17:10 от Bepec » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #10 : Июнь 26, 2013, 17:09 »
Цитата: Bepec от Июнь 26, 2013,  17:07
Видимость я спрашивал.
Отвечаю - весь расклад известен, все клетки "открыты"
Записан
Old
Джедай : наставник для всех
*******
Online Online

Сообщений: 4349



Просмотр профиля
« Ответ #11 : Июнь 26, 2013, 17:15 »
Цитата: Igors от Июнь 26, 2013,  17:00
- да, есть начальный запас топлива, напр 100 (максимальный)
Ok

Цитата: Igors от Июнь 26, 2013,  17:00
- нет, перемещение не требует затрат, только капкан кмкньшает энергию
Не согласен. Перемещение требует -1 энергии.

Цитата: Igors от Июнь 26, 2013,  17:00
- нет, перемещение по диагонали запрещено
Ok

Цитата: Igors от Июнь 26, 2013,  17:00
- нет, после посещения пищи/капкана они не исчезают.
Тоже не согласен. По мне, так и первое и второе должно исчезнуть после контакта.

Цитата: Igors от Июнь 26, 2013,  17:00
Хотя я в упор не вижу что это меняет - с этими условиями или др - все равно ни одной мысли нет  Улыбающийся
А здесь интересно экспериментировать. Описал логику, запустил в арене, посмотрел результат. Поменял карту, запустил, посмотрел.
Для начала лобовая логика: двигаться по линии вправо, пока не дойдешь до конца карты -> опуститься вниз на одну клетку и двигаться влево, до начала карты. А потом можно пробовать варианты с обходом препятствий.
Или второй вариант, двигаться по спирали от стартовой точки.
Много всего можно придумать, но интересно будет когда будет арена и визуально можно будет смотреть на действия бота.
Записан
Old
Джедай : наставник для всех
*******
Online Online

Сообщений: 4349



Просмотр профиля
« Ответ #12 : Июнь 26, 2013, 17:17 »
Цитата: Igors от Июнь 26, 2013,  17:09
Отвечаю - весь расклад известен, все клетки "открыты"
Здесь тоже не соглашусь. По мне интересней, если бот будет иметь ограниченную видимость.
Записан
Majestio
Гость
« Ответ #13 : Июнь 26, 2013, 17:24 »
Цитата: Igors от Июнь 26, 2013,  13:37
Цитировать
Дано поле, на котором случайным образом разбросаны пища (мощность 1-10), капканы (мощность 1-10), камни и пустые поля. Транспортер должен обойти максимально возможное число полей за минимальное количество ходов. При этом, если он входит на клетку с пищей, то мощность у него прибавляется на заданное количество единиц, но не более, чем на 100. Если транспортер попадает в капкан, его энергии убавляется (если достигнет нуля - транспортер уничтожен). Камни пройти нельзя.

Учитывая последующие "уточнения" - я бы предложил алгоритм, похожий на "обойти ходом шахматного коня поле". Идея "правильности" алгоритма - планировать так последующий ход, чтобы как можно плотнее прижиматься к краям поля. Иными словами - сужающаяся спираль. Я бы пробовал именно так.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #14 : Июнь 26, 2013, 17:32 »
Цитата: Old от Июнь 26, 2013,  17:15
нет,
...
Тоже не согласен. По мне, так и первое и второе должно исчезнуть после контакта.
...
Здесь тоже не соглашусь.
...
Да пожалуйста, можно принять любой из вариантов, но, во всяком случае на данном этапе я не вижу никакой разницы

Цитата: Old от Июнь 26, 2013,  17:15
А здесь интересно экспериментировать. Описал логику, запустил в арене, посмотрел результат. Поменял карту, запустил, посмотрел.
Для начала лобовая логика: двигаться по линии вправо, пока не дойдешь до конца карты -> опуститься вниз на одну клетку и двигаться влево, до начала карты. А потом можно пробовать варианты с обходом препятствий.
Или второй вариант, двигаться по спирали от стартовой точки.
Много всего можно придумать, но интересно будет когда будет арена и визуально можно будет смотреть на действия бота.
Я тоже думал об этих вариантах (других не было), но они не имеют никакой разумной "стратегии". Напр встретив камень мы его обошли (пусть пока не знаю как) но при этом наш порядок обхода пострадал - напр остались клетки позади камня. И что дальше? Продожать сканирование в данном порядке - а как потом вернуться к пропущенным? Примерно то же когда много капканов
Записан
Страниц: [1] 2 3   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.054 секунд. Запросов: 22.