roboforum.ru

ну так этож твой курсовой проект, а не Антона
ему не надо

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

Добавлено спустя 1 минуту 2 секунды:
Мне то что сделать? я удаленно курс алгоритмов на графах читать не буду
Тем более, что указанная задача ни разу ни из простых.

Добавлено спустя 7 минут 25 секунд:
Это типа как "Я только что окончил 9-й класс, как мне взять вот этот поверхностный интеграл, и вообще, что такое интеграл?"

так давайте я еще раз постараюсь объяснить:
1) Интерфейс программы должен быть примерно такой как в программе которая привязана к сообщению
2) Кнопки должны быть такие же как и в этой программе
3) человек рисует помещение вид сверху и расставляет препятствия, примеры даны в архиве с программой
4) робот должен двигаться внутри помещение(тоесть внутри рисунка) я думаю что лучший алгоритм для обхода это "змейка", пройденные места он должен помечать как в программе в другой цвет
5) 2 условия:
1. Робот не должен попасть на одно и тоже место 2 раза(то есть в одну и ту же клетку)
2. В комнате так же рисуются препятствия, которые он должен обходить

PS программу эту писал omlin и выкладывал в теме "Алгоритм - обход пылесосом территории", если кто то знает как написать или есть исходники этой программы, буду очень благодарен

Добавлено спустя 29 секунд:
вот архив

Добавлено спустя 11 минут 25 секунд:
ясно все, тему в юмор пофиксили, меня обосрали по нескольку раз, а ничего дельного не сказали

2assassin6: Я же сказал - при такой постановке задачи я могу нарисовать помещение, в котором не существует указанного вами порядка обхода клеток.

ну а если рисовать только простые помещения как на примерах?

У вас листочка в клеточку под рукой нету? Возьмите да попробуйте порисовать, глядишь какую-нибудь эвристику придумаете для простых случаев. Когда будет что обсудить - возвращайтесь с конкретными вопросами.

assassin6, берёте конспекты/книги/методички/... по:
а) теории графов
б) программированию (тут читаем прорекурсию)
если выпивка, гулянки, нежелание учится или думать не мешают, то за пару дней напишите

Поддержи отечественного преподавателя

=DeaD=
а, таки успел прочитать про вопрос с преподом... я немного переписал сообщение, мне кажится так будет немного помягче

2Angel71: Не уверен я, что просто рекурсия + обычные алгоритмы на графах ему помогут. Или есть конкретные идеи?

на вскидку по памяти эйлеровы циклы, но тут почитать немного нужно, а то с годами забывается

Добавлено спустя 13 минут 25 секунд:
самое оно http://ru.wikipedia.org/wiki/Задача_коммивояжёра
таки гамильтонов цикл

Не...
Тут немного другая задача.
Думаю, что никакие формальные методы не прокатят - скорее эвристики.

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


Кроме того в условии много неизвестных.

Абсолютно непонятно, как робот находит препятствия - то ли когда упирается в него
"лбом", то ли может "чувствовать" стену с любой стороны независимо от направления движения...
А может быть видит издалека?

Но это все мои догадки, условия в том виде, в котором их ставит топикстартер вообще неопределенные,
мягко говоря.

2Michael_K знает незнает, да и робот это или нет какая разница? этож по сути алгоритмическая задача.
есть некий масив точек. грубо говоря нужно перемещатся из точки в точку так, чтоб пройтись по всем точкам не "заходя" в точку дважды и перемещаться можно только в соседнюю точку. яж не с потолка это навыдумывал. смотрим:

assassin6 писал(а):так давайте я еще раз постараюсь объяснить:
...
3) человек рисует помещение вид сверху и расставляет препятствия, примеры даны в архиве с программой
4) робот должен двигаться внутри помещение(тоесть внутри рисунка) я думаю что лучший алгоритм для обхода это "змейка", пройденные места он должен помечать как в программе в другой цвет
5) 2 условия:
1. Робот не должен попасть на одно и тоже место 2 раза(то есть в одну и ту же клетку)
2. В комнате так же рисуются препятствия, которые он должен обходить

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

знает незнает, да и робот это или нет какая разница?

Большая разница.
Представьте - одно дело когда ваш коммивояжер видит карту и заранее планирует маршрут.
И другое, когда он едет в следующий город, не зная, тупик там, пересадка на велосипед
или денег ему там отвалят.

И в случае, если тупик - придется возвращаться, а это запрещено условиями.

на входе картинка, ака двумерный масив бит.