Энциклопедия по робототехнике - Поиск пути на карте (обсужд.)

=DeaD=

Guriy писал(а):

возникли вопросы:
-Алгоритмы будут помещаться как сканы с бумаги?
-В каком виде алгоритмы нужно делать? На руссом алгоритмическом, блок-схемами, UML etc.?
а то кто-то код выложит по незнанию....

Есть классические подходы к изложению алгоритмов, например, как в общепризнанной книжке Кормена - "Алгоритмы и структуры данных" (http://www.ozon.ru/context/detail/id/83808/). Там используется условный язык в котором описываются все алгоритмы. Вполне можно привести в википедии описание этого языка и все примеры писать на нем. А вообще по опыту могу сказать, что можно легко приводить описания алгоритмов на любом общепризнанном языке (С++, Паскаль, Бейсик), если будут нормальные комменты и код с именами переменных - читабельный, то кому надо, тот без особых проблем разберется. А если комменты будут убогие и код написанный "лишь бы запустился", то никакой правильный язык или диаграммы не помогут.

Guriy писал(а):

имхо нужно просто добавить подразделы в программирование, типа:

Программирование:
- Алгоритмы и структуры данных
- Программная реализация

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

Ну-ну, еще скажите, что софт и железо оставим на верхнем уровне... предлагаю прекратить этот бессмысленный спор

.

Добавлено спустя 16 часов 38 минут 11 секунд:
Вот! Первая серьезная статья по алгоритмам написана и выложена

[[Перемещение робота в нужную точку карты]]

Прошу заценить.

Кстати, в ней же приведен пример языка для представления алгоритмов. Прошу высказаться всех желающих.

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

Guriy

=DeaD= писал(а):

Прошу заценить.

Кстати, в ней же приведен пример языка для представления алгоритмов. Прошу высказаться всех желающих.

Вот этот язык и назывался в мое время "русским алгоритмическим"

Digit

2 =DeaD=
1. Заценить смогу только в понедельник.
2. Навигацию по разделам закончу на неделе.
3. Дай все ж определение разделу "алгоритмы". Вернее, не определение, а описание раздела, краткую аннотацию. Для остальных разделов видимо аннотацией будет то, что вы с АВР123 понаписали?

=DeaD=

Digit писал(а):

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

А вообще есть сейчас смысл вводить эти аннотации? Есть человек заблудившийся в этой структуре, он не один?

Если уверены, что надо - давайте сделаем

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

Программирование - особенности разработки программ на различных платформах и в различных средах разработки, включая особенности программирования портов ввода-вывода.

И что с АВР123 написали - можно использовать как аннотации.

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

Digit

=DeaD= писал(а):

Если уверены, что надо - давайте сделаем

Ых, мы общаемся на "ты"

Я думаю, что надо. Когда будут аннотации у разделов - меньше будет вопросов у тех, кто занимается данным проектом. Пока абсолютная ясность насчет того, что где должно лежать и в каком виде, есть только у тебя! :wink:

Так что в целях внесения ясности аннотации и надо ввести.

=DeaD=

Digit писал(а):

=DeaD= писал(а):

Если уверены, что надо - давайте сделаем

Ых, мы общаемся на "ты"

Digit писал(а):

Я думаю, что надо. Когда будут аннотации у разделов - меньше будет вопросов у тех, кто занимается данным проектом. Пока абсолютная ясность насчет того, что где должно лежать и в каком виде, есть только у тебя! :wink:

Так что в целях внесения ясности аннотации и надо ввести.

Засчитывается

Digit

Добавил аннотации вроде близко к вашим, но с вольностями. Почитайте.

И может оформление разделов сделать, как на [[главной]] странице вики "добро пожаловать" сделано? Ну, чтоб каждый раздел в своем "окошке" синеньком?

=DeaD=

Digit писал(а):

Добавил аннотации вроде близко к вашим, но с вольностями. Почитайте.

И может оформление разделов сделать, как на [[главной]] странице вики "добро пожаловать" сделано? Ну, чтоб каждый раздел в своем "окошке" синеньком?

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

Digit

Ок. Давай я в понедельник сделаю.

Добавлено спустя 10 часов 42 минуты 21 секунду:

=DeaD= писал(а):

Вот! Первая серьезная статья по алгоритмам написана и выложена

[[Перемещение робота в нужную точку карты]]

Прошу заценить.

Заценил.
То ли из-за того, что читал посреди ночи, то ли написано так, но алгоритм Дейкстры, хоть я о нем и имею представление, не понял :pardon:

Не вполне понятно написано, как мне кажется. Возможно, имеет смысл вначале рассмотреть упрощенный случай - например алгоритм А* - а потом сформулировать уже алгоритм Дейкстры в общем виде?
И еще. Иллюстраций мало

Сейчас повторно статью перечитаю и нарисую какие-схемки для наглядности.

А,еще одну штуку вспомнил! Про переход от векторного пространства к взвешенному графу: не понятно, каким образом этот переход осуществляется. Подраздел называется " Переход к задаче поиска пути во взвешенном графе", но при этом для случая векторной карты данный переход не раскрыт. Непорядок.

=DeaD=

Digit писал(а):

Ок. Давай я в понедельник сделаю.

Вижу начал делать

а я закончил и картинок подцепил. Теперь просто конфетка! => [[Справочник решений]] <=

Digit писал(а):

Заценил.
То ли из-за того, что читал посреди ночи, то ли написано так, но алгоритм Дейкстры, хоть я о нем и имею представление, не понял :pardon:

Не вполне понятно написано, как мне кажется. Возможно, имеет смысл вначале рассмотреть упрощенный случай - например алгоритм А* - а потом сформулировать уже алгоритм Дейкстры в общем виде?
И еще. Иллюстраций мало

Сейчас повторно статью перечитаю и нарисую какие-схемки для наглядности.

Иллюстраций вообще вроде нет

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

Digit писал(а):

А,еще одну штуку вспомнил! Про переход от векторного пространства к взвешенному графу: не понятно, каким образом этот переход осуществляется. Подраздел называется " Переход к задаче поиска пути во взвешенном графе", но при этом для случая векторной карты данный переход не раскрыт. Непорядок.

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

Digit

=DeaD= писал(а):

Вижу начал делать

а я закончил и картинок подцепил. Теперь просто конфетка! => [[Справочник решений]] <=

Ага, супер!

=DeaD= писал(а):

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

Блин, я ступил

Читал еще в ночь с субботы, запомнил, что с векторной косяк, а сейчас сгоряча написал... :oops:

В общем, если опять ничего не путаю, там не дается метода составления графа. В этом разделе есть метод выделения бесконечного множества вершин, которые могут быть вершинами графа. Но поиск на бесконечном графе - это нонсенс!

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

=DeaD=

Digit писал(а):

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

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

) конечных чисел (каждый многоугольник вокруг препятствия имеет конечное число вершин) + 2 вершины (старт+финиш) = конечное число.

