Интересная задачка

[Bepec]

Если капканы и еда не исчезает, пойдёт алгоритм проезда по всем капканам до 10 hp и поездка нажраться )

[Old]

Примерно то же когда много капканов

Стоп, капканы бот видеть тоже не должен, иначе теряется их смысл.

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

[Igors]

Стоп, капканы бот видеть тоже не должен, иначе теряется их смысл.

Вы все-таки уходите/углубляйтесь "в решение", а не в "условие" 

[Bepec]

Тут такая засада. Пока нет начальных данных, решение может плавать

Вот если бот видит все капканы, но незнает сколько они дают - будет в разы легче

[Old]

Вы все-таки уходите/углубляйтесь "в решение", а не в "условие" 

Вы мне предлагаете написать арену?
Идеи следующий:
боты пишутся на javascript, ядро предоставляет боту небольшое api для исследования карты: посмотреть что в соседних ячейках и переместиться в соседнюю ячейку. Если в клетке:
* пусто - -1 энергии и переместиться на клетку;
* камень - -1 энергии и остались на месте;
* капкан - -10 энергии и переместиться на клетку;
* еда - +10 энергии и переместиться на клетку.

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

[kambala]

Транспортер должен обойти максимально возможное число полей за минимальное количество ходов

это требование означает, что задача является оптимизационной, и никакой речи о неполной видимости не может и быть. или решение не обязано быть оптимальным (т.е. можно хоть полный перебор использовать)?

еще не сказано можно ли посещать клетки больше одного раза.

[Igors]

Транспортер должен обойти максимально возможное число полей за минимальное количество ходов

это требование означает, что задача является оптимизационной, и никакой речи о неполной видимости не может и быть. или решение не обязано быть оптимальным (т.е. можно хоть полный перебор использовать)?

Согласен, в постановке автора - все поле открыто (и все веса известны). Хотя и закрытое (полуоткрытое) поле - тоже интересно. Повторюсь - пока не видно что вообще делать  

еще не сказано можно ли посещать клетки больше одного раза.

Мне кажется это оговаривать не нужно. Напр в левом верхнем углу свободные клетки, а перед ними "забор" из камней

000
ххх

До угла никак не добраться не пройдя какие-то др клетки дважды

Вы мне предлагаете написать арену?

Ну "не запрещаю" Мне лично неясно что писать - нет идей. Подумаю, если что-то будет - завтра напишу (чтобы по пустому не месить)

[kambala]

еще не сказано можно ли посещать клетки больше одного раза.

Мне кажется это оговаривать не нужно. Напр в левом верхнем углу свободные клетки, а перед ними "забор" из камней

000
ххх

До угла никак не добраться не пройдя какие-то др клетки дважды

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

[CuteBunny]

А если так?

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

[Bepec]

на словах просто, я вот например слабо себе представляю реализацию графа

[CuteBunny]

на словах просто, я вот например слабо себе представляю реализацию графа

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

p.s.: мне даже кажется, что сложность не в представлении графа, а в решении задачи связности узлов: знать какие узлы мы уже посетили, как дойти до другого узла из текущего и т.д. Короче я пока застрял на первой главе и дальше не идёт!:)

[Bepec]

Заметно. Ну да ладно, я беру отгул из этой темы - на работе запара, вы тут порешайте, арену сделайте, графики постройте пока без меня

[Old]

Мне лично неясно что писать - нет идей.

Что совсем никаких?

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

[Igors]

А если так?

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

Ниже я это покритикую, но приятно видеть что человек думает (а не только мордой в салат/букварь  )

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

(т.е. можно хоть полный перебор использовать)

Да, кстати о птичках - прямой перебор никто не отменял, пусть он будет работать разумное время только на очень малленьких полях. Но я не могу сообразить как сделать прямым перебором 

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

Это др задача - типа "движок", у бота какой-то алгоритм, дальше жизнь покажет. Все-таки изначально это задача оптимизации, Вы ее "узурпировали". Да, Ваше предложение интересно, но тогда давайте подходить профессионально - кому мы это впарим? А то, знаете, энтузиазм быстро затухает (см напр последний пост Вереса), да и вообще я меркантильный человек   

[Bepec]

Не надо на меня валить. У меня рефлектометр на запросы еле отвечает, мне с ним разбираться надо. *!battle cry!*