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

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

Russian Qt Forum > Forum > Программирование > Алгоритмы > Интересная задачка
Страниц: 1 [2] 3   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Интересная задачка  (Прочитано 20762 раз)
Bepec
Гость
« Ответ #15 : Июнь 26, 2013, 17:35 »
Если капканы и еда не исчезает, пойдёт алгоритм проезда по всем капканам до 10 hp и поездка нажраться )
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4349



Просмотр профиля
« Ответ #16 : Июнь 26, 2013, 17:36 »
Цитата: Igors от Июнь 26, 2013,  17:32
Примерно то же когда много капканов
Стоп, капканы бот видеть тоже не должен, иначе теряется их смысл. Улыбающийся

IMHO, здесь не идет речь четко обойти все (без исключения) клетки, требуется обойти как можно больше. Т.е. это соревнования стратегий.
А для этого нужно проводить "бои" и сравнивать.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #17 : Июнь 26, 2013, 17:40 »
Цитата: Old от Июнь 26, 2013,  17:36
Стоп, капканы бот видеть тоже не должен, иначе теряется их смысл. Улыбающийся
Вы все-таки уходите/углубляйтесь "в решение", а не в "условие"  Улыбающийся
Записан
Bepec
Гость
« Ответ #18 : Июнь 26, 2013, 17:46 »
Тут такая засада. Пока нет начальных данных, решение может плавать Веселый

Вот если бот видит все капканы, но незнает сколько они дают - будет в разы легче Веселый
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4349



Просмотр профиля
« Ответ #19 : Июнь 26, 2013, 17:53 »
Цитата: Igors от Июнь 26, 2013,  17:40
Вы все-таки уходите/углубляйтесь "в решение", а не в "условие"  Улыбающийся
Вы мне предлагаете написать арену?
Идеи следующий:
боты пишутся на javascript, ядро предоставляет боту небольшое api для исследования карты: посмотреть что в соседних ячейках и переместиться в соседнюю ячейку. Если в клетке:
* пусто - -1 энергии и переместиться на клетку;
* камень - -1 энергии и остались на месте;
* капкан - -10 энергии и переместиться на клетку;
* еда - +10 энергии и переместиться на клетку.

Ядро генерирует карту нужного размера и с нужными параметрами, дальше ядро начинает дергать метод бота tick(), в котором бот "осматривается" и принимает решение куда двигаться дальше.
Ядро все это дело визуализирует и считает количество шагов, пройденных клеток и т.д.
Ботов может быть много и они могут ходить по одной или разным картам.
Записан
kambala
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4727



Просмотр профиля WWW
« Ответ #20 : Июнь 26, 2013, 18:17 »
Цитировать
Транспортер должен обойти максимально возможное число полей за минимальное количество ходов
это требование означает, что задача является оптимизационной, и никакой речи о неполной видимости не может и быть. или решение не обязано быть оптимальным (т.е. можно хоть полный перебор использовать)?

еще не сказано можно ли посещать клетки больше одного раза.
Записан
Изучением C++ вымощена дорога в Qt.

UTF-8 has been around since 1993 and Unicode 2.0 since 1996; if you have created any 8-bit character content since 1996 in anything other than UTF-8, then I hate you. © Matt Gallagher
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #21 : Июнь 26, 2013, 18:30 »
Цитата: kambala от Июнь 26, 2013,  18:17
Цитировать
Транспортер должен обойти максимально возможное число полей за минимальное количество ходов
это требование означает, что задача является оптимизационной, и никакой речи о неполной видимости не может и быть. или решение не обязано быть оптимальным (т.е. можно хоть полный перебор использовать)?
Согласен, в постановке автора - все поле открыто (и все веса известны). Хотя и закрытое (полуоткрытое) поле - тоже интересно. Повторюсь - пока не видно что вообще делать  Улыбающийся

Цитата: kambala от Июнь 26, 2013,  18:17
еще не сказано можно ли посещать клетки больше одного раза.
Мне кажется это оговаривать не нужно. Напр в левом верхнем углу свободные клетки, а перед ними "забор" из камней
Цитировать
000
ххх
До угла никак не добраться не пройдя какие-то др клетки дважды

Цитата: Old от Июнь 26, 2013,  17:53
Вы мне предлагаете написать арену?
Ну "не запрещаю" Улыбающийся Мне лично неясно что писать - нет идей. Подумаю, если что-то будет - завтра напишу (чтобы по пустому не месить)
Записан
kambala
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4727



Просмотр профиля WWW
« Ответ #22 : Июнь 26, 2013, 19:03 »
Цитата: Igors от Июнь 26, 2013,  18:30
Цитата: kambala от Июнь 26, 2013,  18:17
еще не сказано можно ли посещать клетки больше одного раза.
Мне кажется это оговаривать не нужно. Напр в левом верхнем углу свободные клетки, а перед ними "забор" из камней
Цитировать
000
ххх
До угла никак не добраться не пройдя какие-то др клетки дважды
вообще-то нужно, и еще нужно придумать критерий оптимальности. если например посещать эти 3 клетки, закрытые камнями, то придется делать лишние ходы, чтобы вернуться (может в момент попадания в такую ситуацию будет невыгодно делать 3 лишних хода ради покрытия 3 полей, только если это не будут последние клетки).
Записан
Изучением C++ вымощена дорога в Qt.

UTF-8 has been around since 1993 and Unicode 2.0 since 1996; if you have created any 8-bit character content since 1996 in anything other than UTF-8, then I hate you. © Matt Gallagher
CuteBunny
Гость
« Ответ #23 : Июнь 26, 2013, 19:41 »
А если так?