Digit писал(а):

Но поиск на бесконечном графе - это нонсенс!

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

А я этой и имел в виду

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

Digit

В статейке нарисовал немного картинок. Продолжаю рисование

Счас построю по твоему алгоритму и посмотрим :wink:

=DeaD=

=DeaD= писал(а):

Digit писал(а):

Но поиск на бесконечном графе - это нонсенс!

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

А я этой и имел в виду

Кстати, я поправил там слегка, теперь понятнее написано?

Добавлено спустя 6 минут 35 секунд:

Digit писал(а):

алгоритм Дейкстры, хоть я о нем и имею представление, не понял :pardon:

Не вполне понятно написано, как мне кажется.

Может вообще не париться, да в википедию сослаться общую? http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

Как думаешь? Или оттуда стырить описалово?

Digit

В общем, проверил векторный вариант на листике

робот поедет достаточно прямо... Но все-таки он не в состоянии проехать между двумя препятствиями по центру - он будет прижиматься к одному из препятствий. А еще решение задачи триангуляции не в статье не описано

Мы ж не можем сделать полносвязный граф - надо проверять пересечение ребер графа и препятствий... В общем, как-то так

Добавлено спустя 2 минуты 49 секунд:

=DeaD= писал(а):

Может вообще не париться, да в википедию сослаться общую? http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

Как думаешь? Или оттуда стырить описалово?

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

Добавлено спустя 6 минут 51 секунду:
Рисунков достаточно?

Добавлено спустя 29 минут 56 секунд:
А зачем обводить препятствия, представленные в виде прямоугольников, прямоугольниками со скругленными углами? Мы ж по-танковски поворачиваем и на время поворота забили... :unknown:

Добавлено спустя 5 минут 48 секунд:

Вики писал(а):

После построения такой карты границ препятствий можно легко составить граф допустимых путей на базе вершин многоугольников из только что построенной карты и начальной + конечной вершин. При этом, конечно, каждое ребро графа допустимо, если не пересекает какой-либо границы препятствия.

Вот к вопросу о триангуляции, о которой я говорил выше... Надо привести алгоритм, позволяющий построить граф, удовлетворяющий условиям из цитаты.

Добавлено спустя 1 час 9 минут 4 секунды:
...в общем для иллюстрации "на пальцах" засунул туда алгоритм А*. Пойдет? Или вообще теперь огромная статья - никто читать не будет?

roboforum.ru

Энциклопедия по робототехнике - Поиск пути на карте (обсужд.)

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