roboforum.ru

Технический форум по робототехнике.

Алгоритм авто-сторожа

Re: Алгоритм авто-сторожа

Сообщение EdGull » 02 ноя 2009, 22:32

ну так этож твой курсовой проект, а не Антона
ему не надо :D
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 02 ноя 2009, 22:43

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

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

Добавлено спустя 7 минут 25 секунд:
Это типа как "Я только что окончил 9-й класс, как мне взять вот этот поверхностный интеграл, и вообще, что такое интеграл?"
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение assassin6 » 02 ноя 2009, 23:14

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

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

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

Добавлено спустя 11 минут 25 секунд:
ясно все, тему в юмор пофиксили, меня обосрали по нескольку раз, а ничего дельного не сказали
Вложения
eto.rar
(186.71 КиБ) Скачиваний: 8
assassin6
 
Сообщения: 28
Зарегистрирован: 22 окт 2009, 14:57
Откуда: moscow

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 02 ноя 2009, 23:15

2assassin6: Я же сказал - при такой постановке задачи я могу нарисовать помещение, в котором не существует указанного вами порядка обхода клеток.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение assassin6 » 02 ноя 2009, 23:17

ну а если рисовать только простые помещения как на примерах?
assassin6
 
Сообщения: 28
Зарегистрирован: 22 окт 2009, 14:57
Откуда: moscow

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 02 ноя 2009, 23:36

У вас листочка в клеточку под рукой нету? Возьмите да попробуйте порисовать, глядишь какую-нибудь эвристику придумаете для простых случаев. Когда будет что обсудить - возвращайтесь с конкретными вопросами.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 00:37

assassin6, берёте конспекты/книги/методички/... по:
а) теории графов
б) программированию (тут читаем прорекурсию)
:) если выпивка, гулянки, нежелание учится или думать не мешают, то за пару дней напишите
Последний раз редактировалось Angel71 03 ноя 2009, 00:47, всего редактировалось 1 раз.
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 03 ноя 2009, 00:46

Поддержи отечественного преподавателя :crazy: :ROFL:
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 00:48

=DeaD=
а, таки успел прочитать про вопрос с преподом... :D я немного переписал сообщение, мне кажится так будет немного помягче
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 03 ноя 2009, 01:06

2Angel71: Не уверен я, что просто рекурсия + обычные алгоритмы на графах ему помогут. Или есть конкретные идеи?
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 01:39

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

Добавлено спустя 13 минут 25 секунд:
:) самое оно http://ru.wikipedia.org/wiki/Задача_коммивояжёра
:crazy: таки гамильтонов цикл
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Re: Алгоритм авто-сторожа

Сообщение Michael_K » 03 ноя 2009, 02:23

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

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


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

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

Но это все мои догадки, условия в том виде, в котором их ставит топикстартер вообще неопределенные,
мягко говоря.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 02:52

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

:) так что обычные графы, на больше ну никак не тянет. детали реализации алгоритма и всё остальное (например может ли перемещаться наискось или нет) это уже совсем другой вопрос
Последний раз редактировалось Angel71 03 ноя 2009, 03:01, всего редактировалось 1 раз.
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Re: Алгоритм авто-сторожа

Сообщение Michael_K » 03 ноя 2009, 03:00

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

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

И в случае, если тупик - придется возвращаться, а это запрещено условиями.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 03:03

:) на входе картинка, ака двумерный масив бит.
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Пред.След.

Вернуться в Юмор

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1