Входное поле магическим образом превращается в частично связный (частично потому что есть камни и пустоты) неориентированный (т.к. из одного узла можно дойти до другого и наоборот) граф. Выбираем случайный начальный узел в этом графе, смотрим, с какими другими узлами связан данный узел и какие узлы в этом списке мы не обошли, если по Приме, то нужно выбрать из этого списка такой узел, вес ребра до которого наименьшее, а если вес ребра - постоянное число, берем случайный узел из этого списка; и т.к. далее, пока не обойдем все узлы до которых можно дойти. Если дошли до такого узла, у которого все связные с ним мы уже обошли - наверное это тупик, надо посмотреть другие узлы несвязные с этим, которые мы еще не обошли, вычислить расстояние до них от текущего узла, выбрать тот узел до которого ближе всего и перейти в него. Добавляем топливо и капканы, теперь к условию обхода добавлем: пока есть топливо - двигаемся.
Записан
Bepec
Гость
« Ответ #24 : Июнь 26, 2013, 19:54 »
на словах просто, я вот например слабо себе представляю реализацию графа Улыбающийся
Записан
CuteBunny
Гость
« Ответ #25 : Июнь 26, 2013, 20:26 »
Цитата: Bepec от Июнь 26, 2013,  19:54
на словах просто, я вот например слабо себе представляю реализацию графа Улыбающийся

Ну вроде граф можно представить в виде матрицы смежности. Либо, через структуры. Я как раз читаю книгу "Фунд. алгоритмы на графах с++", там вроде все на матрицах смежностей. У Шилдта в справочнике, вроде как задачи с графами были на структурах.

p.s.: мне даже кажется, что сложность не в представлении графа, а в решении задачи связности узлов: знать какие узлы мы уже посетили, как дойти до другого узла из текущего и т.д. Короче я пока застрял на первой главе и дальше не идёт!:)
« Последнее редактирование: Июнь 26, 2013, 20:30 от CuteBunny » Записан
Bepec
Гость
« Ответ #26 : Июнь 26, 2013, 20:40 »
Заметно. Ну да ладно, я беру отгул из этой темы - на работе запара, вы тут порешайте, арену сделайте, графики постройте пока без меня Веселый
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4349



Просмотр профиля
« Ответ #27 : Июнь 26, 2013, 21:01 »
Цитата: Igors от Июнь 26, 2013,  18:30
Мне лично неясно что писать - нет идей.
Что совсем никаких?

2all Давайте сводить основные правила в четкий список. Тогда можно будет прикинуть какие сенсоры и рычаги будут доступны боту. Кстати, сразу предлагаю подумать про жизнь нескольких ботов на одной карте. Может получится интересно.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #28 : Июнь 27, 2013, 07:45 »
Цитата: CuteBunny от Июнь 26, 2013,  19:41
А если так?

Входное поле магическим образом превращается в частично связный (частично потому что есть камни и пустоты) неориентированный (т.к. из одного узла можно дойти до другого и наоборот) граф. Выбираем случайный начальный узел в этом графе, смотрим, с какими другими узлами связан данный узел и какие узлы в этом списке мы не обошли, если по Приме, то нужно выбрать из этого списка такой узел, вес ребра до которого наименьшее, а если вес ребра - постоянное число, берем случайный узел из этого списка; и т.к. далее, пока не обойдем все узлы до которых можно дойти. Если дошли до такого узла, у которого все связные с ним мы уже обошли - наверное это тупик, надо посмотреть другие узлы несвязные с этим, которые мы еще не обошли, вычислить расстояние до них от текущего узла, выбрать тот узел до которого ближе всего и перейти в него. Добавляем топливо и капканы, теперь к условию обхода добавлем: пока есть топливо - двигаемся.
Ниже я это покритикую, но приятно видеть что человек думает (а не только мордой в салат/букварь  Улыбающийся)

Очевидно что "локальный" выбор ребра/хода как минимум не имеет ничего общего с оптимальностью. Ну ладно, шли-шли и в конце-концов уперлись в край. Переходим в ближайшую. Оттуда еще в ближайшую и.т.д. Так? (если нет поправьте). Если переход в ближайшую неосуществим (нет ребра), то возвращаемся на шаг назад  и оттуда смотрим ближайшую (а как иначе?). Это выглядит как-то "хаотично" (типа наркоман ищет дозу), ну оптимальностью здесь точно не пахнет. Однако для "просто обхода" по-видимому годится (ведь и этого не было).

Цитата: kambala от Июнь 26, 2013,  18:17
(т.е. можно хоть полный перебор использовать)
Да, кстати о птичках - прямой перебор никто не отменял, пусть он будет работать разумное время только на очень малленьких полях. Но я не могу сообразить как сделать прямым перебором  Улыбающийся

Цитата: Old от Июнь 26, 2013,  21:01
2all Давайте сводить основные правила в четкий список. Тогда можно будет прикинуть какие сенсоры и рычаги будут доступны боту. Кстати, сразу предлагаю подумать про жизнь нескольких ботов на одной карте. Может получится интересно.
Это др задача - типа "движок", у бота какой-то алгоритм, дальше жизнь покажет. Все-таки изначально это задача оптимизации, Вы ее "узурпировали". Да, Ваше предложение интересно, но тогда давайте подходить профессионально - кому мы это впарим? А то, знаете, энтузиазм быстро затухает (см напр последний пост Вереса), да и вообще я меркантильный человек  Улыбающийся 
Записан
Bepec
Гость
« Ответ #29 : Июнь 27, 2013, 07:57 »
Не надо на меня валить. У меня рефлектометр на запросы еле отвечает, мне с ним разбираться надо. *!battle cry!*
Записан
Страниц: 1 [2] 3   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


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