ему не надо
roboforum.ru
Технический форум по робототехнике.
Алгоритм авто-сторожа
Re: Алгоритм авто-сторожа
ну так этож твой курсовой проект, а не Антона
ему не надо
ему не надо
Re: Алгоритм авто-сторожа
Так определиться бы с заданием, сформулированная вами задача не всегда имеет решение вообще.
Добавлено спустя 1 минуту 2 секунды:
Мне то что сделать?
я удаленно курс алгоритмов на графах читать не буду
Тем более, что указанная задача ни разу ни из простых.
Добавлено спустя 7 минут 25 секунд:
Это типа как "Я только что окончил 9-й класс, как мне взять вот этот поверхностный интеграл, и вообще, что такое интеграл?"
Добавлено спустя 1 минуту 2 секунды:
Мне то что сделать?
я удаленно курс алгоритмов на графах читать не буду Тем более, что указанная задача ни разу ни из простых.
Добавлено спустя 7 минут 25 секунд:
Это типа как "Я только что окончил 9-й класс, как мне взять вот этот поверхностный интеграл, и вообще, что такое интеграл?"
Re: Алгоритм авто-сторожа
так давайте я еще раз постараюсь объяснить:
1) Интерфейс программы должен быть примерно такой как в программе которая привязана к сообщению
2) Кнопки должны быть такие же как и в этой программе
3) человек рисует помещение вид сверху и расставляет препятствия, примеры даны в архиве с программой
4) робот должен двигаться внутри помещение(тоесть внутри рисунка) я думаю что лучший алгоритм для обхода это "змейка", пройденные места он должен помечать как в программе в другой цвет
5) 2 условия:
1. Робот не должен попасть на одно и тоже место 2 раза(то есть в одну и ту же клетку)
2. В комнате так же рисуются препятствия, которые он должен обходить
PS программу эту писал omlin и выкладывал в теме "Алгоритм - обход пылесосом территории", если кто то знает как написать или есть исходники этой программы, буду очень благодарен
Добавлено спустя 29 секунд:
вот архив
Добавлено спустя 11 минут 25 секунд:
ясно все, тему в юмор пофиксили, меня обосрали по нескольку раз, а ничего дельного не сказали
1) Интерфейс программы должен быть примерно такой как в программе которая привязана к сообщению
2) Кнопки должны быть такие же как и в этой программе
3) человек рисует помещение вид сверху и расставляет препятствия, примеры даны в архиве с программой
4) робот должен двигаться внутри помещение(тоесть внутри рисунка) я думаю что лучший алгоритм для обхода это "змейка", пройденные места он должен помечать как в программе в другой цвет
5) 2 условия:
1. Робот не должен попасть на одно и тоже место 2 раза(то есть в одну и ту же клетку)
2. В комнате так же рисуются препятствия, которые он должен обходить
PS программу эту писал omlin и выкладывал в теме "Алгоритм - обход пылесосом территории", если кто то знает как написать или есть исходники этой программы, буду очень благодарен
Добавлено спустя 29 секунд:
вот архив
Добавлено спустя 11 минут 25 секунд:
ясно все, тему в юмор пофиксили, меня обосрали по нескольку раз, а ничего дельного не сказали
- Вложения
-
eto.rar- (186.71 КиБ) Скачиваний: 8
Re: Алгоритм авто-сторожа
2assassin6: Я же сказал - при такой постановке задачи я могу нарисовать помещение, в котором не существует указанного вами порядка обхода клеток.
Re: Алгоритм авто-сторожа
ну а если рисовать только простые помещения как на примерах?
Re: Алгоритм авто-сторожа
У вас листочка в клеточку под рукой нету? Возьмите да попробуйте порисовать, глядишь какую-нибудь эвристику придумаете для простых случаев. Когда будет что обсудить - возвращайтесь с конкретными вопросами.
Re: Алгоритм авто-сторожа
assassin6, берёте конспекты/книги/методички/... по:
а) теории графов
б) программированию (тут читаем прорекурсию)
если выпивка, гулянки, нежелание учится или думать не мешают, то за пару дней напишите
а) теории графов
б) программированию (тут читаем прорекурсию)
если выпивка, гулянки, нежелание учится или думать не мешают, то за пару дней напишитеПоследний раз редактировалось Angel71 03 ноя 2009, 00:47, всего редактировалось 1 раз.
Re: Алгоритм авто-сторожа
Поддержи отечественного преподавателя 
Re: Алгоритм авто-сторожа
=DeaD=
а, таки успел прочитать про вопрос с преподом... я немного переписал сообщение, мне кажится так будет немного помягче
а, таки успел прочитать про вопрос с преподом...
я немного переписал сообщение, мне кажится так будет немного помягчеRe: Алгоритм авто-сторожа
2Angel71: Не уверен я, что просто рекурсия + обычные алгоритмы на графах ему помогут. Или есть конкретные идеи?
Re: Алгоритм авто-сторожа
на вскидку по памяти эйлеровы циклы, но тут почитать немного нужно, а то с годами забываетсяДобавлено спустя 13 минут 25 секунд:
самое оно Задача_коммивояжёра таки гамильтонов циклRe: Алгоритм авто-сторожа
Не...
Тут немного другая задача.
Думаю, что никакие формальные методы не прокатят - скорее эвристики.
Во-первых, робот не знает карту заранее,
Во-вторых, условие не проходить одну "клетку" дважды делает задачу нерешаемой в общем случае
(я предполагаю, что робот всегда занимает ровно одну клетку и может сделать "шаг" только в одну из соседних),
хотя можно свести задачу к минимизации "двойных шагов".
Кроме того в условии много неизвестных.
Абсолютно непонятно, как робот находит препятствия - то ли когда упирается в него
"лбом", то ли может "чувствовать" стену с любой стороны независимо от направления движения...
А может быть видит издалека?
Но это все мои догадки, условия в том виде, в котором их ставит топикстартер вообще неопределенные,
мягко говоря.
Тут немного другая задача.
Думаю, что никакие формальные методы не прокатят - скорее эвристики.
Во-первых, робот не знает карту заранее,
Во-вторых, условие не проходить одну "клетку" дважды делает задачу нерешаемой в общем случае
(я предполагаю, что робот всегда занимает ровно одну клетку и может сделать "шаг" только в одну из соседних),
хотя можно свести задачу к минимизации "двойных шагов".
Кроме того в условии много неизвестных.
Абсолютно непонятно, как робот находит препятствия - то ли когда упирается в него
"лбом", то ли может "чувствовать" стену с любой стороны независимо от направления движения...
А может быть видит издалека?
Но это все мои догадки, условия в том виде, в котором их ставит топикстартер вообще неопределенные,
мягко говоря.
Re: Алгоритм авто-сторожа
2Michael_K знает незнает, да и робот это или нет какая разница? этож по сути алгоритмическая задача.
есть некий масив точек. грубо говоря нужно перемещатся из точки в точку так, чтоб пройтись по всем точкам не "заходя" в точку дважды и перемещаться можно только в соседнюю точку.
яж не с потолка это навыдумывал. смотрим:
так что обычные графы, на больше ну никак не тянет. детали реализации алгоритма и всё остальное (например может ли перемещаться наискось или нет) это уже совсем другой вопрос
знает незнает, да и робот это или нет какая разница? этож по сути алгоритмическая задача.есть некий масив точек. грубо говоря нужно перемещатся из точки в точку так, чтоб пройтись по всем точкам не "заходя" в точку дважды и перемещаться можно только в соседнюю точку.
яж не с потолка это навыдумывал. смотрим:assassin6 писал(а):так давайте я еще раз постараюсь объяснить:
...
3) человек рисует помещение вид сверху и расставляет препятствия, примеры даны в архиве с программой
4) робот должен двигаться внутри помещение(тоесть внутри рисунка) я думаю что лучший алгоритм для обхода это "змейка", пройденные места он должен помечать как в программе в другой цвет
5) 2 условия:
1. Робот не должен попасть на одно и тоже место 2 раза(то есть в одну и ту же клетку)
2. В комнате так же рисуются препятствия, которые он должен обходить
так что обычные графы, на больше ну никак не тянет. детали реализации алгоритма и всё остальное (например может ли перемещаться наискось или нет) это уже совсем другой вопросПоследний раз редактировалось Angel71 03 ноя 2009, 03:01, всего редактировалось 1 раз.
Re: Алгоритм авто-сторожа
знает незнает, да и робот это или нет какая разница?
Большая разница.
Представьте - одно дело когда ваш коммивояжер видит карту и заранее планирует маршрут.
И другое, когда он едет в следующий город, не зная, тупик там, пересадка на велосипед
или денег ему там отвалят.
И в случае, если тупик - придется возвращаться, а это запрещено условиями.
Re: Алгоритм авто-сторожа
на входе картинка, ака двумерный масив бит.