поиск источника радиации ( КуМиР ), советы по поиску литературы.

[kynew]

Здраствуйте, прошу помочь в решении задачи в среде разработки Кумир.
Студент 1го курса, программная инженерия. К сожалению, не совсем доходит пока принципы решения. Если есть возможность, прошу объяснить или дать ссылки , полезные начинающему программисту. Благодарен.
Можно дать подсказки к решению или что-то подобное, буду благодарен.
Использовать циклы,ветвления,вспомог.алгоритмы.

Задача.
Даны два источника радиации со значением N. От каждого источника образуется
радиоактивное пятно, представляющее собой квадрат с убывающей радиацией. При пересечении
пятен радиация суммируется. Найти источники радиации за наименьшее кол-во шагов



Добавлю, может кто-то посоветовать литература в следующих направлениях : разработка сайтов, с++ и в целом принцип решения задач, мышление.
Естественно с учетом того, что познания мои стремятся к 0.

[Abstraction]

Моя долго думать, при чём тут "разработка сайтов".
В смысле алгоритмов и общих познаний об ИИ, существует совершенно дивная книга - Рассел, Норвиг: "Искусственный интеллект: современный подход".

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

Об алгоритмах и их воплощении в языках программирования существует ряд очень хороших книг - Кнут: "Искусство программирования"; Кормен и др.: "Алгоритмы"; Ахо, Хопкрофт, Ульман: "Структуры данных и алгоритмы"; Скиена: "Алгоритмы".
По C++ есть талмуд Страуструпа; вроде неплохой самоучитель Шилдта; на более высоком уровне - книги Мейерса.
По разработке сайтов много посоветовать не смогу; вроде неплоха Роббинс, "Web-дизайн".

[kynew]

Разработка, ну это общие знания, они никому не помещают. Можно подробнее про 4 уравнения. Они должны описывать изменения радиации? Радиация уменьшается на 1 за клетку.

[Abstraction]

Сначала Вы. Поподробнее про мир, в котором предстоит действовать нашей программе (агенту). Что он из себя представляет, как можно проводить измерения, достоверны ли измерения, что такое "шаг"...
Грубо говоря, если у нас бесконечная доска, то мы можем очень долго источники искать, путешествуя по клеткам с нулевой радиацией.

[kynew]

Итак. Мир, это область, поделенная на клетки. Если бы можно было файл вставить, я бы вставил обстановку или клиент программы. Шаг - 1 клетка. Поле может быть произвольного размера. Источник радиации произвольной величины. С измерениями я сам еще не разобрался. Он может вроде бы запоминать и считывать данные. То есть, когда я писал если радиация >0 то, он ее находил. Если другое значение - он ее находил. Робот, агент, может ходить в стороны, закрашивать клетку ( в этой задаче - источник нужно закрасить). Насчет достоверности, я не понимаю Вас. К сожалению, мое обучение - 2 месяца. За эти месяцы я узнал лишь виды алгоритмов, ветвления и вспомог. алгоритмы.

[ CODE ]

Кусочек кода программы, в котором задействована радиация ( моя лабораторная прошлая )

нц пока справа свободно
если радиация = 5 то
закрасить
вправо
иначе
вправо
все
кц
[/CODE ]

[Abstraction]

Стартовая позиция агента задаётся программистом? В любом случае, у меня есть такое ощущение, что алгоритм, находящий оба источника за строго наименьшее количество шагов при любом их расположении, просто невозможен.

А так, вот мои идеи вчерне - естественно, надо проверять, у меня пока нет уверенности, что это будет работать во всех случаях.

Модель мира агента: пара точек, в которых находятся источники. Изначально обе точки помечены как "неизвестные". Для каждой клетки, агент может вычислить ожидаемый уровень радиации от "известных" ему источников.
Режим сканирования: агент идёт по доске зигзагами, пока не найдёт клетки с неожиданной радиацией (вообще, везде ниже под "радиацией" понимается измеренный уровень радиации минус ожидаемый от известных источников). При её обнаружении, агент переходит в режим обнаружения (агрессивный).
Режим обнаружения (агрессивный): агент движется вперёд до тех пор, пока в текущей клетке уровень радиации выше, чем в предыдущей посещённой. Если, по сравнению с предыдущей, уровень остался тем же или агент упёрся в стенку, следующий шаг делается перпендикулярно предыдущему (и запоминается, что был совершён поворот). Если уровень упал после поворота, агент разворачивается ("повернул не в ту сторону"). Если после поворота уровень остался тем же, агент переходит в режим обнаружения (неуверенный) (Это означает, что источники рядом и их влияние накладывается). Если уровень упал при движении по прямой, агент делает шаг назад и переходит в режим отметки. Если агент оказался в углу, он переходит в режим отметки.
Режим обнаружения (неуверенный): агент идёт, постоянно поворачивая "лесенкой", пока уровень радиации не меняется. Если он упал, агент делает шаг назад (развернувшись) и продолжает. Если он вырос, агент переходит в режим обнаружения (агрессивный).
Режим отметки: агент отмечает точку, на которой стоит, как "известную", помечает её, затем, если уровень радиации стал равен нулю, переходит в режим сканирования, иначе в режим обнаружения (неуверенный).

[Abstraction]

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

[kynew]

Не совсем понял идею. Я предполагал сделать так : дойти до левого верхнего угла поля. Затем вниз по диагонали идти и считать радиацию. Если увеличивается, то идти так же. Если нет, то пройти в сторону. Окончательно не придумал решения.

[kynew]

Итак.

Это обстановка, в которой действует робот ( ромбик). В данном случаи она 10*10. Источники радиации закрашены (значение 10). Цифры, это предполагаемые значения, без учета сложения значений от второго квадрата ( чтобы Вы могли представить, как изменяется радиация). Буква q в нашем случаи, значение радиации равное 16. Это суммируя значения обоих квадратов. И как мне найти закрашенные клетки. Обстановка не доделана. Цифры, как в левом верхнем углу, должны быть во всем квадрате, уменьшаясь на 1 за 1 клетку от квадрата. При наложении друг на друга - суммируются.


Даны два источника радиации со значением N. От каждого источника образуется
радиоактивное пятно, представляющее собой квадрат с убывающей радиацией. При пересечении
пятен радиация суммируется. Найти источники радиации за наименьшее кол-во шагов
Полное условие. Можно за любое кол-во шагов. Лишь бы понять принцип.

Источники могут быть в любом месте, размеры поля любые. Это, как пример.